Faster Compressed Suffix Trees for Repetitive Collections
Gonzalo Navarro and Alberto Ordúñez
Recent compressed suffix trees targeted to highly repetitive sequence
collections reach excellent compression performance, but operation times
are very high. We design a new suffix tree representation for this scenario
that still achieves very low space usage, only slightly larger than the best
previous one, but supports the operations orders of magnitude faster. Our
suffix tree is still orders of magnitude slower than general-purpose
compressed suffix trees, but these use several times more space when the
collection is repetitive.
Our main novelty is a practical grammar-compressed tree representation with
full navigation functionality, which is useful in all applications where
large trees with repetitive topology must be represented.