Fast Fully-Compressed Suffix Trees

Gonzalo Navarro and Luís Russo

We speed up the fully-compressed suffix tree representation (FCST), which is the only one using asymptotically optimal space. Classical representations of suffix trees are fast, but require too much space (O(n log n) bits for a string of length n over an alphabet of size s, which is considerably more than the n log s bits needed to represent the string). Modern compressed suffix tree representations are smaller, getting close to the compressed string size, and achieve constant to sublogarithmic time for most operations. However, their space is not fully optimal. An exception is the FCST, which achieves fully optimal space but its times are superlogarithmic. Our contribution significantly accelerates the FCST representation, achieving for many operations log-logarithmic times on typical texts. The resulting FCST variant becomes very attractive in terms of space and time, and a promising alternative in practice.