Published in

MDPI, Algorithms, 2(6), p. 319-351, 2013

DOI: 10.3390/a6020319

Springer, Lecture Notes in Computer Science, p. 94-105, 2010

DOI: 10.1007/978-3-642-13193-6_9

Links

Tools

Export citation

Search in Google Scholar

Practical Compressed Suffix Trees

Journal article published in 2010 by Rodrigo Cánovas ORCID, Gonzalo Navarro
This paper is made freely available by the publisher.
This paper is made freely available by the publisher.

Full text: Download

Green circle
Preprint: archiving allowed
Upload
Green circle
Postprint: archiving allowed
Upload
Green circle
Published version: archiving allowed
Upload
Policy details
Data provided by SHERPA/RoMEO

Abstract

The sux tree is an extremely important data structure for stringology, with a wealth of ap- plications in bioinformatics. Classical implementations require much space, which renders them useless for large problems. Recent research has yielded two implementations oering widely dierent space-time tradeos. However, each of them has practicality problems regarding either space or time requirements. In this paper we implement a recent theoretical proposal and show it yields an extremely interesting structure that lies in between, oering both practical times and aordable space. The implementation of the theoretical proposal is by no means trivial and involves signicant algorithm engineering.