Compressing Suffix Trees by Path Decompositions

In this paper, we solve the long-standing problem of designing I/O-efficient compressed indexes. Our solution broadly consists of generalizing suffix sorting and revisiting suffix tree path compression. In classic suffix trees, path compression works by replacing unary suffix trie paths with pairs of pointers to $T$, which must be available in the form of some random access oracle at query time. In our approach, instead, we (i) sort the suffix tree's leaves according to a more general priority function $\pi$ (generalizing suffix sorting), (ii) we build a suffix tree path decomposition prioritizing the leftmost paths in such an order, and (iii) we path-compress the decomposition's paths as pointers to a small subset of the string's suffixes. At this point, we show that the colexicographically-sorted array of those pointers represents a new elegant, simple, and remarkably I/O-efficient compressed suffix tree. For instance, by taking $\pi$ to be the lexicographic rank of $T$'s suffixes, we can compress the suffix tree topology in $O(r)$ space on top of a $n\log\sigma + O(\log n)$-bits text representation while essentially matching the pattern matching I/O complexity of Weiner and McCreight's suffix tree. Another (more practical) solution is obtained by taking $\pi$ to be the colexicographic rank of $T$'s prefixes and using a fully-compressed random access oracle. The resulting self-index allows us to locate all occurrences of a given query pattern in less space and orders of magnitude faster than the $r$-index.