Constant-Time Inverse Suffix Array Queries in Compact Space and Sublinear-Time Construction of Suffix Array Indexes

Abstract

For a text $T\in[0..\sigma)^n$ with $2\leq\sigma\leq n$, its suffix array orders the suffix starting positions lexicographically, while its inverse suffix array maps each position to its suffix's rank. Since compressed suffix arrays and FM-indexes appeared in 2000, a central goal has been to support both queries in $O(n\log\sigma)$ bits. Thankachan recently reduced inverse suffix array query time to $O(\log\log n/\log\log\sigma)$, but constant time remained open. We give the first inverse suffix array structure with optimal space and query time: $O(n\log\sigma)$ bits and $O(1)$ time. For binary texts, this unconditionally separates the two queries for deterministic structures, since every $O(n)$-bit suffix array structure in the cell-probe model with $\Theta(\log n)$-bit cells has worst-case query time $\Omega(\log\log n/\log\log\log n)$. Construction is a second challenge: linear time can take $\Theta(\log_{\sigma} n)$ times as long as reading the input or writing a compact index. Previously, sublinear construction was known for only one such index supporting both queries. In the word RAM with $\Theta(\log n)$-bit words, we deterministically construct the new structure and two suffix array families from the packed text in $O(n\min(1,\log\sigma/\sqrt{\log n}))$ time. For $B\geq2$, the first family uses $O(n\log\sigma(1+\log_B\log_\sigma n))$ bits and has query time $O(B(1+\log_B\log_\sigma n))$, whereas the second uses $O(Bn\log\sigma(1+\log_B\log_\sigma n))$ bits and has query time $O(1+\log_B\log_\sigma n)$. Each has peak preprocessing space bounded by its index size. For binary texts, the second family matches the deterministic cell-probe time-space lower bound whenever $B\geq(\log\log n)^{\Omega(1)}$, and, outside the slowest-query regimes, improving the deterministic construction time to $o(n/\sqrt{\log n})$ would yield an equally fast Dictionary Matching algorithm.