Practical Compressed Suffix Trees
Rodrigo Cánovas and Gonzalo Navarro
The suffix tree is an extremely important data structure for stringology,
with a wealth of applications in bioinformatics. Classical implementations
require much space, which renders them useless for large problems.
Recent research has yielded two implementations offering
widely different space-time tradeoffs. However, each of them has practicality
problems regarding either space or time requirements. In this paper we
a recent theoretical proposal and show it yields an extremely interesting
structure that lies in between, offering both practical times and affordable
space. The implementation of the theoretical proposal is by no means trivial
and involves significant algorithm engineering.