A Survey of the Bijective Burrows-Wheeler Transform

The Burrows-Wheeler Transform (BWT) of a string $T$ is a permutation of the characters of $T$. Consider the multiset of rotations of $T$, . If $T=U^k$ for a primitive string $U$, then each element of $[T]$ will appear $k$ times in this multiset. Now $\mathrm{𝖡𝖶𝖳}(T)$ can be obtained by concatenating the last characters of these strings when they are given in omega-order (or, equivalently in this case, in lexicographic order). For example, $\mathrm{𝖡𝖶𝖳}(\mathrm{𝚊𝚋𝚛𝚊𝚌𝚊𝚍𝚊𝚋𝚛𝚊𝚊})=\mathrm{𝚛𝚊𝚍𝚊𝚛𝚌𝚊𝚊𝚊𝚊𝚋𝚋}$. See also Figure 1. The number of runs of the BWT of a string $T$ is denoted $r(T)$, i.e. $r(T)=\rho (\mathrm{𝖡𝖶𝖳}(T))$. Thus, $r(\mathrm{𝚊𝚋𝚛𝚊𝚌𝚊𝚍𝚊𝚋𝚛𝚊𝚊})=8$.

Let $S$ be a string of length $n$. The standard permutation of $S$ is a permutation ${\pi }_S$ of the index set $\{0,\mathrm{\dots },n-1\}$ of $S$, defined as follows: if either , or $S[i]=S[j]$ and . In other words, ${\pi }_S(i)$ is the position of character $S[i]$ in the stable sort of the characters of $S$. For example, for $S=\mathrm{𝚛𝚊𝚍𝚊𝚛𝚌𝚊𝚊𝚊𝚊𝚋𝚋}$, ${\pi }_S=[10,0,9,1,11,8,2,3,4,5,6,7]=(0,10,6,2,9,5,8,4,11,7,3,1)$, where we give $\pi$ both in one-line notation and in cycle notation. When $S$ is the BWT of some string, then the standard permutation of $S$ is also known as LF-mapping [29], which can be used to recover the original string up to rotation. For example, given ${\pi }_S$ as above, we can recover the Lyndon word $T$ with $\mathrm{𝖡𝖶𝖳}(T)=S$, spelling it back-to-front, as follows: $T[n-1]=S[0]=𝚛$, and for $i>1$, $T[n-i]=S[{\pi }^i(0)]$. We get $T=\mathrm{𝚊𝚊𝚊𝚋𝚛𝚊𝚌𝚊𝚍𝚊𝚋𝚛}$, which is the Lyndon rotation of abracadabraa. The process can be modified to uniquely recover the input string by either adding the lexicographic rank of the rotation to be recovered, or by adding a unique end-of-string marker to the string.

Since all rotations of $T$ have the same BWT, it is clear that the BWT is not a bijection on ${\mathrm{\Sigma }}^{\ast }$. It is well known that a string $S$ is the BWT of a primitive string if and only if ${\pi }_S$ is cyclic. Likhomanov and Shur gave a more general characterization [50]: $S$ is the BWT of some string if and only if the number of cycles of ${\pi }_S$ equals the greatest common divisor of the lengths of the runs of $S$. This characterization encompasses powers, as well.

In fact, the number of strings of length $n$ which are the BWT of some string (referred to as BWT images in [50]) equals the number of necklaces of length $n$. This follows from the definition of the BWT and the fact that the LF-mapping uniquely recovers the conjugacy class of the input string. In other words, the BWT is a bijection between necklaces of length $n$ and BWT images of length $n$. The number of necklaces of length $n$ is ${\sum }_{d|n}Lyn(d,\sigma )$, where $\sigma$ is the alphabet size and $Lyn(d,\sigma )$ is the number of Lyndon words of length $d$ over an alphabet of size $\sigma$, or equivalently, the number of conjugacy classes of primitive words of length $d$. This can be seen by a counting argument on necklaces, distinguishing the case where the necklace is primitive (of which there are $Lyn(n,\sigma )$ many), and the case where it is a power $U^k$, with $U$ primitive (in which case $d=|U|$ is a divisor of $n$). It is known [51] that $Lyn(d,\sigma )=\frac{1}{d}{\sum }_{d^{\prime }|d}\mu (d^{\prime }){\sigma }^{\frac{d}{d^{\prime }}}$, where $\mu$ is the Möbius function defined as: $\mu (1)=1$, $\mu (n)={(-1)}^j$ if $n$ is the product of $j$ distinct primes, or $0$ otherwise ($n$ is divisible by a square number). Note that for all $n$, the number of necklaces of length $n$ is at least ${\sigma }^n/n$, with equality if and only if $n$ is prime.⁵⁵5It is sometimes imprecisely stated, e.g. [32, 47], that $(1/n)$th of all strings are BWT images, but this is only true for $n$ prime.

The extended BWT (eBWT) [54] is essentially⁶⁶6The original definition of eBWT does not assume the strings to be Lyndon words, but stores information concerning the rotations of the input strings. a bijection between multisets of Lyndon words of total length $n$ and strings of length $n$. It is defined as the concatenation of the last characters of the rotations of the input strings, given in omega-order. Underlying the $\mathrm{𝖾𝖡𝖶𝖳}$ is the observation that the BWT is a special case of the inverse of the Gessel-Reutenauer bijection [31] between permutations of a given type and descent set and strings of a given type (see [21] for more details).

The $\mathrm{𝖾𝖡𝖶𝖳}$ is a straightforward generalization of the BWT in that for any primitive string $T$, $\mathrm{𝖾𝖡𝖶𝖳}(\{T\})=\mathrm{𝖡𝖶𝖳}(T)$. Given a string $S$, the standard permutation ${\pi }_S$ of $S$ (i.e., its LF-mapping) can be used to construct a multiset $ℳ$ with $\mathrm{𝖾𝖡𝖶𝖳}$ equal to $S$ in the same way as before, yielding one string per cycle of ${\pi }_S$. For more details on the $\mathrm{𝖾𝖡𝖶𝖳}$, see [18] in this volume. Note that the eBWT is surjective: every string is the eBWT of something. However, the preimage is not necessarily a string; in general, it is a multiset of strings.

The bijective BWT (BBWT), on the other hand, is a variant of the BWT which is a bijection from ${\mathrm{\Sigma }}^{\ast }$ to ${\mathrm{\Sigma }}^{\ast }$: every string is the BBWT of some string (of the same length).

The BBWT is thus the eBWT of the multiset of Lyndon factors of $T$ (see Example 2). The inverse of the BBWT is constructed as follows: Take a string $S$, and let $\{L_1,\mathrm{\dots },L_m\}$ be the multiset of Lyndon words that we get via the LF-mapping from $S$, i.e., one string per cycle of ${\pi }_S$. Now concatenate the strings $L_i$ in non-increasing order. This yields the unique string $T$ whose BBWT is $S$.

We define the generalized conjugate array $\mathrm{𝖦𝖢𝖠}$ of a string $T$ as follows: $\mathrm{𝖦𝖢𝖠}[j]=i$ if the conjugate of $L_k$ starting in position $i$ is $j$th in omega-order among all conjugates of the Lyndon factors of $T$, where $L_k$ is the Lyndon factor containing position $i$ of $T$.

Notice that the standard BWT can be considered as a special case of BBWT since $\mathrm{𝖡𝖡𝖶𝖳}(\mathrm{𝗆𝗂𝗇𝗋𝗈𝗍}(T))=\mathrm{𝖡𝖶𝖳}(T)$. Indeed, the two transforms coincide exactly on the set of necklaces:

If we fix the inverse BWT to be always the necklace representative of the conjugacy class, then one can consider the BWT as a bijection from a subset of strings (necklaces) to a subset of strings (BWT images). The BBWT thus is a generalization of the BWT, since it is a bijection from ${\mathrm{\Sigma }}^{\ast }$ to ${\mathrm{\Sigma }}^{\ast }$ and coincides with the BWT on this subset.

Similarly to the BWT, we will be interested in the number of runs of the BBWT of a string $T$, denoted $r_B(T)$, i.e. $r_B(T)=\rho (\mathrm{𝖡𝖡𝖶𝖳}(T))$. Thus, $r_B(\mathrm{𝚊𝚋𝚊𝚊𝚋𝚊𝚋𝚊𝚊𝚋𝚊𝚊𝚋})=6$.

In the rest of the paper, $n$ denotes the length of the string under investigation (if no misunderstanding is possible).

The first analysis of a BBWT construction algorithm with sound time bounds is due to Bannai et al. [6], who draw a connection to the algorithm of [14] constructing the eBWT, and were able to adapt this algorithm for computing the BBWT in $O(n\log n/\log \log n)$ time. This BBWT construction algorithm works in an online fashion, i.e., it builds the BBWT per Lyndon factor, starting with the first one, and then incrementally indexes each further factor until adding the last Lyndon factor. Compared to the BWT, there is no known algorithm computing the BWT in an online model that allows reading a specific prefix of the text (such as its Lyndon factors). However, it is possible to construct the BWT online by reading the text from the reverse order (e.g., [22]) – a setting for which we do not know whether a solution for the BBWT exists. The main idea of the BWT construction algorithm is that it computes the BWT of $T\$$, where $\$$ is a sentinel character smaller than all other characters appearing in $T$. The construction starts with BWT just storing $\$$, and at any time later, the BWT contains exactly one $\$$ at a specific position. By the definition of the LF mapping, going from this position backwards would give the last character of $T$. Now, assume that we have built the BWT of $T[i..n-1]$ and want to insert $T[i-1]$. For that, we perform a backward search step from the position of $\$$ for the character $T[i-1]$. Say we end up at a position $p$, then we exchange $\$$ with $T[i-1]$ but insert $\$$ at position $p$ and recurse, see Figure 3 for a visualization. The same trick works without $\$$ for the BBWT if we process the Lyndon factors sequentially, starting from the leftmost and lexicographically largest one. This is because, when inserting a new Lyndon factor $L_x$, we know that it is lexicographically smaller than all other Lyndon factors. Hence, we can insert the last character $c$ of $L_x$ at the first position in the BBWT and backward search $c$ to find the insertion position of the previous character in $L_x$. This gives the following complexities.

In this section, we will sketch the two existing linear-time algorithms for BBWT construction. Both algorithms are non-trivial modifications of linear-time suffix array construction algorithms. The first, due to Bannai et al. [7] (2021), is based on the well-known SAIS-algorithm of Nong et al. [63]. The second, due to Olbrich et al. [64] is a modification of the algorithm GSACA by Baier [3]. In what follows, we will sketch the proofs of the following theorem:

In the case of a string that is terminated by an end-of-string character, the BWT can be computed in linear time from the suffix array, by noticing that $\mathrm{𝖡𝖶𝖳}[i]=T[n-1]$ if $\mathrm{𝖲𝖠}[i]=0$, and $\mathrm{𝖡𝖶𝖳}[i]=T[\mathrm{𝖲𝖠}[i]-1]$ otherwise. This, however, uses the fact that the last suffix is the smallest among all suffixes, which is not necessarily the case in general. In actual fact, the conjugate array $\mathrm{𝖢𝖠}$ would be needed, since for all $0\le i\le n-1$, we have $\mathrm{𝖡𝖶𝖳}[i]=T[\mathrm{𝖢𝖠}[i]-1]$, where the subtraction is modulo $n$. One solution is to first compute the Lyndon rotation of $T$ because for Lyndon words, the suffix array and the conjugate array coincide. The first algorithm that directly computes the BWT of a string $T$ without an end-of-string character, and without computing Lyndon rotations, was given in [15] (and was inspired by the SAIS-based algorithm [7] we are about to see).

For the BBWT, we need is the $\mathrm{𝖦𝖢𝖠}$ of $T$, due to the following connection:

The two linear-time algorithms below take advantage of this idea by modifying known SA-construction algorithms to construct the $\mathrm{𝖦𝖢𝖠}$ instead of the $\mathrm{𝖲𝖠}$.

Köppl et al. [46] discovered that the BBWT construction algorithm of Theorem 4, which incrementally builds the BBWT from the text by one Lyndon factor at a time, can be used in the setting of in-place construction, where only $O(1)$ additional working space is allowed to turn $T$ into its BBWT. Here, the main observation is that the in-place construction algorithm of [22] for the BWT can be changed to compute the BBWT instead of the BWT. That is because we can compute the Lyndon factorization with Duval’s algorithm with constant space while constructing the BBWT. In detail, we let Duval’s algorithm detect the next Lyndon factor, then pause it to consume this factor, and recurse by resuming Duval’s algorithm.

For restoring the original text from the BBWT, there is a need for supporting the FL-mapping, the inverse of the LF-mapping. The FL-mapping can be implemented by a select query on $\mathrm{𝖡𝖡𝖶𝖳}$, which however needs $O(n^{1+\epsilon })$ time for a solution with constant working space [59] for a constant $\epsilon >0$.

A more involved analysis revealed that it is even possible to turn BWT into BBWT directly without inversion using $O(n^{2+\epsilon })$ time and $O(1)$ working space. The idea is to run Duval’s algorithm using FL-mappings to detect the Lyndon factorization. Since Duval’s algorithm uses three pointers to text positions, we can simulate the pointers by pointers into the BWT and use the FL-mapping to advance a pointer. When a Lyndon factor has been detected, we try to move $\$$ such that the Lyndon factor has its own orbit in the standard permutation of the BBWT. However, this change can also break the cycle of the remaining BWT, for which additional moves have to be performed.

The authors also gave an algorithm for computing the run-length compressed BBWT online, Lyndon factor by Lyndon factor. Similar to computing the run-length compressed BWT online reading the reversed text, the authors also show how to compute the run-length compressed BBWT in $O(r_B)$ space and $O(n\log n/\log \log n)$ time.

On the practical side, we are aware of the implementations by David A. Scott⁸⁸8https://web.archive.org/web/20210615215623/http://bijective.dogma.net/bwts.zip, Branden Brown⁹⁹9https://github.com/zephyrtronium/bwst, Yuta Mori in his OpenBWT library¹⁰¹⁰10https://web.archive.org/web/20170306035431/https://encode.ru/attachment.php?attachmentid=959&d=1249146089, and of Neal Burns¹¹¹¹11https://github.com/NealB/Bijective-BWT. While the first two are naive but easily understandable implementations calling general sorting algorithms on all conjugates to directly compute the BBWT, the implementation of Yuta Mori seems to be an adaptation of the SAIS algorithm to induce the BBWT. The implementation of Neal Burns takes an already computed suffix array $\mathrm{𝖲𝖠}$ as input, and transforms $\mathrm{𝖲𝖠}$ into $\mathrm{𝖦𝖢𝖠}$ by shifting values to the right until they fit. Hence, the running time is based on the lengths of these shifts, which can be $O(n^2)$, but seem to be negligible in practice for common texts.

Finally, the two linear-time algorithms we presented, due to Bannai et al. [8]¹²¹²12https://github.com/mmpiatkowski/bbwt and Olbrich et al. [64]¹³¹³13https://gitlab.com/qwerzuiop/lfgsaca, have both been implemented.

The Run-Length compressed BWT (RLBWT) [53] is a representation of $T$ of size $r(T)$. From its definition, it is not clear why the RLBWT can be considered as a form of dictionary compression, since the transform is applied before the run-length encoding. However, suppose for each run in the BWT, we define the reference (copying) of a symbol to point to the previous symbol in the run (except for the first one in the run). Then, if we consider all of these references on corresponding positions of the text, the text can be partitioned into at most $2r(T)+1$ phrases, where each phrase is either a single symbol that corresponds to the beginning of a run, or, a maximal substring such that the offsets of the references are the same for all positions in the phrase [62, Theorem 9]¹⁴¹⁴14We note that [62] assumes that strings are terminated with a $\$$ and the proved bound is $2r(T)$. For strings that are not terminated by $\$$, there can be $2r(T)+1$ phrases, e.g., with $T=ababaaaabab$.. The latter phrases can then be encoded by two integers – the length and offset, resulting in a representation for $T$ of size $O(r(T))$, known as bidirectional macro schemes (BMSs) [70], the most general (and most powerful) representation in dictionary compression.

The above relation can be shown as follows: Suppose two lexicographically adjacent rotations ${\mathrm{𝗋𝗈𝗍}}^{i+1}(T)$ and ${\mathrm{𝗋𝗈𝗍}}^{j+1}(T)$ have the same BWT symbol (i.e., $T[i]=T[j]$). Then, position $j$ will reference position $i$, with offset $i-j$. Due to the property of LF mapping, ${\mathrm{𝗋𝗈𝗍}}^i(T)$ and ${\mathrm{𝗋𝗈𝗍}}^j(T)$ will also be adjacent rotations, and, if they have the same BWT symbol as well, position $j-1$ will reference position $i-1$, with offset $(i-1)-(j-1)=i-j$ and therefore have the same offset. This continues until the adjacent rotations do not have the same BWT symbol, which can happen at most $r(T)-1$ times – at boundaries of runs. A minor point we have overlooked above is that the offsets $i-j$ and $(i-1)-(j-1)$ would always be the same in the cyclic sense, but they can become different in the linear sense when $i=0$ or $j=0$, since position $-1$ wraps around to position $n-1$. This can happen at most twice. Since there are exactly $r(T)$ single symbol phrases, the total number of phrases is at most $(r(T)-1)+2+r(T)=2r(T)+1$.

Badkobeh et al. [2] showed that for the Run-Length compressed BBWT (RLBBWT), a similar BMS of size $O(r_B(T))$ can be induced. An important observation to achieve this bound is that $r_B(T)$ can be lower bounded by the number of distinct Lyndon factors $\mathrm{\ell }(T)$ of the Lyndon factorization of $T$ [16, 2]. This follows from [16, Corollary 9], which states that:

Since, in the case of BBWT, $ℳ=\{L_1,\mathrm{\dots },L_{\mathrm{\ell }(T)}\}$ where all the Lyndon factors are distinct and primitive, we have:

Applying the same referencing of symbols for BBWT as BWT described above, the same arguments hold, except that there can be more instances where the references wrap around, i.e., when $i$ or $j$ corresponds to the beginning of a Lyndon factor. However, this is at most twice for each distinct Lyndon factor, since identical Lyndon factors occur adjacently. Therefore, by Corollary 12, the total number of phrases can be bounded by $O(r_B(T)+\mathrm{\ell }(T))=O(r_B(T))$.

Therefore, RLBWT and RLBBWT respectively induce BMSs of size $O(r(T))$ and $O(r_B(T))$, where all references point to a smaller (omega-order) position, and can be considered as a form of dictionary compression.

Denote by $z(T)$ the size of the LZ77¹⁵¹⁵15We use the name LZ77 which is prevalent in the literature, though it has been mentioned that LZ76 is more precise [60]. factorization [48] of $T$. It is known that $z(T)$ is the size of a smallest BMS where all references point to a smaller (text-order) position. The question of whether $r(T)$ can be bounded in terms of $z(T)$ was answered by Kempa and Kociumaka [43, Theorem 3.2], who showed that for any string $T$, $r(T)=O(z(T){\log }^{2}n)$ holds.

Badkobeh et al. [2] showed that this proof can be extended to the case of $r_B(T)$. The term $z(T)$ appears in Kempa and Kociumaka’s proof when considering, for given $k$, the set $T_k$ of all substrings of $T^{\omega }$ of length $k$, where $|T_k|$ can be bounded by $O(z(T)k)$ since any substring of $T^{\omega }$ must have an occurrence containing the last position of an LZ77 phrase (including the last phrase). The main difference in the proof is in the definition of the set $T_k$, which should be modified to be the set of all substrings of length $k$ of $\{{(L_1)}^{\omega },\mathrm{\dots },{(L_{\mathrm{\ell }(T)})}^{\omega }\}$, rather than $T^{\omega }$. This can be bounded by $O(z(T)k+\mathrm{\ell }(T)k)$, since such a substring is either a substring of $T$, or, is a substring of ${(L_i)}^{\omega }$ that is not a substring of $L_i$. $|T_k|=O(z(T)k)$ is obtained by applying the result by Urabe et al. [71] that shows $\mathrm{\ell }(T)\le 4z(T)$. The rest of the proof is essentially the same, giving:

For BWT, a tighter bound of $r(T)=O(\delta (T){\log }^{2}n)$ where $\delta (T)={\max }_{1\le d\le n}\{T_d/d\}$ follows easily, since $\delta (T)\ge |T_k|/k$, $|T_k|=O(\delta (T)k)$. Kempa and Kociumaka further show a bound of $r(T)=O(\delta \log \delta \max \{1,\log \frac{n}{\delta \log \delta }\})$ [43, Theorem 3.7]. We note that $\delta (T)$ is known to lower-bound (and can be strictly smaller than) all dictionary compression measures [45]. Tighter bounds for $r_B(T)$ are not yet known.

The following results are known about the change that $r_B$ may undergo if some operation is applied to $T$.

Badkobeh et al. [2] considered the difference between $r(T)$ and $r_B(T)$. Notice that a lower bound on the multiplicative difference between $r(T)$ and $r_B(T)$ is a lower bound on the multiplicative difference between $r_B(T)$ and $r_B(T^{\prime })$ for any rotation $T^{\prime }$ of $T$ due to Proposition 3, since $r(T)$ is equivalent to $r_B(\mathrm{𝗆𝗂𝗇𝗋𝗈𝗍}(T))$, the RLBBWT of a specific rotation of $T$. A family of strings where $r_B(T)$ could be a $\mathrm{\Theta }(\log n)$ factor larger than $r(T)$ was reported.

The family for Theorem 17 is the Fibonacci words of odd order, i.e., $\{F_{2k+1}:k=0,1,\mathrm{\dots }\}$. It is well known that $r(F_k)=2$ for any $k\ge 2$. For $r_B(F_{2k+1})$, using a result by Melançon on the Lyndon factorization of $F_{2k+1}$ [58], it is shown that the number of Lyndon factors is $k+1$. Then, by Corollary 12, $r_B(F_{k+1})=\mathrm{\Omega }(k)$ is obtained.

The opposite case was shown in [5]: that $r(T)$ can be a $\mathrm{\Theta }(\log n)$ factor larger than $r_B(T)$.

The family used in the proof of Theorem 18 was also related to Fibonacci words. It is noticed that prepending a symbol $b$ to the Lyndon rotation of a Fibonacci word is conjugate to the string used by Giuliani et al. [34, 35, 36] for BWT, thus giving $\mathrm{\Theta }(\log n)$ runs, while $r_B$ is easily verifiable to be $3$. An alternate (perhaps simpler) direct proof based on morphisms is also given in [5].

As for upper bounds, poly-logarithmic bounds were derived from the upper bounds $O(z(T){\log }^{2}n)$ of both $r(T)$ and $r_B(T)$ mentioned above, as well as other known bounds $z(T)=O(\delta (T)\log n)$ and $r(T),r_B(T)=\mathrm{\Omega }(\delta (T))$ [44, 45, 61].

Similar to what was observed for the lower bound, Theorem 19 implies an upper bound on the multiplicative difference between $r(T)$ and $r_B(T)$, as well.

As seen in Theorem 18, rotating the string can in some cases improve the compression performance of RLBBWT by a $\mathrm{\Theta }(\log n)$ factor. Such a rotation can be encoded as an extra integer ($\log n$ bits). Recall that in order to recover the string, BWT required extra information (an integer of $\log n$ bits¹⁶¹⁶16Here, we do not consider the case of adding an explicit terminal symbol – using an extra explicit terminal symbol outside the alphabet may increase the encoding of each symbol by $1$ bit (e.g. when $\sigma =2^k$ for some $k$), which would then require an extra $n+\log (\sigma +1)$ bits.) to specify which rotation was the original string. Since the BWT is equivalent to BBWT for a specific rotation $\mathrm{𝗆𝗂𝗇𝗋𝗈𝗍}(T)$ of $T$ (Proposition 3), it is always possible to find an encoding of a string using RLBBWT preceded by a rotation, that uses at most the space required for RLBWT (and the extra information). It is known that $\mathrm{𝗆𝗂𝗇𝗋𝗈𝗍}(T)$ can be computed in linear time [69]. Badkobeh et al. raise the question of whether the optimal rotation, i.e., can be computed in sub-quadratic time, and give partial results towards this goal [2].

Badkobeh et al. further consider a compression scheme where multiple rotations and BBWT operations can be used. They give the following conjecture for strings with the same Parikh vector, where the Parikh vector of a string $T$ is a vector of the length of the alphabet storing the frequencies of the characters in $T$.

If the conjecture is true, this implies that any string can be represented, for example, by its Parikh vector and a sequence of integers alternately representing rotations or the number of times BBWT should be applied to obtain the string.

They show that the conjecture holds for the case where the alphabet is binary, or, when each symbol occurs only once.

The theorem is proved by showing that, under the assumption of the alphabet, a string that is not the lexicographically smallest string can always be transformed, using a combination of rotations and an inverse BBWT operation, into a lexicographically smaller string. The theorem then follows from the bijectivity of rotations and BBWT.

As mentioned at the beginning of Section 5, BWT is known to have a property which tends to group characters together. Other than by entropy arguments, this so-called clustering effect has also been analyzed with respect to the run-length encoding.

The binary strings which are clustered completely by BWT have been completely characterized by Mantaci et al. [56]:

A similar result was shown for the BBWT in [12]:

In the first case, $\mathrm{𝖡𝖡𝖶𝖳}(T)={𝚊}^{\mathrm{\ell }}{𝚋}^k$, while in the second case, $\mathrm{𝖡𝖡𝖶𝖳}(T)={𝚋}^k{𝚊}^{\mathrm{\ell }}$, such that $T$ is the $m$th power of the Lyndon rotation of a standard word, where $m=\gcd (k,\mathrm{\ell })$.

Note that Fibonacci words (a subset of standard Sturmian words) have many runs: $\rho (w)=\mathrm{\Theta }(n)$. This implies that in some cases, the BWT is able to transform, with respect to run-length encoding, a least compressible string to a most compressible string. The same holds for $\mathrm{𝖡𝖡𝖶𝖳}$, again due to Proposition 3.

It is important to note that the BWT does not always make the string more compressible¹⁷¹⁷17In fact, there can exist no such lossless compression algorithm [49]., and there exist strings $T$ for which $r(T)>\rho (T)$. For example, $\mathrm{𝖡𝖶𝖳}(\mathrm{𝚊𝚊𝚋𝚋})=\mathrm{𝚋𝚊𝚋𝚊}$. However, Mantaci et al. [55] showed that $r(T)$ can never be more than twice the number of runs of $T$:

Badkobeh et al. [2] showed that the result can be further generalized for BBWT.

These results indicate that, with respect to run-length encoding, BWT and BBWT transform the string in an asymmetric way; while it is possible sometimes to make the string drastically compressible (Theorems 23 and 24), it will not make it much less compressible than it currently is (Theorems 25 and 26).

The examples of Theorems 23 and 24 are in some sense remarkable with respect to run-length encoding. However, the compressibility of the string with respect to dictionary compression does not change: the example only shows a compressible string (with respect to $r$ and $r_B$) being transformed into a compressible string.

Bannai et al. [5] analyze how BWT and BBWT change the string with respect to other repetitiveness measures. For both BWT and BBWT, it is proved that the transforms will not increase the repetitiveness measure by more than a poly-logarithmic factor.

The proof is based on the simple observation that since $𝔪(T)=O(\rho (T))$, $𝔪(\mathrm{𝖡𝖶𝖳}(T))=O(\rho (\mathrm{𝖡𝖶𝖳}(T))=O(r(T))=O(\delta (T){\log }^{2}n)=O(𝔪(T){\log }^{2}n)$. A poly-logarithmic bound for BBWT can be shown as well, with the use of Corollary 20. Thus, $𝔪(\mathrm{𝖡𝖶𝖳}(T))/𝔪(T)=O(\mathrm{𝗉𝗈𝗅𝗒𝗅𝗈𝗀}(n))$ and $𝔪(\mathrm{𝖡𝖡𝖶𝖳}(T))/𝔪(T)=O(\mathrm{𝗉𝗈𝗅𝗒𝗅𝗈𝗀}(n))$.

Furthermore, it is shown that there is an infinite family of strings such that the BBWT transforms a maximally incompressible string, with respect to any measure lower-bounded by $\delta$, to a very compressible string.

The family of strings identified is again the Fibonacci words, which are very compressible, but here used as images of BBWT, i.e., $T$ is such that $\mathrm{𝖡𝖡𝖶𝖳}(T)=F_k$ for some $k$. It is proved that the string $T$ obtained by applying the inverse BBWT to Fibonacci words are not compressible by dictionary compression. Thus, BBWT transforms strings in an asymmetric way with respect to other repetitiveness measures as well. An interesting implication of this result is that in some cases, by applying BBWT in a pre-processing step before applying a dictionary compression, it is possible to transcend any dictionary compressor. It is not yet known whether analogous strings exist for BWT; the same construction using inverse BWT does not work since Fibonacci words are not always BWT images.

The proof of Theorem 28 is based on an elegant characterization of the LF mapping (or ${\pi }_{F_k}$) on the Fibonacci word $F_k$. It utilizes a bit string representation of integers based on the fact (re)discovered¹⁸¹⁸18See https://proofwiki.org/wiki/Zeckendorf%27s_Theorem/Historical_Note. by Zeckendorf [72], that any integer can be uniquely represented as the sum of a set of distinct and non-consecutive Fibonacci numbers. It is shown that if a position $i$ in $F_k$ is represented as a $k$-bit string $s_i$ based on the Zeckendorf representation (for $j\in [0,k)$, the $j$th bit is 1, if and only if the $(j+1)$st Fibonacci number is used), the bit-string corresponding to the position ${\pi }_{F_k}(i)$ is a rotation of $s_i$. This implies that each conjugacy class of $k$-bit strings for positions in $[0,|F_k|)$ correspond to a cycle in the standard permutation ${\pi }_{F_k}$ of $F_k$. Then, by showing that the length of cyclic strings corresponding to the cycles of ${\pi }_{F_k}$ can be bounded by $k$, and, when $k$ is prime, that the Lyndon rotation of each of the strings occur uniquely in $T$, it follows that $\delta (T)\ge (|F_k|-2k+1)/2k=\mathrm{\Omega }(n/\log n)$.