Burrows-Wheeler Transform (BWT)

watch cyclic rotations sort into a matrix whose last column clusters repeated characters — then reverse it losslessly

Starting values — Burrows-Wheeler Transform (BWT)

Input text	banana

Change any control above and the results recompute from these.

Loading interactive simulation...

why sorting rotations creates runs 🖖

When you sort all cyclic rotations of a text, every rotation that shares the same suffix ends up adjacent. The last column — the character just before each sorted prefix — collects characters that all preceded the same context in the original text. Repeated patterns mean many rotations share a common suffix, so the same preceding character appears many times in a row in the last column. Those runs are what RLE and move-to-front encoding exploit. The transform is lossless because the first column F (sorted BWT) and last column L (the BWT itself) together encode a complete map — the LF-mapping — letting you reconstruct the original character by character from just these two columns and the key.

BWT rearranges, it doesn't shrink 🖖

On its own, BWT makes text no smaller: the output has exactly the same length and the same characters, only in a different order. Its real job is to be a reversible preparation step that clusters identical characters together so the compressors that follow — move-to-front, run-length encoding, then Huffman or arithmetic coding — have an easy time. On "abracadabra$" the output is the same twelve characters and contains four a's in a row where the input had no two adjacent.

The same trick that maps your DNA 🖖

A compression idea quietly became a cornerstone of genomics. Wrapped in a structure called the FM-index, the BWT lets you search for a short DNA fragment inside a 3-billion-letter human genome while storing that genome in only a couple of gigabytes. Aligners like Bowtie and BWA — the Burrows-Wheeler Aligner — are built on it, so a 1994 compression trick now underpins how millions of sequencing reads are matched every day.

Problem solved in full

The Burrows–Wheeler transform of "banana$" with all seven rotations sorted 5 steps
Find the Burrows–Wheeler transform of "banana$" and then decide whether anything has been compressed. This is the BWT output step: sentinel appended, all seven rotations sorted, last column read off.
1. The sentinel is appended before anything else happens. Because $ sorts before every letter and appears exactly once, no two rotations can compare equal, so the sort has a single unambiguous answer.
  
  $s = banana$ (n = 7), r_{k} = s [k :] + s [: k], k = 0, \dots, 6$
2. Sorting the rotations lexicographically is the only work the transform does. Reading down the seven rows, notice that the sort has grouped the string by what comes after each position.
  
  $$banana, a$banan, ana$ban, anana$b, banana$, na$bana, nana$ba$
3. The last character of a rotation is the character standing immediately before its first character in the original. That is why the sort produces runs: rows 1 and 2 both begin with 'a' and both end in 'n', because both of those a's are preceded by an n in banana. The key is the row number of the original, and without it the transform cannot be undone.
  
  $L_{j} = s_{(k_{j} - 1) mod n} ⟹ L = annb$aa, key = 4$
4. Nothing has been compressed yet, and nothing could have been — the output is a permutation of the input, the same seven characters in a different order. What changed is the run structure, and that is the only thing that changed.
  
  $b ∣ a ∣ n ∣ a ∣ n ∣ a ∣ $ : R = 7, \overset{r}{ˉ} = 1.00 ⟶ a ∣ nn ∣ b ∣ $ ∣ aa : R = 5, \overset{r}{ˉ} = \frac{7}{5} = 1.4$
5. RLE charges two bytes per run, so five runs cost ten bytes against a seven-byte input. Its break-even never moves: the number of runs has to be under half the length, which here means three or fewer.
  
  $2 R = 10 > N = 7 ⟹ \frac{7}{10} = 0.70 \times, 2 R < N ⟺ R < 3.5$
Answer

The panel prints annb$aa with key = 4, an average run of 1.4 characters, 10 bytes of RLE and a score of 0.70×. The transform did exactly what it promises — it lifted the average run by 40% without touching a single character — and the pipeline still lost, because seven characters is not enough text for that gain to cover two bytes per run. Double the word and the arithmetic flips. "bananabanana$" is thirteen characters and its transform is annnnbba$aaaa: six runs instead of five, while the length nearly doubled, giving 12 bytes against 13 and a score of 1.08×. That is the whole case for BWT — the run count is governed by how many distinct contexts the text has, not by how long it is, so the longer the block the better it pays, which is why bzip2 transforms blocks of up to 900 kB rather than words.

$bananabanana$ : N = 13, R = 6 ⟹ 2 R = 12 < 13, \frac{13}{12} = 1.08 \times$

Learning path

Compression by hand

References (3)

Insight blocks 1 and 2 — the transform itself: M. Burrows and D. J. Wheeler, "A Block-sorting Lossless Data Compression Algorithm." Digital Systems Research Center, Research Report 124, 1994.
Insight block 3 — the aligners it turned into: B. Langmead, C. Trapnell, M. Pop and S. L. Salzberg, "Ultrafast and memory-efficient alignment of short DNA sequences to the human genome." Genome Biology 10, R25, 2009.
And the one the block names outright: H. Li and R. Durbin, "Fast and accurate short read alignment with Burrows–Wheeler transform." Bioinformatics 25(14), 1754–1760, 2009.

By the 42Math team · Updated 2026-08-17

Reviewed against published sources. Corrections welcome. Editorial policy · Corrections

All Computing lessons →

Example problems

banana - "banana$" becomes "annb$aa": the three a's that were never adjacent now sit in two groups, and the run count falls from 7 to 5.
mississippi - "mississippi$" becomes "ipssm$pissii" - the textbook example, and at this length the run count is unchanged at 9. BWT needs longer text before the clustering pays.
abracadabra - "abracadabra$" becomes "ard$rcaaaabb": four a's in a row where the original had no two adjacent, and 12 runs down to 8. The best clustering of the four presets here.
DNA sequence - "AGATCAGA$" becomes "AGC$GTAAA", three A's together from a string with none adjacent. On a genome this is what an FM-index indexes.