The Burrows-Wheeler transform

The Burrows-Wheeler transform

Juan Francisco Rodríguez Herrera
Vicente González Ruiz

September 12, 2016

Contents

1 The forward transform
2 The inverse transform

Intro

The BWT (Burrows-Wheeler Transform) is an algorithm that inputs a string and outputs:
1. A diﬀerent string with the same symbols, but with a diﬀerent order.
2. An index.
This is the forward transform.
There is an inverse transform that, using the output of the forward transform, recover the original string.
The transformed string tends to have longer runs.
The length of the runs in proportional to the correlation between the symbols and the length of the input.

1 The forward transform

Let $B$ the block-size in symbols:

Read $B$ symbols.
Build a square matrix of size $B \times B$ where the ﬁrst row is the original sequence, the second one is the same sequence but cyclically shifted one symbol to the left, and so on ...
Sort lexicographically the matrix by rows.
Search in the last column the row in which the ﬁrst symbol of the original sequence it is found. This is the index $i$ .
Output $i$ and the last column $O []$ .

Encoding example

Initial matrix

Sorted matrix



$<$ a $>$ babcbababaaaaaaa	0
babcbababaaaaaaa $<$ a $>$	1
abcbababaaaaaaa $<$ a $>$ b	2
bcbababaaaaaaa $<$ a $>$ ba	3
cbababaaaaaaa $<$ a $>$ bab	4
bababaaaaaaa $<$ a $>$ babc	5
ababaaaaaaa $<$ a $>$ babcb	6
babaaaaaaa $<$ a $>$ babcba	7
abaaaaaaa $<$ a $>$ babcbab	8
baaaaaaa $<$ a $>$ babcbaba	9
aaaaaaa $<$ a $>$ babcbabab	10
aaaaaa $<$ a $>$ babcbababa	11
aaaaa $<$ a $>$ babcbababaa	12
aaaa $<$ a $>$ babcbababaaa	13
aaa $<$ a $>$ babcbababaaaa	14
aa $<$ a $>$ babcbababaaaaa	15
a $<$ a $>$ babcbababaaaaaa	16



aaaaaaa $<$ a $>$ babcbabab	10	0
aaaaaa $<$ a $>$ babcbababa	11	1
aaaaa $<$ a $>$ babcbababaa	12	2
aaaa $<$ a $>$ babcbababaaa	13	3
aaa $<$ a $>$ babcbababaaaa	14	4
aa $<$ a $>$ babcbababaaaaa	15	5
a $<$ a $>$ babcbababaaaaaa	16	6
abaaaaaaa $<$ a $>$ babcbab	8	7
ababaaaaaaa $<$ a $>$ babcb	6	8
$<$ a $>$ babcbababaaaaaaa	0	9
abcbababaaaaaaa $<$ a $>$ b	2	10
baaaaaaa $<$ a $>$ babcbaba	9	11
babaaaaaaa $<$ a $>$ babcba	7	12
bababaaaaaaa $<$ a $>$ babc	5	13
babcbababaaaaaaa $<$ a $>$	1	14	$\leftarrow i$
bcbababaaaaaaa $<$ a $>$ ba	3	15
cbababaaaaaaa $<$ a $>$ bab	4	16

2 The inverse transform

Sort $O []$ over $S []$ .
Compute $T []$ where if $S [j] = O [l]$ (being $l$ the ﬁrst symbol of $O []$ that matches this condition), then $T [j] = l$ . Notice that all of symbols of $T []$ have to be diﬀerent.
Let $k \leftarrow i$ .
Execute B times:
1. Output $O [k]$ .
2. $k \leftarrow T [k]$ .

Decoding example

$O [] =$ baaaaaabbabaacaab and $i = 14$ .
$O [] =$ 01234567890123456
$O [] =$ 00000000001111111
$S [] =$ aaaaaaaaaaabbbbbc (we sort).
$S [] =$ 12345691245078063
$S [] =$ 00000001111000111
Compute T[].
- $S [0] = a$ is in $O [1]$ , therefore, $T [0] = 1$ .
- $S [1] = a$ is in $O [2]$ , therefore, $T [1] = 2$ .
- $⋮$
$T [] = {$ 1,2,3,4,5,6,9,11,12,14,15,0,7,8,10,16,13 $}$
$T [] = {$ 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6
$T [] = {$ 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
$k \leftarrow 14$ .
Execute 17 times:
- Output $O [14] = a$
- $k \leftarrow 10$ .
- Output $O [10] = b$ .
- $k \leftarrow 15$ .
- Output $O [15] = a$ .
- $k \leftarrow 16$
- $⋮$
Finally, the initial sequence of symbols is reconstructed.

Let’s go to the lab!

Download http://www.ace.ual.es/~vruiz/doctorado/text-compression.tar.gz, make bwt and make unbwt.
Encode each image of the Test Image Corpus using the BWT and RLE codecs (pipe both codecs writing rle < raw-file | bwt > encoded-file). Continue ﬁlling the table:
    Codec | lena boats pepers zelda Average
----------+--------------------------------
      rle | ....  ....   ....  ....    ....
bwt + rle | ....  ....   ....  ....    ....
Better results?
Verify that the encoding/decoding is lossless!