Dynamic Fully-Compressed Suffix Trees

Luís M. S. Russo, Gonzalo Navarro, Arlindo L. Oliveira

Abstract:

Suffix trees are by far the most important data structure in stringology, with myriads of applications in fields like bioinformatics, data compression and information retrieval. Classical representations of suffix trees require $O(n \log n)$ bits of space, for a string of size $n$. This is considerably more than the $n \log_2\sigma$ bits needed for the string itself, where $\sigma$ is the alphabet size. The size of suffix trees has been a barrier to their wider adoption in practice. A recent so-called fully-compressed suffix tree (FCST) requires asymptotically only the space of the text entropy. FCSTs, however, have the disadvantage of being static, not supporting updates to the text. In this paper we show how to support dynamic FCSTs within the same optimal space of the static version and executing all the operations in polylogarithmic time. In particular, we are able to build the suffix tree within optimal space.