BURROWS-WHEELER scramble it to order it, and back again
Take a string, list all its rotations, sort them, and read off the last column. The result looks scrambled — but equal letters now cluster into runs (easy to compress), and, astonishingly, the scramble is perfectly reversible. It is the heart of bzip2 and of modern genome aligners. The transform is sort-and-index work, so it runs in real I-13.
THE TECHNIQUE all rotations, sorted, last column
Append an end-marker, form every cyclic rotation, sort them lexicographically, and take the final character of each — that column is the transform. Equal characters bunch into runs because sorting groups rotations by the context that follows them. And it inverts: the last column plus stable sorting is enough to walk the original back out. live demo
HISTORY & CREDIT a decade in a drawer
“Burrows-Wheeler, 1994” — but the second name had it then a decade earlier and never published it alone. cited
~1983 · David Wheeler — co-inventor of the subroutine (the “Wheeler jump”) on the EDSAC, 1949 — devises the block-sorting transform at Cambridge. He does not publish it; it circulates quietly. 1994 · Michael Burrows & Wheeler write it up as a DEC SRC research report (“A Block-sorting Lossless Data Compression Algorithm”) — a decade after the idea. 1996 · Julian Seward’s bzip2 makes it a household compressor (BWT + move-to-front + Huffman). 2000s · the FM-index built on the BWT powers short-read genome aligners (Bowtie, BWA) — the transform searches DNA without decompressing it.
A transform that makes data more ordered without losing a bit, sat unpublished for ten years. Wheeler, ~1983
RECOMMEND FOR I-13 sort rotations, read a column
The forward transform is: build the rotations (indices into the string), sort them, and gather one character each — all indexed array work. On the bounded array with the sorts the campaign already runs (counting-049, quick-045):
# BWT of "BANANA$"
transform = ANNB$AA # the N's and A's cluster into runs -> compressible
# reversible: last column + stable sort walks the original back
Recommend:nothing new for the transform itself — it is rotation indices + a sort + a gather, all bounded-array work over character codes (no bignum, no bitwise). The one aggregate it strains is strings (the campaign’s standing aggregate note): the rotations are conceptually substrings, expressed here as start-indices into one array, and the sort compares by those indices. Note: the space-savvy version never materialises the rotations — it sorts suffixes (a suffix array), which is the same 1-D index-array discipline, just with a smarter comparator.