Practical Linear-Time Computation of Smallest Suffixient Sets
Francisco Olivares, Gonzalo Navarro · 2026
Read Practical Linear-Time Computation of Smallest Suffixient Sets by Francisco Olivares, Gonzalo Navarro (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-31034.txt.
Introduction
Olivares and Navarro study suffixient sets. These are a recent tool for indexing huge repetitive text collections, such as genome archives and versioned document sets. A suffixient array keeps only a small subset of text positions. Sorted in a special right-to-left order, that subset still supports useful pattern matching. It also uses less space than the run-length Burrows-Wheeler transform, the current standard index.
The pair give the first algorithm that builds smallest suffixient sets in linear time. Their method makes a single pass over its inputs, and it is actually implemented. Earlier methods reached at most two of those three goals. In tests on large collections, the new algorithm beat or matched the best prior tools on both running time and memory. That makes the smaller index practical to build at scale.
Catalog record
| CREATOR | Francisco Olivares, Gonzalo Navarro |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 31 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.31034
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Practical Linear-Time Computation of Smallest Suffixient Sets Thanks: Funded by Basal Funds FB0001 and Fondecyt grant 1260080, ANID, Chile. Francisco Olivares, Gonzalo Navarro Abstract Suffixient arrays are recent structures that have attracted attention because they offer relevant pattern matching functionality in less asymptotic space than the Run-Length BWT, the de-facto standard to index highly repetitive string collections. Various algorithms exist for building them from the suffix array data structures. We present the first construction algorithm that is (i) linear-time, (ii) one-pass over the structures, and (iii) implemented and practical. This makes the construction particularly useful on large text collections, which we demonstrate empirically by showing that it dominates the space/time tradeoff map of the implemented constructions. 1 Introduction and Related Work Many of the fastest-growing text collections are highly repetitive, meaning that most documents are near-copies of others: genome collections like the One Million Genome Initiative, software repositories like Software Heritage, and versioned text collections like Wikipedia are examples of this phenomenon. Effectively searching such huge collections requires using storage formats that exploit repetitiveness to reduce space while offering fast indexed searches. The Run-Length Burrows-Wheeler Transform (RLBWT) is at the root of many successful compressed indexes for this scenario [ 4 , 16 , 13 , 8 ] . The space of this family of indexes dominated by r , the number of equal-letter runs in the BWT of the collection. A very recent development [ 9 ] further pushes towards space reduction by defining a new measure \chi\leq r , the size of the smallest so-called suffixient set of the text. This is a subset of the text positions that, if sorted by the corresponding prefixes in colexicographic order (i.e., comparing right-to-left), yields the so-called suffixient array [ 5 ] . Provided with a method to access the compressed text, the suffixient array can efficiently search for one occurrence of a pattern in the text, or find all its maximal substrings that occur in the text. This is less than the classic pattern matching functionality of finding all the pattern occurrences, but sufficient for various applications while using less space. Since smallest suffixient sets are meant to be used on large repetitive text collections, their efficient construction is key to their adoption. Cenzato et al. [ 6 , 5 ] already proposed two efficient constructions, which work on top of the suffix array (SA), the Burrows-Wheeler Transform (BWT), and the longest common prefix array (LCP) of the reversed text. Their first algorithm [ 6 ] , performs one single pass over those structures (i.e., it is “one-pass”) and takes time O(n+\overline{r}\log\sigma) , where n is the length of the text, \overline{r} is the r value for the reverse text, and \sigma is the alphabet size. Their second algorithm [ 6 ] , which we call LF, is linear-time but not one-pass, just as their third algorithm [ 5 ] , which we call FM. FM is faster than LF but uses more space. Bonizzoni et al. [ 2 ] recently proposed the first algorithm that is both linear-time and one-pass, but no implementation is reported. Fujimaru et al. [ 12 ] present linear-time online algorithms that work directly on the text, processing them left-to-right or right-to-left. In another SPIRE submission, Fujimaru et al. [ 11 ] present another linear-time algorithm, which is however not one-pass nor implemented; it uses some structures built on the text and some on its reverse. They also present the first sublinear-time construction (also not implemented). Finally, Köppl and Kucherov [ 15 ] gave a near-real time construction algorithm, without reporting an implementation. In this context, we present the first algorithm to build smallest suffixient sets that is (i) linear-time, (ii) one-pass, and (iii) implemented. See Table 1 . We empirically demonstrate its practicality by comparing it with the implemented alternatives: our algorithm outperforms previous algorithms, or matches the best ones, in both time and space. Algorithm linear-time one-pass implemented One-pass [ 6 ] no yes yes LF [ 6 ] yes no yes FM [ 5 ] yes no yes Bonizzoni et al. [ 2 ] yes yes no Online [ 12 ] yes yes* yes Linear [ 11 ] yes no no Near-linear [ 15 ] no yes* no Ours yes yes yes Table 1: The existing algorithms to build a smallest suffixient set, and ours in this context. Algorithms “Online” and “Near-linear” are one-pass over the text, not in the same sense as the others. 2 Preliminaries By [i,j] we refer to all values i,i+1,\dots,j , if i\leq j , and [i,j]=\emptyset , otherwise; and we define [n]=[1,n] . A string T[1,n]\in\Sigma^{n} is a concatenation of n elements of an alphabet \Sigma=\{1,\dots,\sigma\} . The length of T is denoted by |T|=n . The empty string \epsilon is the only string satisfying |\epsilon|=0 . T[i] indicates the i -th element of T , and T[i,j]=T[i]\dots T[j] is the substring of T starting at position i and ending at position j , if 1\leq i\leq j\leq n , and T[i,j]=\epsilon otherwise. A prefix of T is a substring of the form T[1,j] and a suffix is a substring of the form T[i,n] . T^{\text{rev}} denotes the reversal of T , that is, T^{\text{rev}}=T[n]\dots T[1] . Given two strings T,S\in\Sigma^{+} , none a prefix of the other, and a total order over \Sigma , the lexicographic order <_{lex} over \Sigma^{+} is defined as T<_{lex}S if and only if T[1,i]=S[1,i] and T[i+1]<S[i+1] , for some i . The suffix array of T[1,n] ( \mathrm{SA}(T) ) is a permutation of the elements of T such that T[\mathrm{SA}(T)[i],n]<_{lex}T[\mathrm{SA}(T)[j],n] for any 1\leq i<j\leq n , namely \mathrm{SA}(T)[i] is the i -th suffix of T in lexicographic order. We assume T ends with a special character \$ , which is smaller than any other symbol in \Sigma and only occurs in T[n] , so \mathrm{SA} is well defined. The longest common prefix array of T ( \mathrm{LCP}(T) ) is defined as \mathrm{LCP}(T)[i]=\ell if and only if 2\leq i and T[\mathrm{SA}(T)[i-1],\mathrm{SA}(T)[i-1]+\ell-1]=T[\mathrm{SA}(T)[i],\mathrm{SA}(T)[i]+\ell-1] and T[\mathrm{SA}(T)[i-1]+\ell]\neq T[\mathrm{SA}(T)[i]+\ell] , that is, \mathrm{LCP}(T)[i] is the length of the maximal prefix shared by the (i-1) -th and the i -th sufixes of T in the lexicographic order; we further define \mathrm{LCP}(T)[1]=0 . The Burrows-Wheeler Transform array of T ( \mathrm{BWT}(T) ) is defined as \mathrm{BWT}(T)[i]=T[\mathrm{SA}(T)[i-1]] , if 2\leq i , and \mathrm{BWT}(T)[1]=T[n] , that is \mathrm{BWT}(T)[i] is the symbol preceding the i -th sufix of T . By \mathrm{SA}_{r} , \mathrm{LCP}_{r} , and \mathrm{BWT}_{r} we refer to \mathrm{SA}(T^{\text{rev}}) , \mathrm{LCP}(T^{\text{rev}}) , and \mathrm{BWT}(T^{\text{rev}}) , respectively, where in this case we assume T^{\text{rev}}=(T[1,n-1])^{\text{rev}}\$ . Given an integer array \mathcal{I} , the previous smaller value array of \mathcal{I} ( \mathrm{PSV}(\mathcal{I}) ) is a lenght- |\mathcal{I}| array defined as \mathrm{PSV}(\mathcal{I})[i]=j if and only if j=\max(\{k<i\mid\mathcal{I}[k]<\mathcal{I}[i]\}\cup\{0\}) , that is, j is the largest index in [1,i-1] for which \mathcal{I} is strictly smaller than \mathcal{I}[i] , if such value exists, and j=0 otherwise. The next smaller value array, \mathrm{NSV}(\mathcal{I}) , is defined analogously for the smaller value with and index bigger than i (or |\mathcal{I}|+1 if none exists). For brevity, by \mathrm{PSV} and \mathrm{NSV} we will refer to \mathrm{PSV}(\mathrm{LCP}_{r}) and \mathrm{NSV}(\mathrm{LCP}_{r}) , respectively. A run in \mathrm{BWT}_{r} is a maximal contiguous substring