For decades, compression forced a choice: Huffman (fast, but wastes a fraction of a bit per symbol) or arithmetic coding (optimal, but slow and patent-encumbered). ANS (2009) dissolves the tradeoff — near-optimal ratio at Huffman speed — by folding the whole message into one growing integer. It now runs inside zstd, LZFSE, and JPEG XL.
THE TECHNIQUE one integer state, growing by -log2(p) per symbol
Keep a single integer state x. Encoding a symbol s replaces x with a larger value using s’s frequency; the rarer the symbol, the more x grows — by exactly −log₂(p) bits, Shannon’s limit. Decoding reads x’s residue to recover the symbol and shrink x back. Encode a string; watch the state climb. live demo
HISTORY & CREDIT a rare recent invention, kept free
“Compression theory is finished, all pre-1990” — true false; the coder your files use today was invented in 2009. cited
1952 / 1976 · Huffman (whole-bit codes) and arithmetic coding (Rissanen/Pasco) mark the old tradeoff: fast-but-lossy-in-bits vs optimal-but-slow. 2009 · Jarek Duda formalises Asymmetric Numeral Systems — a single-state coder that is both near-optimal and Huffman-fast; the tabled form (tANS) is branch-light and cache-friendly. kept free · Duda placed it in the public domain; Google’s rANS-variant application (filed ~2016) was rejected by the USPTO in 2018 as obvious over his prior art. in the wild · zstd (Facebook), LZFSE (Apple), JPEG XL, and CRAM genomics — ANS is the default modern entropy stage.
The last great compression primitive, and one of the few kept deliberately unpatented. Duda 2009
RECOMMEND FOR I-13 integer state, table lookups
The tabled form is integer multiply / divide / mod and lookups into a small frequency table — and it round-trips on the compiler:
$ i13 run ans.i13 # freqs a:3 b:1, M=4, state x=7
enc('b',7) = 31 dec(31) -> 'b', state 7 # exact round-trip
enc('a',7) = 9 # common symbol grows state less (~0.42 bits vs 2 bits)
Recommend:nothing new for the tabled (tANS) form — a single integer state plus × / % and lookups into a bounded frequency array, all small integers well inside f64’s exact range (verified round-trip 7→31→7, and the common symbol grows the state less). It dissolves Huffman’s (dart 006) whole-bit tradeoff on the same integer-array substrate. Note: the real want appears in streaming rANS, whose state must be renormalised (emit bytes) to stay bounded — without it the single state climbs past 253 and loses f64 exactness. A fixed-width integer state + a renormalise primitive is the honest addition; bounded tANS needs neither.