BWT and Combinatorics on Words

The Burrows-Wheeler transform (BWT) is a fundamental algorithm introduced in 1994 by Michael Burrows and David Wheeler in the field of data compression [12]. Although more than 30 years have passed since its introduction, the BWT remains at the core of many tools used in bioinformatics for analyzing biological sequences (see [40, 45, 41]) and, in particular, constitutes the backbone of popular efficient compressed indexing schemes [21, 25].

The clustering effect of the BWT, i.e., the remarkable property of grouping identical characters when they share common contexts, has made it a powerful tool for boosting compression performances [54, 20] and enabling very efficient pattern searching in highly repetitive sequence collections [25, 38].

The BWT is a reversible transformation that lexicographically sorts all cyclic rotations of the input text $w$ and produces a permutation of the characters of $w$, denoted by $bwt(w)$, by taking the last character of these sorted rotations. From a combinatorial point of view, its simplicity combined with its effectiveness has made the BWT a fascinating study object [66]. The study of the combinatorial properties of the BWT not only helps in understanding its theoretical foundations but also in exploring its potential as a new combinatorial tool for analyzing the structural properties of words. A pioneering work in this area was done by Mantaci et al. [53], who showed that the BWT can be used to characterize standard Sturmian words, an infinite family of binary words widely studied in combinatorics on words [48].

This chapter aims to highlight strong connections between the BWT and combinatorics on words. Most combinatorial studies on the BWT have focused on the properties of words produced by the transformation and their relation to its clustering effect. Here, we provide an overview of these results, showing the role of the BWT as an effective new tool for assessing the complexity of combinatorial objects.

The effect of the BWT clustering on a word $w$ can be evaluated using the measure $r(w)$, which denotes the number of clusters (also called BWT runs) produced by the BWT applied to $w$, i.e., the number of runs of consecutive identical characters in $bwt(w)$. The value $r(w)$ is also used as a measure of the repetitiveness of the word $w$. In fact, the more repetitive a word is, the more likely it is that $bwt(w)$ contains long runs of consecutive identical characters. This property makes $w$ highly compressible using BWT-based compression algorithms. Furthermore, the performance in terms of both space and time of text compressors and compressed indexing data structures applied on a text $w$ can be evaluated by using $r(w)$ [24, 25]. Exploring the relationships between $r$ and the combinatorial properties of the words, as well as its sensitivity to some combinatorial transformations on words, can also have implications for the analysis and definition of BWT-based compressed indexing schemes.

In Section 3, we provide an overview of the main combinatorial properties of the BWT and relate them to some well-known permutations that can be associated with the words produced by the BWT as output (also called BWT images) [46].

Section 4 is focused on results that relate the number of BWT runs to the number of maximal runs in the input word [52, 51]. On the one hand, this provides a measure of the effectiveness of the BWT; on the other hand, it allows a deeper investigation into the combinatorial properties of words for which the BWT is more effective. In particular, in [11, 23] this relationship has been studied for morphic words, which are infinite families of binary words obtained by iteratively applying a morphism starting from a single character. Morphisms are a well-known combinatorial tool for constructing highly repetitive families of words. Other interesting researches connect the measure $r$ with other repetitiveness measures used in combinatorics on words, such as factor complexity, which counts the number of distinct factors that appear in a word for each length. Periodic words, for example, which are obtained by iterating the same factor, have a constant factor complexity. It is possible to define upper and lower bounds for the measure $r$ as a function of the measure $\delta$, the supremum of the normalized factor complexity [33].

Much attention has been given to the combinatorial characterization of the so-called clustering words under the BWT. This is the family of words for which $r$ assumes its minimum value. These words are the most compressible using BWT-based compressors. This topic is the focus of Section 5. The case of binary words has been studied in [53]. For larger alphabets, the relationship between clustering words and the trajectories of interval exchange transformations has been investigated in [19]. The combinatorial properties of a subclass of these words, called perfectly clustering words, for which the BWT produces sequences of lexicographically decreasing maximal runs, have been extensively studied. Only recently, the first combinatorial characterization of perfectly clustering words has been established [43]. Similarly, it can be interesting to explore the combinatorial properties of words for which the number of BWT runs is maximal. However, no known combinatorial characterization of such words exists. De Brujin words, on the other hand, are examples of infinite families of words for which the number of BWT runs is close to the maximum [32]. This result has been used in [47] to define a BWT-based algorithm to generate random de Brujin words.

In Section 6, we present results showing how the number of BWT runs is affected by some combinatorial operations on words. Sensitivity analysis is crucial for understanding the stability of compression-based repetitiveness measures [1]. It has been shown that, unlike other repetitiveness measures, $r$ is not invariant under reversal, with known upper and lower bounds on the ratio between $r$ of a word and of its reverse [29]. The impact of edit operations, such as insertion, deletion, and substitution, is also analyzed, establishing both upper and lower bounds for the growth in the number of BWT runs after edits [1, 30, 31]. Additionally, the section explores results on the behavior of $r$ under morphisms, proving that injective binary morphisms always increase or preserve $r$, with the well-known family of Sturmian morphisms being the only ones that preserve it [22].

Let $\mathrm{\Sigma }=\{a_1,a_2,\mathrm{\dots },a_{\sigma }\}$, with , be a finite ordered alphabet. The order on $\mathrm{\Sigma }$ induces the standard lexicographic order ${\le }_{lex}$ on the set ${\mathrm{\Sigma }}^{\ast }$ of words over $\mathrm{\Sigma }$.

Given a word $w=w_1{w}_2\mathrm{\cdots }{w}_n\in {\mathrm{\Sigma }}^{\ast }$ with each $w_i\in \mathrm{\Sigma }$, the length $n$ of $w$ is denoted by $|w|$. We let $\epsilon$ denote the empty word, the only word of length $0$. The set of words of length $n$ over $\mathrm{\Sigma }$ is denoted by ${\mathrm{\Sigma }}^n$. With $alph(w)$ we denote the subset of $\mathrm{\Sigma }$ of letters occurring in $w$. We let ${|w|}_{a_i}$ denote the number of occurrences in $w$ of the letter $a_i$. The Parikh vector $P_w$ of a word $w$ is the vector $[n_1,\mathrm{\dots },n_{\sigma }]$, where $n_i$ is the number of occurrences of $a_i$ in $w$, i.e, for each $a_i\in \mathrm{\Sigma }$, $P_w[i]={|w|}_{a_i}$.

A word $v$ is said to be a factor of a word $w$ if it occurs as a subword in $w$, i.e., $v=w[i,j]=w_i\mathrm{\cdots }{w}_j$, for some $1\le i\le j\le n$. The set of all factors of a word $w$ is denoted by $Fact(w)$. A factor of type $w[1,j]$ is called a prefix, while a factor of type $w[i,n]$ is called a suffix. The longest proper factor of $w$ that is both a prefix and a suffix is called the longest border of $w$. Let $Fact(w)$ be the set of factors of $w$. A factor $u$ of $w$ is right (resp. left) special in $w$ if there exist $a,b\in \mathrm{\Sigma }$, $a\ne b$, such that $ua,ub\in Fact(w)$ (resp. $au,bu\in Fact(w)$). A factor $u$ of $w$ is bispecial if it is both right and left special.

Two words $x,y\in {\mathrm{\Sigma }}^{\ast }$ are conjugates (or $x$ is a cyclic rotation of $y$), if $x=uv$ and $y=vu$, for some $u,v\in {\mathrm{\Sigma }}^{\ast }$. Conjugacy between words is an equivalence relation over ${\mathrm{\Sigma }}^{\ast }$. A word $z$ is called a circular factor of $w$ if it is a factor of some conjugate of $w$. A word $w$ is primitive if $w\ne u^h$ for every nonempty word $u$ and integer $h>1$. The cyclic rotations of a primitive word are all distinct. The (primitive) root of a word $w$, denoted by $\sqrt{w}$, is the shortest word such that $w={(\sqrt{w})}^h$, for some integer $h\ge 1$. So, a word is primitive if and only if it coincides with its root. A Lyndon word is a primitive word that is smaller than all of its proper conjugates (or, equivalently, suffixes).

The reversal of the word $w=w_1\mathrm{\cdots }{w}_n$ is the word $\tilde{w}=w_n\mathrm{\cdots }{w}_1$. If $w=\tilde{w}$, then $w$ is called a palindrome. The empty word is also assumed to be a palindrome. A word $w$ has the two-palindrome property if it can be written as $uv$ where $u$ and $v$ are palindromes. This is equivalent to the fact that $w$ is symmetric, i.e., $w$ is a conjugate of its reversal $\tilde{w}$.

A maximal run (or $cluster$) $u$ in a word $w$ is the factor $u=w[i,j]$ (with ) where $w_i=w_{i+1}=\mathrm{\cdots }=w_j$, and $w_{i-1}\ne w_i$, $w_j\ne w_{j+1}$ if $w_{i-1}$ and/or $w_{j+1}$ exist. Informally, a maximal run is a maximal factor of consecutive occurrences of the same letter.

The Burrows–Wheeler matrix (BWT matrix) of a word $w$ is the matrix ${ℬ}_w$ whose rows are the conjugates of $w$ in ascending lexicographic order. Let us denote by $F$ and $L$, respectively, the first and the last column of the BWT matrix of a word $w$. We have that $F$ is the sequence of sorted letters of $w$, i.e., $F=a_1^{n_1}{a}_2^{n_2}\mathrm{\cdots }{a}_{\sigma }^{n_{\sigma }}$, where $(n_1,n_2,\mathrm{\dots },n_{\sigma })$ is the Parikh vector of $w$; $L$, instead, is the Burrows–Wheeler Transform of $w$ and is denoted by $bwt(w)$.

A word is a BWT image if it is the Burrows–Wheeler Transform of some word. Not every word is a BWT image. The Burrows–Wheeler Transform is therefore a (non-surjective) map from the set of conjugacy classes of words to the set of words.

The standard permutation of a word $u=u_1{u}_2\mathrm{\cdots }{u}_n$ over $\mathrm{\Sigma }$ is the permutation ${\pi }_u$ of $\{1,2,\mathrm{\dots },n\}$ such that if and only if or $u_i=u_j$ and . In other words, ${\pi }_u$ orders distinct letters of $u$ lexicographically, and equal letters by occurrence order.

A word $u$ is a BWT image of a primitive word if and only if ${\pi }_u$ is a length-$n$ cycle, in which case the standard permutation of $u$ is also called $LF$-mapping. More generally, the problem of characterizing BWT images has been faced in [46], where the authors prove two necessary and sufficient conditions. The first one describes the words that are BWT images, while the second one explains which words can be converted to BWT images using a natural “pumping” procedure. Both conditions can be checked in linear time. In particular, the following theorem is proved.

By using the theorem one can deduce that the word $u=bccaaab=b^1{c}^2{a}^3{b}^1$ is not a BWT image because the ${\pi }_u$ decomposes into the $2$ cycles $(\mathrm{1\; 4})$ and $(\mathrm{2\; 6\; 3\; 7\; 5})$, but the lengths $1,2,3,1$ of the maximal runs in $u$ are coprime.

In the paper [46], the authors also characterize the words $v=c_1\mathrm{\cdots }{c}_h$ that can be transformed to $BWT$ images by a sort of “pumping”: each letter $c_i$ can be replaced by $c_i^{p_i}$ for an arbitrary positive number $p_i$. In particular, they prove the following theorem that uses the notion of global ascent³³3A word $v$ has a global ascent if $v=xy$, where $x$, $y$ are nonempty and the biggest letter of $x$ is less than or equal to the smallest letter of $y$. of a word.

Using the algorithm provided in their paper, starting from the word $v=dacba$, one can construct the word $w=daccbaa$ that is the $bwt$ image of $aacbcad$. An interesting open question is that of constructing the shortest possible $bwt$ image with a given order of letters.

The inverse standard permutation ${\pi }_u^{-1}$ of a word $u$, i.e., the inverse permutation of the standard permutation of $u$, can be obtained by listing in left-to-right order the positions of $a_1$ in $u$, then the positions of $a_2$, and so on. The inverse standard permutation of a BWT image is also called $FL$-mapping. If $w$ is a Lyndon word, the inverse standard permutation of $bwt(w)$, in cycle form, can also be obtained by reading the Inverse Suffix Array (ISA) of $w$ as a cycle [16, 59]. Recall that the ISA of a word $w$ is the array whose $i$th entry is the ranking of the suffix of $w$ starting at position $i$.

In the rest of this chapter, unless otherwise specified, we will deal with primitive words only.

If $w$ is a Lyndon word and $u$ is its BWT, then $w$ can be uniquely reconstructed from $u$. In fact, we have: $w_n=u_1$ and, for every $j=1,\mathrm{\dots },n-1$, $w_{n-j}=u_{{\pi }_u^j(1)}$. In other words, if ${\pi }_u=(j_1{j}_2\mathrm{\cdots }{j}_n)$ is the cycle corresponding to the standard permutation of $u$, with $j_1=1,$ then $w=u_{j_n}{u}_{j_{n-1}}\mathrm{\cdots }{u}_{j_1}$. If $w$ is a primitive word that is not Lyndon, it is sufficient to memorize its index in the BWT matrix to reconstruct it uniquely from its BWT.

One of the key properties of the BWT is that it produces a word that is typically more compressible than the word given as input. Such compressibility arises from the fact that sorting the conjugates of a given word $w$ places those with equal or similar prefixes consecutively in the matrix ${ℬ}_w$, so the characters preceding those similar contexts are grouped in $bwt(w)$. As a result, repetitions in the input word $w$ tend to produce long runs of equal characters in $bwt(w)$ (so-called clustering effect). For this reason, a commonly used measure to evaluate the repetitiveness of a text, and consequently its compressibility via the BWT, is the number of BWT runs, i.e., the number of maximal runs the BWT applied produces, after being applied to the text. More formally, given a word $w$, the measure $r=r(w)$ denotes the number of the BWT runs and it is defined as

where $runs(v)$ denotes the number of maximal runs of a word $v$. The more repetitive a word $w$ is, the lower the number $r$ of its BWT runs.

From a combinatorial point of view, the parameter $r$ has been studied to obtain more information about the combinatorial complexity and repetitiveness of a word from the number of BWT runs it produces. The following proposition, which immediately follows from Proposition 2, shows that the number of BWT runs of a periodic word is exactly the number of BWT runs of its primitive root.

In the previous section, we have shown that $r(w)$, the number of maximal runs of the BWT of a word $w$, can range from the size of the alphabet to, at most, the double of the number of runs of the original word $w$. In this section, we focus on these special extreme cases, namely, the one where $r(w)=|\mathrm{\Sigma }|$ and the one where $r(w)=2\cdot runs(w)$.

These extreme cases are important because they could have implications for the compressibility of the input text. Indeed, when the number of maximal runs is minimized, it is possible to achieve the optimal performance of the BWT-based compressor by using techniques such as run-length encoding (RLE) and move-to-front (MTF) [7]. In the opposite case, using a BWT-based compressor may not be effective. To understand the “clustering effect” from a combinatorial perspective, several studies have analyzed the structural properties of words that produce the maximum or minimum number of maximal runs when a text is transformed using the BWT.

In this section, we present some recent results concerning the sensitivity of $r$ with respect to some combinatorial operations on words. Sensitivity analysis is a fundamental aspect of understanding the stability of compression-based repetitiveness measures.