An(other) Entropy-Bounded Compressed Suffix Tree

Johannes Fischer, Veli Mäkinen, and Gonzalo Navarro

Suffix trees are one of the most important data structures in stringology, with myriads of applications in fluorishing areas like bioinformatics. As their main problem is space usage, recent efforts have focused on compressed suffix tree representations, which obtain large space reductions in exchange for moderate slowdowns. Such a smaller suffix tree could fit in a faster memory, outweighting by far the theoretical slowdown. We present a novel compressed suffix tree. Compared to the current compressed suffix trees, it is the first achieving at the same time sublogarithmic complexity for the operations, and space usage which goes to zero as the entropy of the text does. Our development contains several novel ideas, such as compressing the longest common prefix information, and totally getting rid of the suffix tree topology, expressing all the suffix tree operations using range minimum queries and a new primitive called next/previous smaller value in a sequence.