In-Place BWT and Lyndon Array Construction in Constant Space

Felipe A. Louza, Arnaud Lefebvre · 2025

Read In-Place BWT and Lyndon Array Construction in Constant Space by Felipe A. Louza, Arnaud Lefebvre (2025) 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-2512-20869.txt.

Introduction

Felipe A. Louza and Arnaud Lefebvre build two text-processing structures using almost no extra memory. The Burrows-Wheeler transform reorders a string to help compression and search, while the Lyndon array records facts about each suffix's smallest rotation. Earlier work built the transform in place; the array usually needs more room.

Their extension keeps suffix ranks updated as the transform is built from right to left. A simple next-smaller-value pass then produces the Lyndon array with only constant extra space. The method runs in quadratic time, so the authors do not pitch it for everyday use. Its appeal is conceptual simplicity, plus working for alphabets of any size.

Catalog record

CREATORFelipe A. Louza, Arnaud Lefebvre
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE15 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-20869

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

In-Place BWT and Lyndon Array Construction in Constant Space Felipe A. Louza, Arnaud Lefebvre Abstract We present an extension of the in-place BWT algorithm of Crochemore et al. [ 8 ] that enables the construction of the Lyndon array using O ⁡ ( 1 ) O(1) extra space. Our approach incrementally maintains the lexicographic ranks of the suffixes during the right-to-left BWT construction and then derives the Lyndon array through a simple next-smaller-value procedure. Although not intended for practical use due to its quadratic running time, the method is conceptually simple and works for unbounded alphabets. 1 Introduction The Burrows–Wheeler Transform (BWT) [ 6 ] and the Lyndon array (LA) [ 11 ] are fundamental structures in string processing. The BWT underlies compressed indexing [ 10 ] and data compression [ 6 ] , while the LA captures the combinatorial structure of a string through its Lyndon factorization and plays a role in several pattern-matching [ 4 , 3 ] and combinatorial algorithms [ 1 , 2 ] The BWT depends on the lexicographic ordering of all suffixes of the input string. A standard approach computes it in O(n) time after constructing the suffix array (SA) [ 16 ] , which requires O(n\log n) bits of extra space. Okanohara and Sadakane [ 18 ] showed how to compute the BWT directly in linear time using only O(n\log\sigma) bits of extra space, where \sigma is the alphabet size, without storing the SA. Under the most restrictive space bound of O(1) extra words, the most efficient known construction is the in-place O(n^{2}) -time algorithm of Crochemore et al. [ 8 ] , which overwrites the text from right to left while maintaining only constant additional memory. Their method works in the general ordered alphabet model, requiring only constant-time symbol comparisons and no assumptions on the alphabet size. The Lyndon array can likewise be computed from the suffix ordering in O(n) time using O(n\log n) bits of extra space [ 11 , 12 , 13 , 17 ] . Alternatively, it can be obtained via Duval’s factorization algorithm [ 9 ] in O(n^{2}) time using O(1) extra space. More recently, Bille et al. [ 5 ] showed that the Lyndon array can be computed in O(n) time using only O(1) extra words, and in o(n) extra bits for the succinct representation [ 14 ] . Their algorithm, like that of Crochemore et al., operates in the general ordered alphabet model and does not depend on \sigma . In this paper we extend the in-place BWT algorithm of Crochemore et al. [ 8 ] so that it simultaneously computes the Lyndon array, while still using only O(1) extra space. The resulting algorithm constructs both structures in quadratic time and constant space. Compared with the linear-time algorithm of Bille et al. [ 5 ] , our approach is slower, but it has the unique advantage of producing the BWT in-place while computing the Lyndon array simultaneously using the same O(1) extra space. 2 Preliminaries i Sorted suffix T_{\mathsf{SA}[i]} \mathsf{SA}[i] \mathsf{ISA}[i] \mathsf{BWT}[i] \mathsf{LA}[i] 0 $ 6 4 A 1 1 A$ 5 3 N 2 2 ANA$ 3 6 N 1 3 ANANA$ 1 2 B 2 4 BANANA$ 0 5 $ 1 5 NA$ 4 1 A 1 6 NANA$ 2 0 A 1 Figure 1: SA, ISA, BWT and LA for T=\texttt{BANANA\$} . The Lyndon array \mathsf{LA}[i] gives the length of the longest Lyndon word starting at position i . Let \Sigma be an ordered alphabet of \sigma symbols, which may be unbounded. We assume symbols in \Sigma are compared in constant-time. Let $ be a special symbol (end marker) not in \Sigma that is lexicographically smaller than every symbol in \Sigma . We denote by \Sigma^{*} the set of all finite nonempty strings over \Sigma , and we define \Sigma\$=\{\,T\$\mid T\in\Sigma^{*}\,\} . For a string T=T[0]T[1]\dots T[n-1] over \Sigma\$ , of length n , we write T[i,j]=T[i]T[i+1]\dots T[j] for the substring starting at position i and ending at j , where 0\leq i\leq j<n . A prefix of T is a substring of the form T[0,k] , and a suffix is a substring of the form T[k,n-1] . We denote the suffix that begins at position i by T_{i} . The suffix array (SA) [ 16 ] of T\in\Sigma\$ is an array \mathsf{SA}[0,n-1] that contains a permutation of \{0,\dots,n-1\} such that T_{\mathsf{SA}[0]}<T_{\mathsf{SA}[1]}<\dots<T_{\mathsf{SA}[n-1]} in lexicographic order. The inverse suffix array (ISA) is the inverse permutation defined by \mathsf{ISA}[\mathsf{SA}[i]]=i . Hence, \mathsf{ISA}[k] gives the lexicographic rank of the suffix T_{k} . The Burrows–Wheeler Transform (BWT) [ 6 ] of a string T is a permutation of its characters that tends to cluster equal symbols. It can be defined using the suffix array as \mathsf{BWT}[i]=\begin{cases}T[\mathsf{SA}[i]-1],&\text{if }\mathsf{SA}[i]>0,\\ \$,&\text{otherwise.}\end{cases} A Lyndon word [ 7 ] is a nonempty string that is strictly smaller in lexicographic order than all of its proper nonempty suffixes. Every string can be uniquely factorized as a concatenation of Lyndon words in nonincreasing lexicographic order (the Lyndon factorization ). The Lyndon array (LA) of a string T\in\Sigma\$ is an array \mathsf{LA}[0,n-1] that stores, for each position i , the length of the longest Lyndon word starting at T[i] . Formally, \mathsf{LA}[i]=\min\{\,j-i\mid j>i,\ T[i,j-1]\text{ is not smaller than }T[j,n-1]\,\}, or equivalently, the Lyndon array can be computed from the inverse suffix array using the next smaller value (NSV) function: \mathsf{LA}[i]=\text{NSV}_{\mathsf{ISA}}(i)-i, where \text{NSV}_{\mathsf{ISA}}(i)=\min\{\,j>i\mid\mathsf{ISA}[j]<\mathsf{ISA}[i]\,\}, (1) and \text{NSV}_{\mathsf{ISA}}(i)=n if no such j exists. Figure 1 shows the SA, ISA, BWT and Lyndon array for T=\texttt{BANANA\$} . 3 In-Place BWT The in-place BWT algorithm of Crochemore et al. [ 8 ] computes the transform in quadratic time using only constant extra space, overwriting the input string from right to left with its BWT as the construction proceeds. The BWT is computed inductively on the length of the suffix. Let BWT(T_{s}) denote the BWT of the suffix T_{s}=T[s,n-1] . The base cases are the two rightmost suffixes: BWT(T_{n-2})=T_{n-2},\quad BWT(T_{n-1})=T_{n-1}. For the inductive step, assume that BWT(T_{s+1}) is already stored in T[s+1,n-1] . The algorithm computes BWT(T_{s}) by inserting the new suffix T_{s} in its correct lexicographic position among the suffixes T_{s+1},\dots,T_{n-1} . It relies on the fact that the position of the end marker $ in BWT(T_{s+1}) corresponds to the rank of the suffix T_{s+1} among the current suffixes. The algorithm consists of four steps, for iterations s=n-2,n-3,\dots,0 . 1. Find the position of the end marker. Locate the position p of $ in T[s+1,n-1] . 2. Compute the rank of the new suffix. Let c=T[s] be the first symbol of T_{s} . The local rank r of T_{s} among the suffixes T_{s},\dots,T_{n-1} is obtained by summing the number of symbols in T[s+1,n-1] that are strictly smaller than c , with the number of occurrences of c in T[s+1,p] . 3. Insert T_{s} into the sequence. Store c into T[p] , replacing the end marker $. 4. Shift symbols to insert a new end marker. Shift the block T[s+1,r] one position to the left and write $ at position T[r] . Then, BWT(T_{s})=T_{s} . Figure 2 illustrates the execution of the in-place BWT algorithm on the text BANANA$ for the iteration s=0 , showing the effect of Steps 1 and

Read the complete text