Burrows–Wheeler Transform
Reorder a text block into a reversible last column and follow its stable inverse mapping.
Free theory articleReorder a text block into a reversible last column and follow its stable inverse mapping.
Concept & interpretation
The Burrows–Wheeler Transform (BWT) permutes a character string by sorting all of its cyclic rotations so that characters preceding similar contexts cluster into runs in the last column, while remaining completely invertible via the Last-to-First (LF) mapping.
Experiment
Explore cyclic sorting and LF links interactively in https://riano.app/module/burrows-wheeler-transform:
- Enter
ABACABAin Text and verify that BWT last column isABC$BAAAand Primary row is 3. - Step through LF row values 0, 1, 2, 3 to see each row highlight alongside its mapped predecessor row LF(i).
- Set Text to
BABABAto see how alternating characters rearrange into clustered runsABBBAA$.