The encyclopedia · Software & IT · Technical decision · 1994
Burrows and Wheeler re-sorted a block's rotations to make it compress far better
Burrows and Wheeler's 1994 transform sorted a block's rotations into an order that clusters equal characters, letting bzip2 beat older compressors.
Digital Equipment Corporation
the move
Lossless compression is bounded by how much redundancy a method can see. LZ-family and Huffman coding each reach a plateau on ordinary text.
Burrows and Wheeler's 1994 DEC report described a block-sorting transform: list every rotation of the block, sort them, and emit the last column. Because rotations share suffixes, identical characters cluster, and a short run-length and move-to-front pass turns that into very few symbols.
The transform is invertible, so it is a rearrangement not a loss. The result fed bzip2, which compressed text more effectively than contemporary tools and made the technique the standard for slow-but-tight compression.
why it works
- Sorting rotations brings identical symbols together where context is the same.
- Run-length and move-to-front coding then find long, cheap runs.
- The transform is a permutation, so decompression is exact.
- It works on any repeated structure, so it is not tuned to one file type.
what transfers
Before you compress, reorder the data so identical symbols sit beside each other. A transform that clusters the predictable parts can make an ordinary compressor dramatically stronger.
what came after
The Burrows-Wheeler transform became bzip2's engine and later the basis of the FM-index, which finds substrings and maps genomes. The same idea powers high-throughput bioinformatics alignment tools today.
references
spotted an error? The archive wants to know.