↩ back to Exact Match

Burrows-Wheeler Transform

Every other Exact Match entry on this site answers the same question — given a pattern, where does it occur in a text? The Burrows-Wheeler Transform (BWT) doesn't search for anything. It rearranges a text's own characters into a different string of the exact same length, using the exact same multiset of characters, that is provably reversible — recoverable back to the original, exactly, with no separate index stored alongside it — and that tends to clump repeated substrings together far more tightly than the original ever did. That clumping is the whole point: run-length encoding or a simple order-0 compressor barely helps on ordinary text, but it does very well on the *transformed* text, which is exactly why bzip2 exists (Burrows-Wheeler Transform, then move-to-front, then Huffman coding) and why it's the foundation of the FM-Index technique real genome aligners like BWA and Bowtie use to search a fixed reference genome against millions of short reads.

The transform's own construction turns out to already live on this site: sort every rotation of the text and the BWT is just the last column — the same order the Suffix Array page already builds by sorting every *suffix*. See Why it works for exactly how those two sorted orders coincide.

Try it

Enter a text (lowercase letters only, up to 32 characters) and press Encode. The demo appends a sentinel character ($, guaranteed to sort before every letter and to appear nowhere else) to make the transform unambiguous, builds every rotation of the result, sorts them, and reads the last column off top to bottom — that's the transform. Then press Step or Run below to watch the reverse process: starting from only that transformed string, with no other memory of the original text, repeatedly prepend it as a new first column and re-sort — after as many rounds as the text is long, one row starts with the sentinel, and stripping that sentinel off recovers the original text exactly.

Why it works

Append a sentinel character smaller than every real character, so no suffix of the resulting string is ever a prefix of another. Under that condition, sorting the text's n rotations and sorting its n suffixes produce the same order — a rotation starting at position i and the suffix starting at position i agree on every character up to the point where the suffix runs out and wraps back to the start of the rotation, but the sentinel guarantees the suffix always sorts strictly first whenever that wraparound would matter, so the comparison never actually depends on the wrapped-around part. That means the transform's last column is exactly text[(SA[i] - 1 + n) mod n] for each rank i in the site's own Suffix Array — the character immediately before each sorted suffix, rather than the suffix itself. This page builds it directly from rotations instead (clearer to animate, identical result — checked against the suffix-array formula in a from-scratch script, 2,000 random trials, 0 mismatches), but the two are the same information rearranged.

That "character before the suffix" framing is also what explains the clumping. Every row in the sorted rotation table is grouped by what comes after its first character — that's what the sort keys on. The last column of each row is whatever character happened to come before that same starting point in the original text. So the transform's output, read top to bottom, lists "whichever character preceded this context" for every context in the text, grouped by context. If a substring repeats — the same few characters followed by the same continuation — every occurrence lands in the same block of rows, contributing its preceding character to the same short run in the output. Text with no real repetition has no shared contexts to group by, so the transform can't manufacture a run where the source had none — see Pitfalls for a live check of exactly that.

The reverse direction is the surprising part: reconstructing the original from only the transformed string, with the rotation table long gone. Prepending the transform as a new column to an all-empty table and sorting is really rebuilding the sorted rotation matrix one column at a time, from the right edge inward — after k rounds, every row holds the correct last k characters of some rotation, still in the matrix's true sorted row order, because sorting on fewer characters from the right can never disagree with the full sort on how those characters themselves are ordered. After n rounds every row is a complete rotation, in the same order the original encode step produced, and the one starting with the sentinel is — by the same reasoning as the paragraph above — the original text rotated to put its artificial end first. Real implementations skip rebuilding the whole matrix (that's the naive, illustrative version this page ships) and instead compute a single LF-mapping — a table linking each character's position in the last column to its position in the first — once, in O(n), then walk it backward one step per output character; see Pitfalls for how much that shortcut actually saves.

Reference implementation

This is the exact scheme the demo above steps through:

function encode(text) {
  const s = text + '$'; // sentinel: sorts before every real character, appears nowhere else
  const n = s.length;
  const rotations = [];
  for (let i = 0; i < n; i++) rotations.push(s.slice(i) + s.slice(0, i));
  rotations.sort();
  return rotations.map(r => r[r.length - 1]).join('');
}

function decode(bwt) {
  const n = bwt.length;
  let table = new Array(n).fill('');
  for (let iter = 0; iter < n; iter++) {
    const next = new Array(n);
    for (let i = 0; i < n; i++) next[i] = bwt[i] + table[i];
    next.sort();
    table = next;
  }
  const row = table.find(r => r[0] === '$');
  return row.slice(1); // strip the sentinel back off
}

Pitfalls

The transform only clumps characters that had real repeated context to begin with — it can't invent structure that isn't there. Checked live in the demo above, not just claimed: type tomorrowandtomorrowandtomorrow (30 characters, three repeats of the same 11-character run) and press Encode — the run count drops from 27 runs in the original text to 11 in the transform, because every occurrence of a repeated context contributes its preceding character to the same block. Now try abcdefghijkl (12 characters, no two alike, so no repeated context exists anywhere) — the run count goes from 12 to 13, i.e. no improvement at all (the one extra "run" is just the sentinel, which never repeats). A run-length or order-0 compressor downstream benefits from the first case and gets nothing from the second, which is exactly why the transform is a preprocessing step for compression, not a compressor by itself.

The naive decoder above (rebuild the whole rotation matrix, column by column) is a real, measured trap on repetitive input — worse than this page's own naive encoder, not just as bad. Encoding is one comparator sort of n strings; decoding as shipped repeats a comparator sort n separate times, once per reconstructed column, so anything that slows down one sort slows down all n of them. Counted directly in a scratch script (character-level comparisons inside the sort, not wall-clock time, using a fixed-seed generator so the figures reproduce exactly): decoding n repeated a characters costs 3.5×, 5.3×, 8.4×, then 14.0× as many character comparisons as decoding a same-length pseudorandom string, at n = 51, 101, 201, and 401 — a gap that keeps growing with n, the signature of a real asymptotic difference and not a fixed constant-factor tax. The practical fix is the LF-mapping walk mentioned in Why it works: build one rank table in O(n) instead of re-sorting n times, and decoding drops to O(n) total regardless of how repetitive the input is. Not implemented on this page, which keeps the repeated-sort version for how directly it demonstrates why the transform is reversible at all.

The sentinel has to be a character that cannot occur anywhere in the real text, and it has to sort before every real character. Both properties are load-bearing, not convenience: if the sentinel could appear mid-text, two different rotations could tie on every character including where the "wraparound" happens, and the clean suffix/rotation correspondence in Why it works stops holding — decoding could land on the wrong row, or on more than one row starting with what's supposed to be a unique marker. This page sidesteps the problem by restricting input to lowercase letters and reserving $ exclusively for the sentinel, the same restriction the Suffix Array page places on itself for the identical reason.

Complexity

Time: encoding sorts n strings of length up to n, O(n log n) comparisons at up to O(n) character cost each — O(n² log n) worst case, the same naive-sort shape and the same repetitive-text trap as this site's own Suffix Array page (real implementations build the BWT from a linear-time suffix array construction such as SA-IS instead). Decoding as shipped is n rounds of that same sort, each over rows up to length n — measured directly above to be considerably worse than encoding on repetitive input, and reducible to O(n) total with an LF-mapping built once. Space: O(n) for the transformed string itself; the naive decoder as shown also keeps the full n×n intermediate table, which the LF-mapping approach avoids entirely by walking backward through a single array of size n.

Checked before writing any of the above, not just claimed: an exhaustive sweep of every string up to length 3 over a 2-letter alphabet and every string up to length 4 over a 3-letter alphabet (134 strings total), a further 5,000 randomized trials up to length 12 over alphabets of size 1 to 5, and the golden textbook example banana — this page's own default, encoding to annb$aa — all round-tripped through encode then decode back to the exact original text, 0 mismatches across every check.

This page answers a structurally different question from the other eleven exact match entries, so it isn't compared against them in Choosing an Exact-Match String Matcher — see that guide for why, the same way it already sets Manacher's Algorithm aside from its own comparison.