Burrows-Wheeler Transform

BWT: Reordering Without Data Loss

Huffman coding uses symbol frequencies, while methods from the Lempel-Ziv family refer to repeated strings. Both preserve data but target different forms of redundancy. The Burrows-Wheeler Transform orders a block by character context and prepares it for later statistical coding.

The Burrows-Wheeler Transform (BWT) orders block rotations by lexicographical position. Described by Michael Burrows and David Wheeler in 1994, BWT does not reduce the data size. It is a reversible permutation of a block that groups characters with similar contexts. The result can then be processed by RLE, MTF, and entropy coding. BWT is one stage of the bzip2 archiver; its documentation reports generally better results than conventional LZ compressors, while the ratio still depends on the data. Sorting an entire block increases computation and memory use, so practical formats divide input into bounded blocks.

The BWT Transform: Rotations, Sorting, and Output

BWT operates on an entire block rather than encoding one byte at a time. Let us transform "ANANAS$". The character '$' marks the end of the string and is lexicographically smaller than the other characters, giving each rotation an unambiguous position.

Step 1: Create All Cyclic Rotations

First, create every cyclic shift of the input string. Each next shift moves the first character to the end.

Step 2: Sort the Rotations Lexicographically

Next, sort the rotations lexicographically. Lexicographical sorting compares characters from left to right in dictionary order. An implementation need not materialize the entire matrix, since rotations can be represented by indexes or a suffix array.

Step 3: Extract the Output, the Last Column

The BWT output is the sequence of characters in the last column of the sorted table. We denote this column by $L$.

L = S$NNAAA

The string "ANANAS$" produces "S$NNAAA". The three 'A' characters form a run that RLE can encode efficiently. Grouping contexts is the purpose of applying BWT before the coding stages.

Step 4: Record the Primary Index

To reverse the transform, store the row containing the original string. In this example, "ANANAS$" is in row 1, so the primary index $I$ is 1.

The complete forward Burrows-Wheeler output for "ANANAS$" is the pair ("S$NNAAA", $1$).

For comparison, a block without an explicit terminator can contain "BANANA". Its rotations sort as "ABANAN", "ANABAN", "ANANAB", "BANANA", "NABANA", "NANABA". The output is $L =$ "NNBAAA", with primary index $I = 3$.

The Inverse BWT Transform: Reconstructing the Input

The inverse process needs only the last column and the primary index. It relies on a property connecting the first and last columns of the sorted matrix.

The Last-to-First (LF) Mapping Property

In the sorted matrix, call the first column $F$ and the last column $L$.

$F$ is the sorted version of the input characters ($,A,A,A,N,N,S). We can reconstruct it by sorting the characters of $L$.

The property that makes BWT reversible is the Last-to-First (LF) Mapping:

The mapping moves from a character in $L$ to its corresponding position in $F$. Because each character in $F$ begins a sorted rotation, repeated moves reconstruct the input backwards. The occurrence number matters because repeated letters occupy different rows. Stable numbering of occurrences identifies one LF edge for each row.

Inverse Transformation Steps

Reconstruct "ANANAS$" from $L =$ "S$NNAAA" and $I = 1$.

1. Step 1: Reconstruct First Column (F): Sort the characters of $L$. Sorting "S$NNAAA" gives $F =$"$AAANNS".
2. Step 2: Start with the Primary Index: The index $I=1$ identifies the row of the original rotation. In $L = (S_0, \$_1, N_2, N_3, A_4, A_5, A_6)$, $L[1]$ is '$'. The character at $L[1]$ is the final character of the input.
3. Step 3: Apply the LF-Mapping: The '$' at L[1] is the first '$' in $L$. It corresponds to the first '$' in $F = (\$_0, A_1, A_2, A_3, N_4, N_5, S_6)$, at index 0. The next row is row 0.
4. Step 4: Walk Backwards, Iteration 2: Go to row 0. The character in $L[0]$ is 'S', the preceding character. So far, read from the end, we have S$.
5. Step 5: Repeat LF-Mapping: The 'S' at $L[0]$ is the first 'S' in $L$. It corresponds to the first 'S' in $F$, at index 6. The next row is 6.
6. Step 6: Continue Iterating:
   • $i = 1$. Take L[1] = '$'. The first '$' in L maps to index 0 in F. New $i = 0$. Reconstructed suffix: $.
   • $i = 0$. Take L[0] = 'S'. The first 'S' in L maps to index 6 in F. New $i = 6$. Reconstructed suffix: S$.
   • $i = 6$. Take L[6] = 'A'. The third 'A' in L maps to index 3 in F. New $i = 3$. Reconstructed suffix: AS$.
   • $i = 3$. Take L[3] = 'N'. The second 'N' in L maps to index 5 in F. New $i = 5$. Reconstructed suffix: NAS$.
   • $i = 5$. Take L[5] = 'A'. The second 'A' in L maps to index 2 in F. New $i = 2$. Reconstructed suffix: ANAS$.
   • $i = 2$. Take L[2] = 'N'. The first 'N' in L maps to index 4 in F. New $i = 4$. Reconstructed suffix: NANAS$.
   • $i = 4$. Take L[4] = 'A'. The first 'A' in L maps to index 1 in F. New $i = 1$. Reconstructed string: ANANAS$.

bzip2 Pipeline Stages After BWT

BWT prepares a block for later transformations. The bzip2 format also has an initial RLE stage, followed by BWT, MTF, another RLE stage, and Huffman coding.

• Stage 1: RLE and Burrows-Wheeler Transform (BWT): The bzip2 format applies an initial RLE stage, then processes data in blocks to group characters with similar contexts and produce the L column and an index.
• Stage 2: Move-to-Front (MTF) Transform: The output of the BWT, which now has long runs of identical characters, is processed by the MTF transform. MTF maintains a list of the alphabet. For each character it processes, it outputs the character's current position in the list and then moves that character to the front of the list. The result is a stream of small numbers (mostly 0s, 1s, and 2s), which is even more statistically redundant.
• Stage 3: Run-Length Encoding (RLE): The stream from MTF is processed by another RLE stage, including to shorten runs of zeros.
• Stage 4: Entropy Coding: In bzip2, the final stream of symbols from the RLE stage is compressed using Huffman coding. Other BWT pipelines may use arithmetic coding at this stage.

In practice, MTF records a character position in the current alphabet list and moves that character to the front. BWT often produces small positions, especially zeros, so RLE can describe their runs with fewer symbols. Huffman then assigns codes according to frequency. Each stage has a separate role and can be reversed during decompression in the opposite order. The primary index is stored with the input block and selects the original rotation.

Role of BWT

BWT is a reversible permutation that uses character context to prepare a block for RLE, MTF, and entropy coding. Sorting increases computation and requires the whole block. The resulting compression depends on the data and on the later pipeline, so BWT itself is not a measure of size reduction. The same rotation order can support text indexes, while bzip2 uses it primarily as a data-preparation stage.