Introduction

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.

Try It

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">Type a short word, then press <b>Transform</b>. The demo builds every rotation of the text, sorts them, and reads off the <b>last column</b> — that string is the Burrows-Wheeler transform. Press <b>Invert</b> to rebuild the original from the last column alone. The transform is perfectly reversible.</p>
<div class="row">
  <input id="txt" type="text" maxlength="12" value="banana" autocomplete="off" spellcheck="false" />
  <button id="run" type="button">Transform</button>
  <button id="inv" type="button" class="ghost">Invert</button>
</div>
<div class="out" id="bwtline"></div>
<div class="matrix" id="matrix"></div>
<div class="status" id="status">A "$" end-marker is appended so the transform is reversible.</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// The Burrows-Wheeler Transform (Burrows & Wheeler, 1994).
// Forward: append an end-marker "$" (smallest character), list every rotation of the string, sort them, and output the LAST column. Identical characters tend to cluster together, which makes the result far more compressible.
// Inverse: from the last column alone you can rebuild the whole sorted matrix (LF-mapping / repeated-prepend), recovering the original exactly.
const END = '


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.

;

function rotations(s){
  const r = [];
  for (let i = 0; i < s.length; i++) r.push(s.slice(i) + s.slice(0, i));
  return r;
}
function bwt(s){
  const m = rotations(s + END).sort();
  return { matrix: m, last: m.map(r => r[r.length - 1]).join('') };
}
// Inverse by repeated prepend-and-sort: prepend the last column, sort, repeat n times; the row ending in "$" is the original (with the marker).
function ibwt(last){
  const n = last.length;
  let table = Array.from({ length: n }, () => '');
  for (let k = 0; k < n; k++){
    for (let i = 0; i < n; i++) table[i] = last[i] + table[i];
    table.sort();
  }
  const row = table.find(r => r[r.length - 1] === END);
  return row.slice(0, -1); // strip the "$"
}

function setStatus(t, cls){ const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + (cls || ''); }
function clean(){ return (document.getElementById('txt').value || '').replace(/\$/g, '').slice(0, 12); }

function showMatrix(matrix){
  const box = document.getElementById('matrix'); box.innerHTML = '';
  matrix.forEach(rowStr => {
    const row = document.createElement('div'); row.className = 'mrow';
    for (let i = 0; i < rowStr.length; i++){
      const c = document.createElement('div');
      c.className = 'ch' + (i === 0 ? ' first' : '') + (i === rowStr.length - 1 ? ' last' : '');
      c.textContent = rowStr[i];
      row.appendChild(c);
    }
    box.appendChild(row);
  });
}

function transform(){
  const s = clean();
  if (!s){ setStatus('Type at least one character.', 'bad'); return; }
  const { matrix, last } = bwt(s);
  showMatrix(matrix);
  document.getElementById('bwtline').innerHTML = fmt('BWT (last column): <b>%last%</b>', { last: last });
  setStatus(fmt('Sorted %length% rotations. Green = first column, red = last column (the transform).', { length: matrix.length }), 'ok');
  console.log('BWT("' + s + '$") =', last);
}
function invert(){
  const s = clean();
  if (!s){ setStatus('Type at least one character.', 'bad'); return; }
  const last = bwt(s).last;
  const back = ibwt(last);
  const ok = back === s;
  setStatus(fmt('%v% Inverted "%last%" → "%back%"%v2%', { v: ok ? '✓' : '✗', last: last, back: back, v2: ok ? ' — matches the original!' : ' (mismatch)' }), ok ? 'ok' : 'bad');
  console.log('iBWT("' + last + '") =', back, '| matches:', ok);
}

document.getElementById('run').addEventListener('click', transform);
document.getElementById('inv').addEventListener('click', invert);
document.getElementById('txt').addEventListener('keydown', e => { if (e.key === 'Enter') transform(); });
transform();
Result
Console

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.

The Real Complexity

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(n2log⁡n)O(n^{2} \log n). Sorting all nn rotations of an nn-character string, where each comparison can scan nn characters, is wasteful — and storing the full matrix costs n2n^{2} space.
  • Done right, it is linear. A suffix array sorts every rotation in O(n)O(n) time and O(n)O(n) space; the last column falls out directly. The inverse is also O(n)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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/burrows-wheeler/Content licensed under CC BY-NC 4.0.