Burrows-Wheeler Transform — Build, Sort, Extract, then Invert

Forward: append $, list rotations, sort, take the last column (the BWT). Inverse: walk the LF-mapping from the $ row to rebuild the original.

phase: build step 0

Rotation matrix of banana$

first column F (sorted chars) last column L = BWT LF target row

BWT output (last column)

Inverse via LF-mapping

The inverse follows LF(i) = C[L[i]] + Occ(L[i], i) from the $ row, emitting the original string backward.

First / Last column rank table — the LF-mapping made explicit

Each row pairs the first column character F with the last column character L and shows the rank (which occurrence of that character it is). The LF-mapping says the k-th occurrence of a character in L jumps to the k-th occurrence of the same character in F. During the inverse walk the current and target rows are highlighted so you can see the jump.

first column F last column L current / LF-target row
Press Step to begin. We build every rotation of the string plus $, sort them, read the last column (the BWT), then invert it with the LF-mapping.
Self-contained visualization. The first column F is always the sorted characters; the last column L is the BWT. Reversibility comes from the LF-mapping forming a single cycle (the unique $ guarantees it). See junior.md (forward), middle.md (LF-mapping inverse, FM-index), and professional.md (proofs).