visual-cs / Burrows-Wheeler Transform

BWT: rearrange characters so repeated patterns cluster together.

The Burrows-Wheeler Transform reorders a string so that characters from similar contexts group together, making subsequent compression (like run-length encoding or move-to-front) far more effective. Used in bzip2 and bioinformatics sequence alignment.

Interactive Demo

Input String

Speed 5

Legend

First Column (F)

Last Column (L / BWT)

Sentinel ($)

Current Row

Active Cell

Reconstructed

Statistics

Enter a string and click Forward BWT to begin.

Step Log

Waiting for input...

How It Works

Forward Transform

1. Append sentinel $ (sorts before all letters).
2. Generate all rotations of the string.
3. Sort rotations lexicographically.
4. The last column of the sorted matrix is the BWT output.

Inverse Transform

1. The BWT string is the last column (L).
2. Sorting L gives the first column (F).
3. Build LF-mapping: LF[i] maps row i in L to the corresponding row in F.
4. Follow the mapping from the sentinel row to reconstruct the original.

Why It Helps Compression

Characters from similar contexts cluster in the BWT output. For banana$, the BWT is annb$aa — note the grouped a's and n's. Run-length encoding then compresses these runs efficiently.

Complexity

Forward BWT O(n² log n) naive — O(n) with suffix array

Inverse BWT O(n)

Space O(n²) for rotation matrix display