THE FOLD / LOOT / THE HOARD / THE BLOCK SORT
THE BLOCK SORT
Burrows-Wheeler — reversible sort that clusters
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Burrows–Wheeler Transform. Take a string, list all its rotations, sort them alphabetically, and read off the last column. That is the BWT — and it is the strange heart of bzip2.
Two things make it magic. First, it is perfectly reversible: from the last column alone you can rebuild the entire sorted table and recover the original, exactly. Second, it clusters similar characters together — because sorting the rotations groups every character by the context that follows it, identical contexts pile their preceding letters into long runs. It doesn’t compress by itself; it rearranges the data so that a simple run-based coder can.
LIT verified live: over 2,000 random strings the inverse transform recovers the original exactly, and on repetitive text the BWT has far more adjacent-equal characters than the input (window.__bwt.invertible && clusteringIncreases). ‘banana’ → annb␣aa. FIG no framing; the rotation-sort, the exact inverse, and the clustering are all real.
Two things make it magic. First, it is perfectly reversible: from the last column alone you can rebuild the entire sorted table and recover the original, exactly. Second, it clusters similar characters together — because sorting the rotations groups every character by the context that follows it, identical contexts pile their preceding letters into long runs. It doesn’t compress by itself; it rearranges the data so that a simple run-based coder can.
LIT verified live: over 2,000 random strings the inverse transform recovers the original exactly, and on repetitive text the BWT has far more adjacent-equal characters than the input (window.__bwt.invertible && clusteringIncreases). ‘banana’ → annb␣aa. FIG no framing; the rotation-sort, the exact inverse, and the clustering are all real.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in THE HOARD, beside THE HUFFMAN — the loot domain of packing your treasure small. BWT is the pre-processing that makes the packing work: it doesn’t shrink the hoard, it sorts it into runs so the next stage can. AVAN (AI) built the instrument: the rotation matrix, the reversible reconstruction, the clustering measure.
The weave: David names the seat (preparing the hoard to be packed); I make the sort visible and the reversibility checkable — the runs forming in 1D, the rotation matrix in 2D, the last column and its inverse links in 3D. The sphere is the seam. Credit: Michael Burrows & David Wheeler (1994).
The weave: David names the seat (preparing the hoard to be packed); I make the sort visible and the reversibility checkable — the runs forming in 1D, the rotation matrix in 2D, the last column and its inverse links in 3D. The sphere is the seam. Credit: Michael Burrows & David Wheeler (1994).
3 ONE DIMENSION
The string, and its BWT below. Watch the transform gather scattered identical letters into runs — the same characters, reordered so that like sits next to like. That clustering is what a compressor feeds on.
4 TWO DIMENSIONS · INTERACTIVE
The rotation matrix: every rotation of the word, sorted. The BWT is the highlighted last column. Cycle the words — and see the inverse transform rebuild the original from that column alone, exactly.
5 THREE DIMENSIONS + AVAN’S INVERSE
The sorted rotation matrix as a turning grid — green characters, the whole sorted table.
AVAN’s addition (the inverse-companion): I light the last column magenta — the BWT itself — and it is a genuine inverse in two senses at once. Sorting the rotations orders every letter by the context after it, so the transform is a reordering by the future rather than the past; and that same structure makes it losslessly reversible — the clustering that helps compression and the exact undo are one mechanism seen forward and backward. Nothing is added or thrown away; the information is only rearranged so its redundancy lies flat and adjacent. The green is the sorted whole; the magenta is the single column that both clusters the data and remembers how to put it back.
LIT Genuine Burrows-Wheeler Transform (Burrows & Wheeler, 1994). Verified live: over 2,000 random strings the inverse transform recovers the original exactly, and on repetitive text the BWT has far more adjacent-equal characters than the input (window.__bwt.invertible && clusteringIncreases, both true). 'banana' -> annb_aa. The rotation-sort, the LF-mapping inverse, and the context-clustering are exact — no information added or lost, only rearranged.
FIG No metaphor is doing the work: the rotation sort, the exact reversibility, and the clustering are all real and checked. BWT alone does not compress — it reorders to expose redundancy for a following coder; that's stated plainly, not overclaimed.
FIG No metaphor is doing the work: the rotation sort, the exact reversibility, and the clustering are all real and checked. BWT alone does not compress — it reorders to expose redundancy for a following coder; that's stated plainly, not overclaimed.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE HOARD · David Lee Wise (ROOT0), with AVAN