Suffixient Arrays: a New Efficient Suffix Array Compression Technique
read the original abstract
The Suffix Array is a classic text index enabling on-line pattern matching queries via simple binary search. The main drawback of the Suffix Array is that it takes linear space in the text's length, even if the text itself is extremely compressible. Several works in the literature showed that the Suffix Array can be compressed, but they all rely on complex succinct data structures which in practice tend to exhibit poor cache locality and thus significantly slow down queries. In this paper, we propose a new simple and very efficient solution to this problem by presenting the \emph{Suffixient Array}: a tiny subset of the Suffix Array \emph{sufficient} to locate on-line one pattern occurrence (in general, all its Maximal Exact Matches) via binary search, provided that random access to the text is available. We prove that: (i) the Suffixient Array length $\chi$ is a strong repetitiveness measure, (ii) unlike most existing repetition-aware indexes such as the $r$-index, our new index is efficient in the I/O model, and (iii) Suffixient Arrays can be computed in linear time and compressed working space. We show experimentally that, when using well-established compressed random access data structures on repetitive collections, the Suffixient Array $\SuA$ is \emph{simultaneously} (i) faster and orders of magnitude smaller than the Suffix Array $\SA$ and (ii) smaller and \emph{one to two orders of magnitude faster} than the $r$-index. With an average pattern matching query time as low as 3.5 ns per character, our new index gets very close to the ultimate lower bound: the RAM throughput of our workstation (1.18 ns per character).
This paper has not been read by Pith yet.
Forward citations
Cited by 9 Pith papers
-
String Representation in Suffixient Set Size Space
Every string admits a substring equation system representation of size O(χ(w)), providing the first such scheme for the repetitiveness measure χ.
-
Computing Smallest Suffixient Arrays in Sublinear Time
Algorithm computes smallest suffixient arrays in sublinear time O((n log σ)/√log n + min(r, r-bar) log^ε n) when alphabet is small and BWT has few runs.
-
Practical Linear-Time Computation of Smallest Suffixient Sets
A linear-time one-pass practical algorithm for building smallest suffixient sets is presented and empirically shown to dominate prior constructions.
-
Smallest Suffixient Sets: Effectiveness, Resilience, and Calculation
Smallest suffixient set size χ is O(r) for BWT runs r, o(v) for some lex parses, bounded by σ+2 on episturmian words, increases by at most 2 on append/prepend, and can increase by Ω(√n) under edits or rotations.
-
Smallest suffixient set maintenance in near-real-time
The smallest suffixient set can be maintained online in polyloglog time per letter in either left-to-right or right-to-left direction via Weiner's suffix tree primitives.
-
Compressing Suffix Trees by Path Decompositions
Introduces a suffix tree path decomposition technique that yields a suffix array sample of size at most r, improving the prior 2r bound for compressed indexes in external memory.
-
Faster PBWT prefix-array access via batching
Batching queries to accumulate r lg(h)/lg(r) substrings with average lg(r)/lg(h) haplotypes reported per substring enables O(r log h) bits and constant time per haplotype in PBWT prefix-array access.
-
Faster PBWT prefix-array access via batching
Batching queries to the PBWT prefix arrays enables constant-time haplotype reporting with O(r log h) space under stated batch-size and average-match conditions.
-
Smallest suffixient set maintenance in near-real-time
Online maintenance algorithms for the smallest suffixient set achieve polyloglog time per character using Weiner's suffix tree construction.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.