THE FOLD / CHEAT / NOCLIP / THE BWT
THE BWT
rearrangement so that compression becomes possible
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Sort every rotation of a string and take the last column. Characters that precede the same context end up next to each other, so the result is full of runs — and the whole thing is exactly reversible from one integer.
LIT verified live. 2,000 characters of repeated text, 27 distinct symbols. Before: 2,000 runs, mean run length 1. After: 40 runs, mean length 50 — a 50× reduction. It inverts back to the original exactly, and the entropy is unchanged to six decimal places: 4.3394 bits either way.
LIT verified live. 2,000 characters of repeated text, 27 distinct symbols. Before: 2,000 runs, mean run length 1. After: 40 runs, mean length 50 — a 50× reduction. It inverts back to the original exactly, and the entropy is unchanged to six decimal places: 4.3394 bits either way.
2 HOW IT WAS WEAVED · AI + HUMAN
Burrows and Wheeler published this in 1994; it is the front end of bzip2 and the basis of the FM-index.
AVAN (AI) got it wrong twice, and both corrections improved it. The inverse transform was simply broken — the reconstruction is the LF mapping, walked backwards from the stored row index. And it was first run on an i.i.d. source, where BWT should fail: it clusters characters by the context that follows them, and a memoryless source has no context. Runs went up, which was the right answer to a badly posed question.
AVAN (AI) got it wrong twice, and both corrections improved it. The inverse transform was simply broken — the reconstruction is the LF mapping, walked backwards from the stored row index. And it was first run on an i.i.d. source, where BWT should fail: it clusters characters by the context that follows them, and a memoryless source has no context. Runs went up, which was the right answer to a badly posed question.
3 ONE DIMENSION
The string, and the last column of its sorted rotations.
4 TWO DIMENSIONS · INTERACTIVE
Take away the structure and watch it stop working.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the same letters, in a better order.
AVAN’s addition (the inverse-companion): the forward reading is that the Burrows–Wheeler transform prepares data for compression. The inverse is that it compresses nothing whatsoever. The output is a permutation — the same multiset of characters, the same entropy to six decimals, not one bit smaller. What it does is move the redundancy from a place no coder can see, spread across contexts, to a place every coder can, adjacency. Read backwards, this is not compression but rearrangement so that compression becomes possible, and the distinction is the whole idea.
LIT 2,000 characters of repeated text over 27 distinct symbols go from 2,000 runs with a mean run length of 1 to 40 runs with a mean of 50 - a 50x reduction - inverting back to the original exactly, with the entropy unchanged to six decimal places at 4.3394 bits either way
FIG Burrows and Wheeler published this in 1994; it is the front end of bzip2 and the basis of the FM-index. AVAN got it wrong twice and both corrections improved it. The inverse transform was simply broken - the reconstruction is the LF mapping walked backwards from the stored row index. And it was first run on an i.i.d. source, where BWT should fail: it clusters characters by the context that follows them and a memoryless source has no context, so runs went up, which was the right answer to a badly posed question.
FIG Burrows and Wheeler published this in 1994; it is the front end of bzip2 and the basis of the FM-index. AVAN got it wrong twice and both corrections improved it. The inverse transform was simply broken - the reconstruction is the LF mapping walked backwards from the stored row index. And it was first run on an i.i.d. source, where BWT should fail: it clusters characters by the context that follows them and a memoryless source has no context, so runs went up, which was the right answer to a badly posed question.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of NOCLIP · David Lee Wise (ROOT0), with AVAN