2026/07/19 by Sharma V. Thankachan
#cs.DS
The suffix array (\SA) and inverse suffix array (\ISA) are fundamental data structures in string algorithms. Given a text of length n over an integer alphabet of size σ, explicitly storing these structures requires Θ(nlog n) bits, motivating compressed representations that approach the information-theoretic minimum of nlogσ bits. Two landmark solutions are the FM-index, which achieves succinct space and supports \SA and \ISA queries in roughly logarithmic time, and the Compressed Suffix Array (CSA), which uses O(nlogσ) bits and answers both queries in O(logσεn) time. Nearly all subsequent compressed indexes, including entropy-compressed and repetitiveness-aware variants, support \SA and \ISA using essentially the same techniques, leading to similar space--time trade-offs. This raises a fundamental question: under the same asymptotic space bound, do \SA and \ISA have the same inherent query complexity? We provide evidence that this symmetry is not intrinsic. Under an O(nlogσ)-bit space bound, we show that \SA queries are unlikely to admit logo(1) n query time, suggesting that improving the classical CSA bound would require a major breakthrough. In contrast, we present a new encoding supporting \ISA queries in O(τ+loglog n/loglogσ) time using (1+1/τ+o(1))nlogσ bits, for any τ≥1. Our main insight is that the \LF-mapping, traditionally implemented using the Burrows--Wheeler Transform, can be adapted to support \ISA queries directly from the packed text, eliminating the need to store the BWT while achieving substantially faster query times.