Burrows-Wheeler transform

The Burrows-Wheeler transform (BWT, also called block-sorting compression), is an algorithm used in data compression techniques such as bzip2. It was invented by Michael Burrows[?] and David Wheeler[?].

When a string is transformed by the BWT, none of its characters change. It just rearranges the order of the characters. If the original string had several substrings that occurred often, then the transformed string will have several places where a single character is repeated multiple times in a row. This is useful for compression, since it tends to be easy to compress a string that has runs of repeated characters. For example, the string:

 SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES

 TEXYDST.E.XIIXIXXSMPPSS.B...S.EEUSFXDIOIIIIT

.BANANA.

.BANANA.
..BANANA
A..BANAN
NA..BANA
ANA..BAN
NANA..BA
ANANA..B
BANANA..

ANANA..B
ANA..BAN
A..BANAN
BANANA..
NANA..BA
NA..BANA
.BANANA.
..BANANA

BNN.AA.A

In these two examples, the output would actually be more than just the string shown. It would be the string plus a pointer telling which character in the output string was the last character in the input string. However, there is an equivalent way to describe the algorithm that doesn't use pointers.

The following pseudocode gives a simple, but inefficient, way to calculate the BWT and its inverse. It assumes that there is a special character 'EOF' which is the last character of the text, occurs nowhere else in the text, and is ignored during sorting. Given this assumption, the transformed text will be the same length as the original text, and there is no need to worry about pointers.

  function BWT (string s)
    create a list of all possible rotations of s
    let each rotation be one row in a large, square table
    sort the table alphabetically (treat each row as a string)
    return the last (rightmost) column of the table

  
  function inverse_BWT (string s)
    create an empty table with no rows or columns
    repeat length(s) times:
      insert s as a new column down the left side of the table
      sort the table alphabetically (treat each row as a string)
    return the row that ends with the 'EOF' character

The remarkable thing about the BWT is not that it generates a more easily coded output - any number of trivial operations would do that - but that it is reversible, allowing the original document to be re-generated from the last column data.

The inverse can be understood this way. Take the final table in the BWT algorithm, and erase all but the last column. Given only this information, you can easily reconstruct the first column. The last column tells you all the characters in the text, so just sort these characters to get the first column. Then, the first and last columns together give you all pairs of characters in the document. Sorting the list of pairs gives the first and second columns. Continuing in this manner, you can reconstruct the entire list. Then, the row with the "end of file" character at the end is the original text.

A number of optimizations can make these algorithms run more efficiently without changing the output. In BWT, there is no need to actually store the table. Each row of the table can be represented by a single pointer into the string s. In inverse_BWT there is no need to store the table or to do the multiple sorts. It is sufficient to sort s once with a stable sort, and remember where each character moved. This gives a single-cycle permutation, whose cycle is the output. A "character" in the algorithm can be a byte, or a bit, or any other convenient size.

There is no need to have an actual 'EOF' character. Instead, a pointer can be used that remembers where in a string the 'EOF' would be if it existed. In this approach, the output of the BWT must include both the transformed string, and the final value of the pointer. That means the BWT does expand its input slightly. The inverse transform then shrinks it back down to the original size: it is given a string and a pointer, and returns just a string.

A complete description of the algorithms can be found in Burrow and Wheeler's paper, or in a number of online sources.

Sample implementation (in C, with English comments) is in article on Polish Wikipedia (http://pl.wikipedia.com/wiki.cgi?Transformata_Burrowsa-Wheelera).

Reference:

M. Burrows and D. Wheeler. A block sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation, 1994.

External links:

• ResearchIndex page for BWT paper (http://citeseer.nj.nec.com/76182)
• BWT paper hosted at DEC (http://gatekeeper.dec.com/pub/DEC/SRC/research-reports/abstracts/src-rr-124)
• Article by Mark Nelson on the BWT (http://dogma.net/markn/articles/bwt/bwt.htm)