Source-linked AI summary
Tiny Suffix Arrays
Sharma V. Thankachan
TL;DR
SA and ISA are fundamental string-processing structures, but their space requirements motivate query support with limited auxiliary space when the text is available. The paper builds an O(n/τ)-word structure for both queries, achieving Õ(τ^3) query time; with LCE, this places three fundamental string primitives in sublinear auxiliary space.
Problem
The paper asks how to support SA and ISA queries within a bounded auxiliary-space budget when the text is available.
Source: §1 · p. 1Method
The data structure combines sampled suffix-array leaves with LCE and pattern- and suffix-reporting structures to answer SA and ISA queries.
Source: §2 · pp. 2–3, §3.2 · p. 4Results
Both SA and ISA queries take Õ(τ^3) time using O(n/τ) auxiliary words for any 1 ≤ τ ≤ n.
Source: §1 · p. 2, §3.2.1 · p. 5Takeaways & Limitations
Together with existing LCE results, the result supports three fundamental string primitives in sublinear auxiliary space.
Source: §4 · p. 5The text must be available through a read-only oracle with constant-time character access; the structure also maintains an O(n/τ)-space LCE structure with O(τ)-time queries.
Source: §2 · p. 2
Abstract
from arXiv · showhide
Suffix array and inverse suffix array queries on a text of length $n$ can be answered in $\widetilde{O}(\tau^3)$ time using an auxiliary data structure occupying $O(n/\tau)$ words, for any $\tau \in [1,n]$.
1 Introduction
The introduction frames suffix-array and inverse-suffix-array queries as a space problem when the text is available, then gives an O(n/τ)-word, Õ(τ^3)-time tradeoff for both. It positions this result against prior compressed representations and small-space work.
Background
- SA and ISA are fundamental to string processing, data compression, bioinformatics, and full-text indexing.The introduction also points to compressed suffix trees and entropy- and repetitiveness-aware representations as results in the broader research line.Source: §1 · p. 1
Motivation
- Compressed suffix arrays and the FM-index support SA and ISA queries in Õ(1) time using O(n log σ) bits, but representations still need Ω(n log σ) bits in the worst case.The paper focuses on auxiliary space because the text is available.Source: §1 · p. 1
- The problem is to support SA and ISA queries within a prescribed auxiliary-space budget, given read-only access to the underlying text.Explicit arrays each require Θ(n log n) bits, while the text uses n⌈log σ⌉ bits; either permutation has an Ω(n log σ)-bit worst-case lower bound.Source: §1 · p. 1
Related work
- Prior small-auxiliary-space results cover LCE, internal pattern matching, text indexing, and sparse suffix-tree construction, but not a general O(n/τ)-word tradeoff for both SA and ISA.The introduction identifies Thankachan [30] as supporting SA, ISA, and suffix-tree operations in polylogarithmic time using O(n log log log σ) bits, still linear in n up to an alphabet-dependent factor.Source: §1 · p. 2
Theorem 1.1
- For any 1 ≤ τ ≤ n, both SA and ISA queries take Õ(τ^3) time with O(n/τ) auxiliary words on a read-only text.The text oracle supports constant-time character access.Source: §1 · p. 2
2 Building Blocks
The building blocks combine LCE queries and suffix reporting with a batched pattern-reporting structure. These components support the later data structure within O(n/τ) auxiliary words.
LCE queries
- The section assumes read-only, constant-time character access and uses Bille et al.’s O(n/τ)-space structure for O(τ)-time LCE queries.LCE(i, j) returns the longest common prefix length of the suffixes starting at i and j.Source: §2 · p. 2
Suffix reporting
- Given two suffixes with LCE at least τ, the structure reports the k suffixes strictly between them lexicographically in Õ(τ^2 + k) time using O(n/τ) space.It samples suffixes and prefixes at τ-spaced positions and uses two-dimensional range reporting on their ranks.Source: §2 · pp. 2–3
Pattern reporting
- For a pattern P and character range [α, β], the structure reports occurrences of every Pc in Õ(m + τ^3/m^2 + (1 + τ^2/m) · occ) time using O(n/τ) space.Encoding text characters in binary reduces the reporting queries from O(σ) to O(log σ).Source: §2 · p. 3
3 The Data Structure
The data structure splits at τ = √n: larger τ permits direct selection and comparison, while smaller τ uses sampled suffix-array leaves and decodes the intervals between them. Both SA and ISA queries take Õ(τ^3) time.
3.1 Solution for τ > √n
- For τ > √n, SA uses space-efficient selection and ISA counts lexicographically smaller suffixes, with each query taking Õ(τ^3) time.Frederickson’s selection algorithm handles √n < τ ≤ n/log n; Munro and Raman’s constant-workspace algorithm handles larger τ.Source: §3.1 · pp. 3–4
3.2 Solution for τ ≤√n
- For τ ≤ √n, sampling every τth suffix-array leaf and adding boundaries of length-τ prefix subtrees uses O(n/τ) sampled leaves.Consecutive sampled leaves with LCP below τ have the property that every intervening suffix has LCP below τ with each endpoint; the sampled suffix array plus working space remains O(n/τ) words.Source: §3.2 · p. 4
3.2.1 Decoding SA[i]
- Decoding SA[i] between consecutive sampled leaves takes Õ(τ^3) time, whether their LCE is at least τ or below τ.The first case reports and sorts the intervening suffixes; the second uses pattern-reporting queries and then sorts them.Source: §3.2.1 · pp. 4–5
3.2.2 Decoding ISA[j]
- For an unsampled suffix, ISA[j] is found by locating it between sampled suffixes, decoding that interval, and determining its rank in Õ(τ^3) time.The initial binary search among sampled suffixes takes Õ(τ log n) time.Source: §3.2.2 · p. 5, §3.2.1 · p. 5
4 Concluding Remarks
The conclusion presents the SA and ISA results as space–time trade-offs under bounded auxiliary space. Together with existing LCE results, they put three fundamental string primitives within sublinear auxiliary space.
Concluding remarks
- Together with existing LCE results, the SA and ISA trade-offs show that three fundamental string primitives can use sublinear auxiliary space.The authors say this opens opportunities to explore space–time trade-offs across string-processing problems, since suffix arrays underpin many data structures and algorithms beyond exact pattern matching.Source: §4 · p. 5