Burrows-Wheeler Transform — Reversible Rearrangement for Compression

bzip2 regularly outcompresses gzip by 10-30% on text data. The reason is the Burrows-Wheeler Transform — a reversible rearrangement that clusters similar contexts together, making subsequent compression dramatically more effective. Michael Burrows and David Wheeler published it in 1994 as a DEC Systems Research Center technical report, and it became the core of bzip2.

The BWT also has a second life in bioinformatics. The FM-index — a compressed data structure built on BWT — allows searching a 3-billion-base genome for any short read in milliseconds while using only 1-2 GB of RAM. The entire field of short-read genome alignment (BWA, Bowtie2, HISAT2 — the tools that process most DNA sequencing data) is built on Burrows-Wheeler.

Forward BWT

1. Form all rotations of the string (append a unique end-of-string marker $)
2. Sort all rotations lexicographically
3. Output the last column (L) of the sorted matrix and the row index of the original string

def bwt(s: str) -> tuple[str, int]:
    """Compute BWT of s. Returns (transformed, original_row_index)."""
    s = s + '$'  # append end marker (lexicographically smallest)
    n = len(s)
    rotations = sorted(s[i:] + s[:i] for i in range(n))
    last_col = ''.join(r[-1] for r in rotations)
    original_idx = rotations.index(s)
    return last_col, original_idx

result, idx = bwt('banana')
print(f'BWT(banana) = {result!r}, original row = {idx}')
result2, idx2 = bwt('mississippi')
print(f'BWT(mississippi) = {result2!r}, original row = {idx2}')

Why BWT Helps Compression

Notice BWT(banana) = 'annb$aa' — the 'a's and 'n's are grouped. This happens because rotations starting with 'an' are sorted together, and those all have the character preceding 'an' in their last column.

In English text, the character before 'an' is usually 'b' (ban), 'c' (can), 'm' (man), 'p' (pan), etc. — similar characters cluster. bzip2 achieves 10-30% better ratio than gzip on English text because of this clustering.

Inverse BWT

Recovery uses the key insight: sorting the last column L gives the first column F. Since each row is a rotation, (F[i], L[i]) are consecutive characters.

def ibwt(last: str, orig_idx: int) -> str:
    """Reconstruct original string from BWT."""
    n = len(last)
    # Build first column by sorting last
    first = sorted(last)
    # LF mapping: last[i] is the character just before first[i]
    # Count occurrences to build precise mapping
    from collections import defaultdict
    table = [''] * n
    for _ in range(n):
        table = [last[i] + table[i] for i in range(n)]
        table = sorted(table)
    return table[orig_idx].rstrip('$')

print(ibwt('annb$aa', 3))        # banana
print(ibwt('ipssm$pissii', 2))  # mississippi

BWT Pipeline — bzip2

bzip2 uses BWT as the first stage of a multi-step pipeline: 1. BWT: Rearrange for character clustering 2. Move-to-Front (MTF): Encode characters by their position in a recently-seen list — clusters become runs of small numbers 3. RLE: Compress runs of zeros (from MTF) 4. Huffman coding: Entropy-code the result

This pipeline achieves better compression than gzip (DEFLATE) on typical text at the cost of more memory and slower speed.

Frequently Asked Questions