Faster Entropy-Bounded Compressed Suffix Trees.
Johannes Fischer, Veli Mäkinen, and Gonzalo Navarro.
Suffix trees are among the most important data structures in stringology,
with a number of applications in fluorishing areas like bioinformatics. Their
main problem is space usage, which has triggered much research striving for
compressed representations that are still functional. A smaller suffix tree
representation could fit in a faster memory, outweighting by far the
theoretical slowdown brought by the space reduction. We present a novel
compressed suffix tree, which is the first achieving at the same time
sublogarithmic complexity for the operations, and space usage that
asymptotically goes to zero as the entropy of the text does. The main ideas
in our development are compressing the longest common prefix information,
totally getting rid of the suffix tree topology, and expressing all the suffix
tree operations using range minimum queries and a novel primitive called
next/previous smaller value in a sequence. Our solutions to those operations
are of independent interest.