THE FOLD / GLITCH / OFF BY ONE / THE RUN LENGTH
THE RUN LENGTH
it loses loudly where others lose quietly
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Replace each run of identical symbols with the symbol and a count. It is the simplest compression there is, and it is the clearest demonstration that no compressor helps everything.
LIT verified live, same coder and same alphabet in all three columns. On run-structured input, 2,000 bytes become 80 — 25× smaller. On strictly alternating input they become 4,000 — exactly double, the worst case, because every run has length one and costs two bytes. On a random source, 3,496. Two of the three columns are expansions.
LIT verified live, same coder and same alphabet in all three columns. On run-structured input, 2,000 bytes become 80 — 25× smaller. On strictly alternating input they become 4,000 — exactly double, the worst case, because every run has length one and costs two bytes. On a random source, 3,496. Two of the three columns are expansions.
2 HOW IT WAS WEAVED · AI + HUMAN
Run-length coding is in fax machines, BMP files and the back end of BWT-based compressors, and it is the pigeonhole theorem you can see in one line.
AVAN (AI) checked that the worst case is exactly doubling rather than merely bad, because 4,000 from 2,000 is a prediction and “expands” is not. It is the cleanest illustration available of the counting argument two spheres over: the coder that wins hardest also loses hardest, on the same alphabet, with nothing changed but the order.
AVAN (AI) checked that the worst case is exactly doubling rather than merely bad, because 4,000 from 2,000 is a prediction and “expands” is not. It is the cleanest illustration available of the counting argument two spheres over: the coder that wins hardest also loses hardest, on the same alphabet, with nothing changed but the order.
3 ONE DIMENSION
Three inputs, one coder.
4 TWO DIMENSIONS · INTERACTIVE
Shorten the runs until the coder turns against you.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a count standing in for a run.
AVAN’s addition (the inverse-companion): the forward reading is that run-length coding is naive and fails on unstructured data. The inverse is that its failure is the honest one. It doubles, loudly and predictably, on exactly the inputs it cannot help — where a sophisticated coder fails quietly by a few percent and leaves you believing it worked. Read backwards, the crudeness is a feature of the diagnostic: a compressor whose worst case is visible has told you something, and one whose worst case is invisible has only hidden it.
LIT the same coder on the same alphabet turns 2,000 bytes of run-structured input into 80 - 25 times smaller - turns strictly alternating input into exactly 4,000, the worst case of doubling because every run has length one and costs two bytes, and turns a random source into 3,496: two of the three columns are expansions
FIG Run-length coding is in fax machines, BMP files and the back end of BWT-based compressors, and it is the pigeonhole theorem you can see in one line. AVAN checked that the worst case is exactly doubling rather than merely bad, because 4,000 from 2,000 is a prediction and expands is not. The coder that wins hardest also loses hardest, on the same alphabet, with nothing changed but the order.
FIG Run-length coding is in fax machines, BMP files and the back end of BWT-based compressors, and it is the pigeonhole theorem you can see in one line. AVAN checked that the worst case is exactly doubling rather than merely bad, because 4,000 from 2,000 is a prediction and expands is not. The coder that wins hardest also loses hardest, on the same alphabet, with nothing changed but the order.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of OFF BY ONE · David Lee Wise (ROOT0), with AVAN