Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space

The last two decades have witnessed a dramatic increase in the amount of highly repetitive datasets consisting of sequential data (strings, texts). Processing these massive amounts of data using conventional data structures is infeasible. This fueled the development of compressed text indexes, which efficiently answer various queries on a given text, typically in polylogarithmic time, while occupying space proportional to the compressed representation of the text. There exist numerous structures supporting queries ranging from simple “local” queries, such as random access, through more complex ones, including longest common extension (LCE) queries, to the most powerful queries, such as the suffix array (SA) functionality. Alongside the rich repertoire of queries followed a detailed study of the trade-off between the size and functionality of compressed indexes (see: Navarro; ACM Comput. Surv. 2021). It is widely accepted that this hierarchy of structures tells a simple story: the more powerful the queries, the more space is needed. On the one hand, random access, the most basic query, can be supported using $\mathcal{O}\left(\delta \log \frac{n \log \sigma}{\delta \log n}\right)$ space (where n is the length of the text, $\sigma$ is the alphabet size, and $\delta$ is the text’s substring complexity), which is known to be the asymptotically smallest space sufficient to represent any string with parameters $n, \sigma$, and $\delta$ (Kociumaka, Navarro, and Prezza; IEEE Trans. Inf. Theory 2023). The other end of the hierarchy is occupied by indexes supporting the suffix array queries. The currently smallest one takes $\mathcal{O}\left(r \log \frac{n}{r}\right)$ space, where $r \geq \delta$ is the number of runs in the Burrows-Wheeler Transform of the text (Gagie, Navarro, and Prezza; J. ACM 2020). We present a new compressed index, referred to as $\delta$ SA, that supports the powerful SA functionality and needs only $\mathcal{O}\left(\delta \log \frac{n \log \sigma}{\delta \log n}\right)$ space. This collapses the hierarchy of compressed data structures into a single point: The space required to represent the text is simultaneously sufficient to efficiently support the full SA functionality. Since suffix array queries are the most widely utilized queries in string processing and data compression, our result immediately improves the space complexity of dozens of algorithms, which can now be executed in $\delta$-optimal compressed space. The $\delta$-SA supports both suffix array and inverse suffix array queries in $\mathcal{O}\left(\log ^{4+\epsilon} n\right)$ time (where $\epsilon \gt 0$ is any predefined constant). Our second main result is an $\mathcal{O}(\delta$ polylog $n)$-time construction of the $\delta$-SA from the Lempel-Ziv (LZ77) parsing of the text. This is the first algorithm that builds an SA index in compressed time, i.e., time nearly linear in the compressed input size. For highly repetitive texts, this is up to exponentially faster than the previously best algorithm, which builds an $\mathcal{O}\left(r \log \frac{n}{r}\right)$-size index in $\mathcal{O}(\sqrt{\delta n}$ polylog $n)$ time. To obtain our results, we develop numerous new techniques of independent interest. This includes deterministic restricted recompression, $\delta$-compressed string synchronizing sets, and their construction in compressed time. We also improve many other auxiliary data structures; e.g., we show the first $\mathcal{O}\left(\delta \log \frac{n \log \sigma}{\delta \log n}\right)$-size index for LCE queries along with its efficient construction from the LZ77 parsing.