Skip to content
Tutorials Center
My learning

Topics

Lesson 29 of 37 ยท Compression in Practice

The Burrows-Wheeler Transform and Move-to-Front

Understand the Burrows-Wheeler transform, move-to-front coding and run-length encoding that power bzip2, and implement the whole reversible pipeline in Python.

Sometimes the best compression trick is not a smarter code, but a smarter view of the data. The Burrows-Wheeler transform (BWT) rearranges a block of text into a string of the same letters that is much easier to compress, and the rearrangement is perfectly reversible. It was published in 1994 and is the heart of bzip2, and of the index structures used in DNA sequence alignment (the FM-index).

In this lesson you implement BWT, its inverse, move-to-front (MTF) coding and run-length encoding (RLE). Together they form the bzip2 pipeline, followed by an entropy coder such as Huffman coding.

The idea

Take a text and list all of its rotations. Sort the rotations alphabetically. The last column of the sorted list is the BWT output. Why is that useful? In English, the letters before "he" are often "t" (as in "the", "then", "there"). Rotations that start with the same context are adjacent after sorting, so the last column groups similar preceding letters together: long runs of the same letter.

To make the transform invertible we append a unique end marker (here $, smaller than all other letters). Then the original text is the only rotation that ends with $.

Python BWT of 'banana' step by step

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For banana the output is annb$aa: the letters are the same, but equal letters are now close to each other. For longer text the effect is much stronger.

Inverting the transform

How can anyone recover the text from just the last column? Sort the last column and you get the first column. Prepend the last column to the sorted first column, sort again, and you get the first two columns, and so on. After n rounds you have the whole table, and the row that ends with $ is the original. That version is quadratic in memory; real implementations use the LF-mapping: the i-th occurrence of a letter in the last column is the same character as the i-th occurrence of that letter in the first column. We use that trick.

Python Inverse BWT with LF-mapping

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Move-to-front and run-length coding

After BWT we have runs like aaabbbb, but the symbols still change. Move-to-front replaces each symbol by its position in a list of recently used symbols, then moves that symbol to the front. A run of the same symbol turns into 0 0 0 after its first occurrence, and nearby symbols become small numbers. The output has a very skewed distribution: lots of zeros and ones, few big values. That is exactly what a Huffman or arithmetic coder loves. Run-length encoding of the zeros shortens it further.

Python Move-to-front

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The full pipeline, measured

Does it really help? We compress a text with an order-0 entropy estimate before and after the transforms. A repetitive structure, like English words repeating, makes BWT shine.

Python BWT + MTF lowers the order-0 entropy

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

BWT alone does not change the letter counts, so the order-0 entropy stays the same. The big drop appears after MTF, because the grouped letters become zeros. That is the point: BWT does not compress by itself, it prepares the data for a simple entropy coder.

Comparing with bzip2

Python ships the real thing as the bz2 module (and in the browser runtime if it is available). The code below falls back gracefully if it is not.

Python bzip2 versus zlib

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For highly repetitive inputs both are tiny. On real text bzip2 is typically a little smaller than gzip but slower; the real trade-off appears with large inputs. bzip2 processes blocks of 100-900 KB, and sorting the rotations costs time and memory (practical implementations use suffix arrays).

BWT is also the basis of the FM-index: with the last column and a few small tables you can search for any substring of a huge genome in time proportional to the pattern length, without storing the text itself. Bioinformatics tools like Bowtie and BWA depend on it.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the Burrows-Wheeler transform of a string?

    Sort all rotations (with an end marker) and read the last column. That output is a permutation of the input that groups similar contexts.
  2. 2. Why is an end-of-string marker needed?

    The unique smallest marker tells the inverse transform where the original text begins and ends.
  3. 3. What does move-to-front coding do with a long run of the same symbol?

    After a symbol is used it moves to the front, so repeating it gives index 0 each time.
  4. 4. Which tools rely on the Burrows-Wheeler transform?

    bzip2 uses BWT + MTF + RLE + Huffman, and FM-indexes in sequence aligners are built on the BWT.

Summary

  • BWT sorts all rotations and outputs the last column: same letters, better grouped.
  • It is reversible with an end marker and the LF-mapping.
  • Move-to-front turns runs and local repeats into small numbers, mostly zeros.
  • RLE and a Huffman or arithmetic coder finish the bzip2 pipeline.
  • BWT does not compress by itself; it makes the data easy for a simple coder.

Next: Lossy Compression and Rate-Distortion