The Bijective Burrows-Wheeler Transform (BBWT) is a variant of the famous BWT [Burrows and Wheeler, 1994]. The BBWT was introduced by Gil and Scott in 2012, and is based on the extended BWT of Mantaci et al. [TCS 2007] and on the Lyndon factorization of the input string. In the original paper, the compression achieved with the BBWT was shown to be competitive with that of the BWT, and it has been gaining interest in recent years. In this work, we present the first study of the number of runs of the BBWT, which is a measure of its compression power. We exhibit an infinite family of strings on which of the string and of its reverse difer by a multiplicative factor of Θ(log ), where is the length of the string. We also present experimental results and statistics on () and (rev), as well as on the number of Lyndon factors in the Lyndon factorization of and rev.
inally introduced in 1994 by Michael Burrows and David J. Wheeler as a preprocessing step
for string compression. The BWT tends to be easier to compress than the original input and
supports eficient pattern matching tasks while keeping the transform in compressed form. Due
to this, this transform has become the cornerstone of several string compressors and compressed
† Funded by the European Union (ERC, REGINDEX, 101039208). Views and opinions expressed are however those of
the author(s) only and do not necessarily reflect those of the European Union or the European Research Council.
Neither the European Union nor the granting authority can be held responsible for them.
data structures [
These properties are due to the so-called clustering efect of the BWT. In fact, if the input
text is highly repetitive, the final transform will tend to include few long runs of the same
character, the number of which is usually denoted . This motivated the interest for as a
parameter to measure text repetitiveness, with several recent papers studying the suitability of
as a repetitiveness measure as well as how is related to other such measures [
tion, which is a variation of the BWT. It is defined as the extended BWT (eBWT) [
This transformation has met increasing interest in the last decade, with several papers
published on this topic. Recently Bannai et al. in [
In the original BBWT paper [
behaviour of of a string and of its reverse. We define an infinite family of words for which
of the string and its reverse difer by a multiplicative factor of Θ(log ), where is the length
of the string, thus proving a parallel result on the BBWT to that of Giuliani et al. [
the BWT, namely that reversing the string may change it significantly, while repetitiveness is,
of course, preserved. The family of strings used in this paper derive from finite Fibonacci words,
as do those of [
tive and additive diference between a string and its reverse, as well as the relationship to the number of factors of its Lyndon factorization.
= 1 · · · of characters from Σ. We denote the length of string as ||. The empty string is the only string of length 0 and is denoted . For ≥ 0, Σ denotes the set of all words of length , and Σ* = ∪≥ 0Σ the set of all finite words over Σ.
Let , , , ∈ Σ* such that = . Then is called a prefix , a substring, and a sufix of . A string is a subsequence of if can be obtained from by deleting some (possibly 0, possibly all) characters from . A prefix (sufix, substring) of a word is a called proper if ̸= . For a string and an integer ≥ 1, = · · · · denotes the -fold concatenation of . A string is called primitive if = implies = and = 1. If is not primitive then it is called a power. Every word can be uniquely written as = for a primitive string , called root of . Given a string , we also define the infinite word = · · · · · We denote the number of maximal equal-letter runs of a string by runs().
or if there exists ∈ Σ* and , ∈ Σ, < such that is a prefix of and is a prefix of . Another order relation on Σ* is the omega-order defined as follows: Let = and = ℓ, , primitive. Then < if = and < ℓ, or else if <lex . Note that the lexicographic and the omega-order coincide on strings of the same length, but they can difer if one is a proper prefix of the other, e.g. ab <lex aba but aba < ab.
s.t. = and ′ = . Conjugacy is an equivalence relation. We denote the conjugacy class of a word ∈ Σ, as [] = { | and are conjugates}. A word is primitive if and only if its conjugacy class has cardinality ||.
of its rotations. A necklace is a Lyndon word or a power of a Lyndon word. For a primitive word , we denote by () the unique conjugate which is a Lyndon word (its Lyndon rotation). Every string can be uniquely written as = 1 · 2 · · · such that are Lyndon words for = 1, . . . , , and 1 ≥ 2 ≥ . . . ≥ [20]. This is called ’s Lyndon factorization. A string is Lyndon if and only if its Lyndon factorization consists of one factor only. The multiset of Lyndon factors in the Lyndon factorization of is denoted ℒ().
, whose th character is the last character of the th rotation of , where the rotations are taken w.r.t. lexicographic order. For example, BWT(banana) = nnbaaa, see Fig. 1. The number of runs of the BWT is denoted () = runs(BWT()), e.g. (banana) = 3.
ℳ: eBWT(ℳ) is a permutation of the characters of the strings in ℳ, whose th character is the last character of the th rotation, where the rotations of all strings in ℳ are listed w.r.t. omega-order. For an example, see Fig. 2. Note that for all strings , eBWT({}) = BWT().
Lemma 1
1. Let ∈ . Then BWT() is a subsequence of eBWT(). 2. Let be a multiset of primitive strings, and ′ a conjugate of some ∈ . Then the number of runs of eBWT( ∪ {′}) equals the number of runs of eBWT(). 3. Given an integer > 0 and a primitive word , let be the multiset consisting of copies of . Then BWT() = eBWT().
Let = 1 · 2 · · · be the Lyndon factorization of string . Then BBWT() = eBWT(ℳ), where ℳ = ℒ() = {1, 2, . . . , } is the multiset of Lyndon factors of . As an example, BWT(banana) = nnbaaa, while BBWT(banana) = annbaa, since the Lyndon factorization of banana is b · an · an · a, and thus ℒ(banana) = {a, an, an, b}, see Fig. 1. sorted rotations BWT abanan n anaban n ananab b banana a nabana a nanaba a
Proof First assume that BWT() = BBWT() holds. Let = , where is primitive and ≥ 1, and let be the conjugate of which is a necklace. Then clearly, = with = (), and ℒ() consists of copies of . Thus:
BBWT() d=ef. eBWT(ℒ()) Lem=ma 1 BWT() , conj. BWT() = BBWT().
= By bijectivity of the BBWT, this implies that equals its own necklace rotation , and is thus a necklace.
Conversely, if = is a necklace, then ℒ() consists of copies of , and BBWT() = eBWT(ℒ()) = BWT(), again by Lemma 1. □
Let us denote by () = runs(BBWT()), the number of runs of the BBWT of . It is known that the number of runs () of the BWT of a binary string is always even. This is because necessarily the first character must be b, and the last character must be a. This is not the case of the BBWT since a and b are the smallest and the greatest Lyndon factor, respectively, that a binary word can have, and therefore, BBWT may start and end with either a or b. In the next lemma, we give the conditions that a or b appear as a Lyndon factor.
Lemma 3 Let ∈ {a, b}* be a binary string, with a < b. Then, a ∈ ℒ() if and only if a is the last letter of . Symmetrically, b ∈ ℒ() if and only if b is the first letter of . Proof We prove just the first statement on a, and the other case is treated symmetrically. For the first direction, observe that a is the smallest Lyndon factor (both in lexicographical and order) that any binary word can have. Since the Lyndon factorization requires that any Lyndon factor must be greater or equal than the following in (if any), a ∈ ℒ() implies that either the next letter in is another a, or there are no more letters in . For the other direction, suppose by contradiction that ends with an a and a ∈/ ℒ(). Then, there exist ℓ ≥ 0, ≥ 1, ∈ {a, b}* such that the word = aℓba ∈ ℒ(), that is the Lyndon factor containing the last a of . However, one can verify that aℓ+1b < aℓba, which contradicts that is a Lyndon word. □
Lemma 4 Let ∈ {a, b}* be a binary word. It holds that () is odd if and only if starts and ends with the same letter.
However, it turns out that there is a simple connection between () and (rev), namely that they must have the same parity: Lemma 5 For every binary string , the diference between the number of runs of the BBWT of and the BBWT of its reverse is even.
Proof If starts and ends with the same character, then so does rev, and by Lemma 4, both have an odd number of runs. If starts and ends with diferent characters, then so does rev, and by Lemma 4, both have an even number of runs. □
The BWT of a word achieves maximal compression when it has as many runs as the size of the alphabet. In case of binary alphabets, it was shown in [21] that the perfect clustering efect of the BWT is a characterization for the family of standard Sturmian words. These words can be constructed through a directive sequence, an infinite sequence of integers {}≥ 0 such that 0 ≥ 0 and > 0 for all > 0. The standard Sturmian words generated by this sequence are the words of the sequence {}≥ 0 such that 0 = b, 1 = a, and +1 = − 1 − 1 for > 1. For instance, the directive sequence 1, 1, 1, 1, . . . generates the well-known sequence of ifnite Fibonacci words : 0 = b, 1 = a, 2 = ab, 3 = aba, 4 = abaab, 5 = abaababa, 6 = abaababaabaab, 7 = abaababaabaababaababa, . . .
Theorem 1 ([21]) BWT() = baℓ, for some , ℓ ≥ 1, if and only if is the power of a rotation of a standard Sturmian word.
necessary that the transform begins with b and ends with a.
Lemma 6 The number of runs of the BBWT of a string is 2 if and only if (i) has the form baℓ for some , ℓ ≥ 1, or (ii) is the Lyndon rotation of a standard Sturmian word or a power of the Lyndon rotation of a standard Sturmian word. diference of as () = () − (rev).
In the rest of the paper, we will look at the relationship between () and (rev). To this end, we define the runs-ratio of string as () = max( ((re)v) , ((re)v) ), and the runs
following interesting property: the number of runs of the BBWT of its reverse has 2( − 2) runs, while the BBWT of the word itself has only 2 runs. Thus, of these words is Θ(log ), where is the length of the word.
tion that for all ≥ 0, || = , where {}≥ 0 is the well-known Fibonacci sequence
Proposition 1 (Some known properties of the Fibonacci words) Let be the Fibonacci word of order ≥ 0. Then there exists a palindrome with the following properties: 1. for all ≥ 2: if is even, then = ab, and if is odd, then = ba, where is a palindrome (in particular, 2 = ). 2. for all ≥ 4, 3. for all ≥ 2, ab is a Lyndon word. 4. for all : ()rev is a conjugate of .
• if is even, then = − 1ba− 2ab = − 2ab− 1ab, and • if is odd, then = − 1ab− 2ba = − 2ba− 1ba. 5. for ≥ 2: BWT() has two runs; in particular, BWT() = b− 2 a− 1 . 6. for ≥ 2: ab and ba, the so-called central words, are adjacent in the BW-matrix of .
Corollary 1 Let be the palindrome from Prop. 1, i.e. = ab for even, and = ba for odd. Then 1. () = ab, 2. = − 1ba− 2 = − 2ab− 1, if even, 3. = − 1ab− 2 = − 2ba− 1, if odd.
here: (0) = b, (1) = a, (2) = ab, (3) = aab, (4) = aabab, (5) = aabaabab.
word . We will show that it consists of the Lyndon rotations of for = 0, . . . , − 2, where the words of even order are listed increasingly (w.r.t. their order), followed by those of odd order listed decreasingly, followed by one additional factor (1) = a. Formally: Lemma 7 Let = ()rev be the reverse of the Lyndon rotation of the Fibonacci word of order . Then the Lyndon factorization of is as follows: 1. = (0) · (2) · (4) · · · (− 2) · (− 3) · (− 5) · · · (3) · (1) · (1) if is even, and 2. = (0) · (2) · (4) · · · (− 3) · (− 2) · (− 4) · · · (3) · (1) · (1) if is odd.
Example 1 In the following we list with its Lyndon factorization, for = 2, . . . , 8 : • 2 = (2)rev = b · a, • 3 = (3)rev = b · a · a, • 4 = (4)rev = b · ab · a · a, • 5 = (5)rev = b · ab · aab · a · a, • 6 = (6)rev = b · ab · aabab · aab · a · a, • 7 = (7)rev = b · ab · aabab · aabaabab · aab · a · a, • 8 = (8)rev = b · ab · aabab · aabaababaabab · aabaabab · aab · a · a.
recursion for : Lemma 8 Let = (())rev. Then the following recursion holds for ≥ 2 : • = − 2− 1 if is even, and • = − 1− 2 if is odd.
Proof First note that since () = ab, and is a palindrome, therefore = ba. Let ≥ 2 be even. By Corollary 1, = ba = b− 2ab− 1a = − 2− 1. Similarly, if is odd, then = ba = − 1ab− 2 = − 1− 2. □
Lemma 9 Let ≥ 4. Then the following holds: • () = (− 3)(− 5) · · · (3)(1)(1)(0)(2)(4) · · · (− 2), if is even, and • () = (− 2)(− 4) · · · (3)(1)(1)(0)(2)(4) · · · (− 3), if is odd.
Proof (of Lemma 7) The proof is by induction on . For the base cases, 2 = b · a, and 3 = b · a · a, as claimed. Now let > 3. If is even, then = − 2− 1 = b− 2ab− 1a. Thus, = (0)(2) · · · (− 4)(− 5) · · · (3)(1)(1) · ⏟ − 2 by⏞the I.H.
(0)(2) · · · (− 4)(− 3) · · · (3)(1)(1) ⏟ − 1 by⏞the I.H. = (0)(2) · · · (− 4)· (− 5) · · · (3)(1)(1)(0)(2) · · · (− 4) · ⏟ (− 2) b⏞y Lemma 9 (− 3) · · · (3)(1)(1) = (0) · (2) · (4) · · · (− 2) · (− 3) · (− 5) · · · (3) · (1) · (1). The claim for odd follows analogously. □ Example 2 For example, 8 = 6 · 7 = babaababaabaa · babaababaabaababaabaa = b · ab · aabab · aabaababaabab · aabaabab · aab · a · a, where the new Lyndon factor is underlined; its factorization from Lemma 9 is (6) = aabaababaabab = aab · a · a · b · ab · aabab. Corollary 2 (from Lemma 7) Let be the reverse of the Lyndon rotation of the Fibonacci word of order . Then ℒ() = {(0), (1), (2), . . . , (− 2)} ∪{(1)}, i.e. the factor (1) = a appears with multiplicity 2 in the factorization, while all other factors appear exactly once.
gives the number of runs of the eBWT of the set of Fibonacci words = {0, 1, . . . , }. A crucial role will be played by the central words, which we list up to order 7 in Table 1. Lemma 10 Let > 0 and be the set of Fibonacci words of order up to , i.e. = {0, 1, . . . , }. Then eBWT() has 2 runs.
Proof We prove the claim by induction on . For = 1, 2, eBWT({a, b}) = ab, which has 2 runs, and eBWT({a, b, ab}) = abab, which has 4 runs, as claimed.
Now let > 2. We will observe what happens to eBWT(− 1) when we insert into − 1 and will show that exactly 2 new runs are created, see Fig. 2.
Let eBWT(− 1) be given, and consider what happens when we add . Denote the two central words of order as = ab and = ba. Note that = if is even, and = if is odd. Clearly, < for all . Moreover, it can be proven that for > 2, the following relationship holds between central words of subsequent order: > − 1 if is even, and < − 1 if is odd.
Now, when considering eBWT(− 1), the two words and are inserted together, i.e. they are adjacent in the eBWT-matrix of . This is because they have the common prefix , of length || − 2, which, for > 3, is longer than the longest word previously present (of length |− 1| = − 1 < − 2); for = 3 the claim can be seen by direct inspection (see Fig. 2, left).
Moreover, the two central words will be inserted immediately adjacent to one of the two central words of order − 1. This is because one of the two central words is always equal to ( for even, for odd), and thus, − 1 is a proper prefix of or − 1 is a proper prefix of , and no longer prefix of these words can be present. Thus we have = > − 1 = − 1 if is even, and = < − 1 = − 1 if is odd. Therefore, and will be inserted immediately after − 1 = − 1 if is even, and immediately before − 1 = − 1 if is odd. It follows by induction that − 1 was inserted immediately after (immediately before) − 2 if is even (if is odd). This in turn implies that the word just before (just after) and is − 2, for even (for odd).
Now consider the number of runs of eBWT(− 1). By the induction hypothesis, eBWT(− 1) has 2 − 2 runs. Inserting the two central words creates two new runs. This is because they end in b and a, in this order, and they are inserted between the two previous Fibonacci words: if is even, then they are inserted between − 1, which ends in a, and − 2, which ends in b; if is odd, then between − 2, which ends in a, and − 1, which ends in b.
Note that, since is a standard word, BWT() has the form baℓ, and by Lemma 1, this will be a subsequence of eBWT(). This implies that, if the two central words of order are inserted between, say, position and position + 1 of eBWT(− 1), then all rotations of ending in b will be inserted before , and all rotations ending in a will be inserted after + 1. Inserting a b will create a new run only if it is inserted between two a’s; likewise, inserting an a will create a new run only if it is inserted between two b’s. It is not dificult to prove (by induction) that all a-runs before the position of − 1 have length 1, and that all b-runs after the position of − 1 have length 1.
Thus, exactly two new runs are created. This completes the proof. □ Theorem 2 Let = () be the Lyndon rotation of the th Fibonacci word . Then () = Θ(log ||).
Proof First note that since is a Lyndon word, BBWT() = BWT() by Lemma 2. Since it is a rotation of , BWT() = BWT(). By Prop. 1, BWT() has two runs, so BBWT() has two runs, thus, () = 2.
Now let = ()rev. By Corollary 2, the set of Lyndon factors of is − 2 = {0, . . . , − 2}. It follows from Lemma 1 that the number of runs of a multiset depends only on the set of the elements (and not on the multiplicity of each element). By Lemma 10, the number of runs of eBWT(− 2) is 2( − 2), and therefore, () = 2( − 2).
Finally, using the fact that || = || = grows exponentially in , it follows that () = 2(2− 2) = Θ() = Θ(log ||). □
multiplicative ( ) and additive diference ( ). We also studied the number of Lyndon factors in the Lyndon factorization of . We considered only those strings which are lexicographically strictly smaller than their reverse. We refer to such strings also as forward strings , as opposed to strings which are strictly larger than their reverse: we refer to these as reverse strings. This is to avoid repeating the same experiment twice (as we compare of a string and of its reverse).
alphabet. We also ran the same experiment over a ternary alphabet, for strings of length up to 15 (data not shown). 5.1. Multiplicative diference in
of a string and its reverse In the first step of our analysis, () was calculated for each forward string . We report the maximum for each length over a binary alphabet in Table 2 1. Our results show that 1The statistics reported in the summary do not include palindrome sequences since their () is always 1. The number of palindromes of length is 2⌈/2⌉. increasing the sequence length , the average runs-ratio as the proportion of sequence pairs having () = 1 decreases. On the other hand, large sequence lengths generate large maximum () values. This suggests that by increasing , we observe more sequences for which the () is very close to 1 and only a small subset for which () is very diferent from (rev), i.e., we observe extremal words with larger () values. In addition, for every up to 21, the most frequent value of () is 1, i.e. probability that () = (rev) is high (see Fig. 3 for = 21).
As for the extremal words, we noticed that several of them are Lyndon rotations of standard words (data not shown). In fact, these strings always have () = 2, and thus they tend to generate large (). In particular, for () ≥ 4 and ≤ 23, all extremal cases are Lyndon rotations of standard words. However, no precise pattern is visible since also non-standard words can be extremal words. On the other hand, if we consider the smallest values, which present an increase in (), for () ≥ 3, the extremal words are the Lyndon rotation of the Fibonacci word of length and its reverse complement. For instance, = 8 is the smallest which allows to obtain () = 3, and the two extremal cases are aabaabab and ababbabb. As for () ≤ 2, the situation appears more complex, since there are several extremal cases that reach the same runs-ratio. 5.2. Number of Lyndon factors and
in relation to (). In Fig. 4 we note that there are no strings with both a high number of
(a) and reverse (b) are empty. The two plots are quite similar, with the exception of the number of Lyndon factors that appear to be higher in reverse strings (see also Fig. 3). In addition, the -axis for forward and reverse is the same, indicating that values of span the same range on both forward and reverse strings.
is always lexicographically strictly smaller than its reverse, if rev has a run of b at the beginning and a run of a at the end the resulting Lyndon factorization will contain several length-one
eight length-one Lyndon factors: b · b · b · b · ab · ab · aababb · a · a · a · a. However, also in this case, no clear pattern arose from our experiments. In fact, there are cases where the Lyndon factorization of leads to () which is much smaller than (rev).
are found on the vertical line indicating 0 as the diference in the number of runs, and the two measures analysed do not seem to strongly correlate. Results were inconclusive also when performing the same analysis counting only distinct Lyndon factors. Further details on the experimental results will be given in the full version of the paper. survey of string orderings and their application to the Burrows-Wheeler transform, Theor.
Comput. Sci. 710 (2018) 52–65. [19] E. Biagi, On comparing the Bijective Burrows-Wheeler-Transform of a word and its reverse,
[20] K. T. Chen, R. H. Fox, R. Lyndon, Free diferential calculus, iv. the quotient groups of the lower central series, Annals of Mathematics 68 (1958) 81. [21] S. Mantaci, A. Restivo, M. Sciortino, Burrows-Wheeler transform and Sturmian words, Inf.
Process. Lett. 86 (2003) 241–246. [22] A. de Luca, A combinatorial property of the Fibonacci words, Inf. Process. Lett. 12 (1981) 193–195. [23] A. de Luca, F. Mignosi, Some combinatorial properties of Sturmian words, Theor. Comput.
Sci. 136 (1994) 361–285. [24] A. de Luca, Sturmian words: Structure, combinatorics, and their arithmetics, Theor.
Comput. Sci. 183 (1997) 45–82. [25] J. Berstel, A. de Luca, Sturmian words, Lyndon words and trees, Theor. Comp. Sci. 178 (1997) 171–203. [26] J. Borel, C. Reutenauer, On Christofel classes, RAIRO Theor. Inf. Appl. 40 (2006) 15–27.