Dynamic Fully-Compressed Suffix Trees
Luís Russo, Gonzalo Navarro, and Arlindo Oliveira
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 s bits needed
for the string itself, where s 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.