The Burrows-Wheeler Transform

Compression usually works by spotting repetition — runs of the same character, or phrases that appear again and again. But real text rarely lines up its repeats neatly. The letters you'd love to group together are scattered all over the file.

In 1994, Michael Burrows and David Wheeler published a startling idea: don't compress the text directly — first reorder it. Their transform shuffles the characters so that identical ones tend to clump into long runs, which off-the-shelf compressors then crush easily.

The magical part is that the shuffle is perfectly reversible. From the scrambled output alone — no extra bookkeeping beyond a single position — you can reconstruct the original exactly. It looks like you've thrown the text into a blender, yet nothing is lost.

Type a short word below. The demo appends an end-marker $, builds every rotation of the string, sorts them into a grid, and reads off the last column in red — that string is the Burrows-Wheeler transform. Notice how identical letters bunch together.

<p class="hint">{{hint}}</p>
<div class="row">
  <input id="txt" type="text" maxlength="12" value="banana" autocomplete="off" spellcheck="false" />
  <button id="run" type="button">{{btn_transform}}</button>
  <button id="inv" type="button" class="ghost">{{btn_invert}}</button>
</div>
<div class="out" id="bwtline"></div>
<div class="matrix" id="matrix"></div>
<div class="status" id="status">{{status_init}}</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.row { display: flex; gap: .5rem; flex-wrap: wrap; align-items: center; margin-bottom: .6rem; }
input { font: 600 15px ui-monospace, monospace; padding: .45rem .6rem; border: 1px solid #adb1b8;
        border-radius: 8px; width: 9rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.out { font: 700 16px ui-monospace, monospace; color: #1d3557; min-height: 1.4em; margin: .3rem 0 .6rem; }
.out b { color: #e63946; }
.matrix { display: inline-grid; gap: 2px; margin: .2rem 0; }
.mrow { display: flex; gap: 2px; }
.ch { width: 26px; height: 26px; display: flex; align-items: center; justify-content: center;
      font: 700 15px ui-monospace, monospace; background: #e8eef3; color: #1d3557;
      border: 1px solid #cdd9e3; border-radius: 5px; }
.ch.last { background: #e63946; border-color: #c92f3c; color: #fff; }
.ch.first { background: #cfe6d6; border-color: #9fcfb0; color: #0a7d33; }
.status { font-size: .95rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; color: #444; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }

// Code not found

Then press Invert. Working from the last column alone, the demo rebuilds the sorted grid one column at a time and recovers your original word — exactly. Try banana (its transform is annb$aa) or mississippi, and watch the repeated letters cluster into runs that a compressor loves.

Unlike most problems on KipuHub, the Burrows-Wheeler transform is not hard — it is solved, efficient, and exact. That is precisely what makes it useful.

• Status: solved. Michael Burrows and David Wheeler introduced it in a 1994 DEC technical report. It is a deterministic transform with a known, exact inverse — no open question, no intractability.
• The naive recipe is $O(n^{2} \log n)$. Sorting all $n$ rotations of an $n$-character string, where each comparison can scan $n$ characters, is wasteful — and storing the full matrix costs $n^{2}$ space.
• Done right, it is linear. A suffix array sorts every rotation in $O(n)$ time and $O(n)$ space; the last column falls out directly. The inverse is also $O(n)$ via the LF-mapping, which links each character in the last column to its twin in the (sorted) first column.
• Reversibility is guaranteed. Because the rows are sorted rotations of one string, the first column is just the sorted last column, and the pairing between them lets you walk the original back out — you only need to remember one row index (or use the $ marker, as the demo does).

So the BWT sits among the comfortably efficient algorithms. The interesting tension is not "can we do it?" but "what do we get" — a representation in which clustering and search become almost free. Compare that to the genuinely hard side of computing in P vs NP.

A reversible reordering that clusters repeats and enables fast search turns out to be enormously practical:

• General compression: bzip2 runs the BWT, then a move-to-front step, then entropy coding — often beating gzip on text by exploiting the clustered runs.
• DNA sequence alignment: the FM-index, built on the BWT, lets aligners like Bowtie and BWA map billions of short reads against a multi-gigabase genome using a compact, searchable index.
• Full-text search: because the BWT supports backward search, you can count and locate any substring of a huge text in time proportional to the pattern, not the text.
• Compressed indexes: "self-indexes" store data and its search index together at close to the compressed size — you search without decompressing.

The same idea that shrinks a text file also lets a laptop search a human genome. For a different angle on squeezing data to its limits, see Squeezing Data.

The Burrows-Wheeler transform is a rare kind of trick: it looks like vandalism — scrambling your text beyond recognition — yet it loses nothing and makes the data far easier to compress and to search. Built with a suffix array, it runs in linear time; inverted with the LF-mapping, it returns your original byte-for-byte.

Sometimes the deepest progress in computing isn't solving an impossible problem but finding a better way to look at an easy one. Reorder the world just so, and patterns that were invisible snap into place. For the broader story of how small data can hide and reveal structure, read Squeezing Data.