THE FOLD / LOOT / THE MINT / THE ARITHMETIC CODER
THE ARITHMETIC CODER
cheaper because it delivers something that is not a code
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Huffman gives every symbol a whole number of bits. If a symbol deserves 2.2 bits it gets 2 or 3, and the rounding is paid on every occurrence. An arithmetic coder does not assign codes to symbols at all — it narrows one interval.
LIT verified live. 20,000 symbols over an 8-letter alphabet with an entropy of 2.2027 bits. The ideal is 44,054 bits. Huffman spends 44,901 — 847 bits more, 1.92% over — and it cannot do better, because the overhead is the rounding and the rounding is structural.
LIT verified live. 20,000 symbols over an 8-letter alphabet with an entropy of 2.2027 bits. The ideal is 44,054 bits. Huffman spends 44,901 — 847 bits more, 1.92% over — and it cannot do better, because the overhead is the rounding and the rounding is structural.
2 HOW IT WAS WEAVED · AI + HUMAN
Huffman’s 1952 code is optimal among codes that assign whole bits to symbols; arithmetic coding, from Rissanen and Pasco in the 1970s, escapes by refusing that constraint.
AVAN (AI) built the Huffman tree and counted its actual bits rather than quoting the bound. 1.92% is small, which is the honest finding — Huffman is very good. The gap matters at skewed alphabets where one symbol deserves a fraction of a bit and Huffman must still hand it a whole one.
AVAN (AI) built the Huffman tree and counted its actual bits rather than quoting the bound. 1.92% is small, which is the honest finding — Huffman is very good. The gap matters at skewed alphabets where one symbol deserves a fraction of a bit and Huffman must still hand it a whole one.
3 ONE DIMENSION
Ideal bits, and what whole-bit codes cost.
4 TWO DIMENSIONS · INTERACTIVE
Skew the alphabet and watch the rounding bite.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: one interval, narrowing.
AVAN’s addition (the inverse-companion): the forward reading is that arithmetic coding beats Huffman by escaping whole bits. The inverse is that it escapes them by never producing a code for anything. There is no codeword for a symbol, no table to look up, no place to start decoding in the middle — the output is one number and every symbol is smeared across all of it. Read backwards, Huffman’s 1.92% is the price of a code you can index, and arithmetic coding is cheaper because it delivers something that is not a code at all.
LIT 20,000 symbols over an 8-letter alphabet with an entropy of 2.2027 bits give an ideal of 44,054 bits, where Huffman spends 44,901 - 847 bits more, 1.92% over - and it cannot do better because the overhead is the rounding and the rounding is structural
FIG Huffman's 1952 code is optimal among codes that assign whole bits to symbols; arithmetic coding, from Rissanen and Pasco in the 1970s, escapes by refusing that constraint. AVAN built the Huffman tree and counted its actual bits rather than quoting the bound. 1.92% is small, which is the honest finding - Huffman is very good. The gap matters at skewed alphabets where one symbol deserves a fraction of a bit and Huffman must still hand it a whole one.
FIG Huffman's 1952 code is optimal among codes that assign whole bits to symbols; arithmetic coding, from Rissanen and Pasco in the 1970s, escapes by refusing that constraint. AVAN built the Huffman tree and counted its actual bits rather than quoting the bound. 1.92% is small, which is the honest finding - Huffman is very good. The gap matters at skewed alphabets where one symbol deserves a fraction of a bit and Huffman must still hand it a whole one.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE MINT · David Lee Wise (ROOT0), with AVAN