The idea: sort the rotations, keep the last column

The Burrows–Wheeler transform (BWT, Burrows and Wheeler, 1994) reorders the letters of a text so that equal letters tend to sit next to each other. It does not make the text shorter. It makes the text easier to compress, and it can be undone exactly. It is the first stage of bzip2.

Add an end marker $ that sorts before every letter. Write down every rotation of the text: rotation i starts at position i and wraps around. Sort the rotations alphabetically. The output is the last column L of the sorted matrix, read from top to bottom.

The seven rotations of banana$ on the left, the same rotations sorted on the right. In the sorted matrix the first column F reads $aaabnn and the last column L reads annb$aa. The start column 6 5 3 1 0 4 2 is the suffix array.
banana$: sort the 7 rotations, and the last column L = annb$aa is the transform.

The first column F is just the text's letters in sorted order, so it carries no information. All the information is in L. Since each row is a rotation, the letter in L comes right before the letter in F in the text. (Demo: banana$: rotations, sort, last column.)

Why equal letters end up together

Sorting puts rows with the same beginning next to each other. The beginning of a row is the context that follows its L letter. In real text a context mostly predicts the letter before it: "he␣" is very often preceded by "t". So the L letters of neighbouring rows are often the same, and L has runs.

In abracadabra$, rows 6–9 start with "bra…", "bra…", "cad…" and "dab…". Every b, c and d in the word follows an "a", so those four rows all end in "a" and L = ard$rcaaaabb has the run aaaa. (Demo: abracadabra$.) A word repeated three times, sixsixsix$, gives L = xsssxx$iii. A text with no repeated letters, abcdefgh$, gives no runs at all: the BWT only helps when contexts repeat. (Demo: abcdefgh$.)

Move-to-front and the rest of bzip2

Runs are not shorter by themselves. Move-to-front (MTF) turns them into small numbers: keep a list of the letters; for each letter of L output its position in the list and move it to the front. A letter that was just used is at position 0, so a run becomes a run of zeros.

textL (BWT)MTF of Lzeroszeros in MTF of the text
banana$annb$aa1 3 0 3 3 3 020
abracadabra$ard$rcaaaabb1 5 5 3 2 5 4 0 0 0 5 040
mississippi$ipssm$pissii1 3 4 0 4 4 3 4 4 0 1 033
sixsixsix$xsssxx$iii3 3 0 0 1 0 2 3 0 050
abcdefgh$h$abcdefg8 1 2 3 4 5 6 7 800

bzip2 then codes the runs of zeros with two special symbols (RUNA and RUNB, a run length in base 2) and gives the remaining numbers Huffman codes, short ones for the frequent small values. It works on blocks of 100–900 KB (bzip2 -1 to -9): bigger blocks have more repeated contexts and longer runs. Compare LZ77 and DEFLATE, which removes repeats by pointing back to them instead of sorting. (Demo: sixsixsix$.)

Inverting with the LF-mapping

The decoder gets only L (and knows where $ is). Sorting L gives F. Now number equal letters from top to bottom in both columns: a₁ a₂ a₃. The LF-mapping says the k-th "a" in L is the same letter of the text as the k-th "a" in F. The reason: rows that end in "a" are sorted by what follows the "a", and so are rows that start with "a", so the a's appear in the same order in both columns.

The F and L columns of banana$ with ranks: F is $ a1 a2 a3 b1 n1 n2, L is a1 n1 n2 b1 $ a2 a3. Arrows go from L of row 0 (a1) to F row 1, from L of row 1 (n1) to F row 5, from L row 5 (a2) to F row 2, and so on, spelling banana backwards.
Each arrow is one LF jump: from a letter in L to the same letter in F, whose row ends with the letter before it.

Start at row 0, the rotation that begins with $. Its L letter is the last letter of the text. Jump to the row whose F is that same letter (LF); its L letter is the one before. After n − 1 jumps the text is rebuilt from right to left, and the next row ends in $. In code, with C[c] = number of letters smaller than c:

r = 0; T[n-1] = '$'
for k = n-2 down to 0:
    T[k] = L[r]
    r = C[L[r]] + rank(L[r], r) - 1   # LF(r)

For banana$: rows 0 → 1 → 5 → 2 → 6 → 3 → 4 give a, n, a, n, a, b, read backwards "banana". (Demo: invert banana's BWT with LF-mapping.)

The BWT and the suffix array

Because $ is unique and smallest, sorting rotations is the same as sorting suffixes: the start column of the sorted matrix is the suffix array, and L[s] = T[SA[s] − 1]. Real encoders build the suffix array (in linear or near-linear time) instead of an n × n matrix. The FM-index keeps L plus rank tables and uses the LF-mapping backwards to count a pattern's matches without the text; read aligners such as Bowtie and BWA search genomes this way.

What the page leaves out

Real bzip2 starts move-to-front from all 256 byte values, adds an initial run-length step, codes zero runs with RUNA/RUNB, uses up to six Huffman tables chosen every 50 symbols, and stores the row number of the original text instead of a $ marker. Fast suffix-array construction (SA-IS, DC3), the FM-index's sampled rank and locate tables, and the bijective BWT are not shown.