Burrows-Wheeler Transform + Move-to-Front (bzip2 stack)

DEFLATE (gzip) is LZ77 + Huffman. bzip2 takes a completely different route: BWT + MTF + RLE + Huffman. It typically beats gzip by 10–25%, at the cost of much slower (and non-streaming) encoding.

The Burrows-Wheeler Transform

BWT is a reversible permutation of the input. It doesn't compress on its own — but it produces a string with long runs of identical characters that subsequent compressors crush.

The algorithm:

1. Form all N rotations of the input string (think of it as a circle).
2. Sort the rotations lexicographically.
3. Output the LAST COLUMN, plus the row index of the original string.

Example with "banana":

Rotations         Sorted              Last col
banana            anana b              a
ananab            anab an              n
nanaba            ba nan a             a
anaban            banan a              a
nabana            nab ana              n     <- primary index here
abanan            nana ba              b

The last column is annnbaa... wait, let me do it properly: sorted gives [anana b, ana ban, a nanab, banana, na bana, nanab a]. The last column = n n b a a a. That's our BWT output.

Key insight: characters that precede the same context appear adjacent in the sorted rotations. In natural text, 'h' is followed by 'e', 'a', 'i', 'o' constantly — so the last column has long runs of those letters clumped together.

Inverse BWT

Surprisingly elegant. Given the last column and the primary index, you can reconstruct the input in O(N) without storing the full rotations matrix. The trick is that the first column is just the last column sorted.

Move-to-Front

BWT gives us clustered runs. MTF turns clusters of any byte into small integers:

table = [0, 1, ..., 255]
for byte b in input:
    output table.index(b)
    move b to position 0

A burst of identical bytes becomes [byte, 0, 0, 0, ...]. A burst of two alternating bytes becomes [b1, b2, 1, 1, 1, ...]. After MTF, the distribution is heavily skewed toward small numbers — perfect input for Huffman (or, in bzip2's case, RLE-then-Huffman).

The full bzip2 pipeline

input -> RLE-1 (cap long runs) -> BWT -> MTF -> RLE-2 (zeros) -> Huffman

Why bzip2 still loses to zstd

bzip2 is non-streaming (BWT needs the whole block) and slow. zstd (LZ77 + tANS) is streaming and faster, and modern dictionaries close most of the ratio gap. But for purely text-shaped sources, BWT is still surprisingly competitive — see xz (LZMA) and bsc for related approaches.

Implementation walkthrough

BWT encode

BWT inverse (the elegant trick)

The first column of the sorted matrix is just the LAST column re-sorted. Pairing positions in the two columns gives a permutation you can walk to reconstruct the original.

MTF

A run of identical bytes becomes [byte_value, 0, 0, 0, ...]. A short alphabet stays in the front of the table — small indices dominate.

Common pitfall

Sorting full rotation strings is O(N² log N) and uses O(N²) memory. Real bzip2 uses suffix-array sorting in O(N log N) time and O(N) memory. For a tutorial implementation O(N² log N) is fine on small inputs — but expect it to crawl past a few KB.