Explaining the Inherent Tradeoffs for Suffix Array Functionality: Equivalences between String Problems and Prefix Range Queries

We address a fundamental question in string processing: how much time is needed to access suffix array entries when there is insufficient space to store it in plain form? The suffix array SAT [1 . . n] of a text T of length n is a permutation of 1, . . . , n that encodes the lexicographic ordering of the suffixes of T . While its canonical application is as a pattern matching index, the suffix array's simplicity, space efficiency, and theoretical guarantees have made it a cornerstone of string processing over the past 35 years, with applications spanning data compression, bioinformatics, and information retrieval.

Prior work has developed unidirectional reductions, showing how suffix array queries (given i ∈ [1 . . n], return SAT [i]) can be reduced, among others, to rank queries over the Burrows-Wheeler Transform (BWT). More recently, an alternative family of prefix queries was introduced, along with a reduction that transforms a simple tradeoff for prefix queries-requiring little more than a page to develop-into a suffix array tradeoff that matches all known space and query time bounds, while achieving sublinear construction time. For a binary text T ∈ 0, 1 n , this tradeoff achieves space usage S(n) = O(n) bits, preprocessing time Pt(n) = O(n/ √ log n), preprocessing space Ps(n) = O(n) bits, and query time Q(n) = O(log ϵ n) for any constant ϵ > 0. Despite this progress, a key question remains: can any of these complexities be improved using fundamentally different techniques?

In this work, we address this question as follows:

• We establish the first bidirectional reduction, proving that suffix array queries are, up to an additive O(log log n) term in query time, equivalent to prefix select queries in all four aspects. For a sequence W [1 . . m] of O(log m)-bit strings, a prefix select query, given i ∈ [1 . . m] and a string X, returns the position j of the ith leftmost string W [j] in W with prefix X. Our reduction unifies previous approaches and offers a structured framework for deriving new tradeoffs without sacrificing generality: before this work, prefix select queries constituted merely one approach to efficient suffix array queries, whereas we prove that, up to the O(log log n) additive overhead in query time, they capture all possible suffix array representations.

• We further show that other core string-processing problems-such as inverse suffix array queries, pattern ranking, lexicographic range queries, and pattern SA-interval queries-are also computationally equivalent to distinct types of prefix queries. In total, we identify six fundamental problem pairs, each consisting of a string problem and a corresponding prefix problem, and prove analogous equivalences.

Taken together, our reductions provide a general method for analyzing the efficiency of suffix array and related queries in terms of prefix queries, demonstrating that further improvements to fundamental string problems can be achieved by focusing solely on this recently introduced class of abstract queries.