Source Coding: Huffman, Arithmetic Coding and ANS

Lossless compression has a hard limit, and Shannon proved it in the same 1948 paper that defined entropy. Section 9 of A Mathematical Theory of Communication (Bell System Technical Journal, vol. 27) states it as Theorem 9, the fundamental theorem for a noiseless channel: a source of entropy $H$ can be encoded to transmit at an average rate approaching $C/H$ symbols per second over a channel of capacity $C$, and "it is not possible to transmit at an average rate greater than $C/H$."

Read that backwards and it says what every compression engineer needs: you cannot average fewer than $H$ bits per symbol. No cleverness, no new algorithm, no more compute. A tool advertising universal compression of arbitrary data is claiming to beat a theorem.

Everything that follows is about how close a practical coder can get to that floor, and what it costs in speed to get there.

Variable-length codes have an obvious problem. If A is 0, B is 01 and C is 1, then the stream 001 could be AAC or AB. You would need a separator, and separators cost bits.

A prefix-free code solves this: no codeword is a prefix of any other. Now the decoder reads bits until it lands on a codeword, emits it, and starts fresh. No lookahead, no separators, no ambiguity.

prefix-free:      A=0    B=10   C=110  D=111
decode 0101110 -> 0 | 10 | 111 | 0  -> A B D A

NOT prefix-free:  A=0    B=01   C=1
decode 001       -> A A C  or  A B ?

The cost is that short codewords are expensive. Spending 0 on A rules out every codeword starting with 0, which is half of all possible codewords. Codeword lengths trade against each other, and the next step makes that trade exact.

There is a precise accounting rule for those trades. A prefix-free binary code with codeword lengths $l_1, l_2, \ldots, l_n$ exists if and only if

$\sum_i 2^{-l_i} \le 1$

This comes from Leon G. Kraft's 1949 MIT master's thesis, A device for quantizing, grouping, and coding amplitude-modulated pulses. Think of it as a budget: you start with 1.0, and a codeword of length $l$ costs $2^{-l}$. One bit costs half your budget. Three bits cost an eighth.

Brockway McMillan then proved the surprising half, in Two inequalities implied by unique decipherability (IRE Transactions on Information Theory, vol. 2, no. 4, December 1956, pp. 115-116): the same inequality binds any uniquely decodable code, prefix-free or not.

That is the punchline. Giving up prefix-freeness buys you nothing. You may as well take the codes that are trivially decodable.

Given the budget, which lengths should you buy? David Huffman answered it with an algorithm so simple it fits in three lines:

1. Treat each symbol as a leaf node weighted by its probability.
2. Repeatedly remove the two lowest-weight nodes and join them under a new parent whose weight is their sum.
3. Stop at one node. Label left branches 0 and right branches 1, and read each leaf's path as its codeword.

Published as A Method for the Construction of Minimum-Redundancy Codes (Proceedings of the IRE, vol. 40, no. 9, September 1952, pp. 1098-1101), it is provably optimal among prefix-free codes that encode one symbol at a time. Hold onto that qualifier.

The origin is genuinely good. Gary Stix's profile of Huffman in Scientific American (vol. 265, no. 3, September 1991) records that Huffman was a graduate student in Robert Fano's information theory course, offered a term paper instead of a final exam. He worked for months, gave up, and the solution arrived as he threw his notes away.

Take A=0.40, B=0.20, C=0.20, D=0.10, E=0.10. First the target:

H = 0.40(1.3219) + 0.20(2.3219) + 0.20(2.3219)
  + 0.10(3.3219) + 0.10(3.3219)
  = 2.1219 bits/symbol

Now merge the two smallest, repeatedly:

step 1:  D(0.10) + E(0.10) -> DE(0.20)
step 2:  B(0.20) + C(0.20) -> BC(0.40)
step 3:  DE(0.20) + A(0.40) -> ADE(0.60)
step 4:  BC(0.40) + ADE(0.60) -> root(1.00)

Lengths: A=2, B=2, C=2, D=3, E=3. One valid assignment is A=10, B=00, C=01, D=110, E=111.

Kraft: 3(2^-2) + 2(2^-3) = 0.75 + 0.25 = 1.00  (budget fully spent)
L    = 0.40(2)+0.20(2)+0.20(2)+0.10(3)+0.10(3) = 2.2000 bits
gap  = 2.2000 - 2.1219 = 0.0781 bits, 3.7% above the floor

Reading each leaf's path from the root gives its codeword. Note that the tree shape is not unique, but the expected length is:

Huffman assigns whole numbers of bits. When a symbol's ideal length is not close to an integer, that rounding is pure waste, and on skewed sources it is catastrophic.

Take a binary source with probabilities 0.9 and 0.1. Its entropy is 0.4690 bits per symbol. Huffman has two symbols and two possible codewords, 0 and 1, so it must spend exactly 1 bit. That is 2.13 times the theoretical minimum, and no amount of tree-building helps.

Robert Gallager quantified the general case in Variations on a theme by Huffman (IEEE Transactions on Information Theory, vol. IT-24, no. 6, 1978, pp. 668-674): binary Huffman redundancy is bounded above by $p_{max} + 0.086$, where $p_{max}$ is the most likely symbol's probability. Skew raises $p_{max}$, and the bound rises with it.

One partial fix is blocking: code symbol pairs instead of singles. The pair probabilities become 0.81, 0.09, 0.09, 0.01, and Huffman spends 1.29 bits per pair, or 0.645 bits per symbol. Better than 1.0, still well above 0.4690, and the alphabet size squares every time you widen the block.

The real fix is to abandon the one-codeword-per-symbol idea entirely. Arithmetic coding represents the whole message as a single interval inside $[0,1)$, narrowing it by one symbol at a time in proportion to that symbol's probability.

Encode AAB from a source with $P(A)=0.8$, $P(B)=0.2$:

start      [0.000, 1.000)   width 1.000
A          [0.000, 0.800)   width 0.800
A          [0.000, 0.640)   width 0.640
B          [0.512, 0.640)   width 0.128

Any number in the final interval identifies the message. Transmit 0.5625, which is 0.1001 in binary. The interval width is exactly $P(AAB) = 0.128$, so the message costs $\log_2(1/0.128) = 2.97$ bits, its own surprisal, with no integer rounding anywhere.

Jorma Rissanen gave the modern formulation in Generalized Kraft Inequality and Arithmetic Coding (IBM Journal of Research and Development, vol. 20, no. 3, May 1976, pp. 198-203); Witten, Neal and Cleary made it practical in Communications of the ACM, vol. 30, no. 6, June 1987, pp. 520-540. Overhead is roughly 2 bits for the entire message, not per symbol.

Arithmetic coding's problem was never compression rate. It was that maintaining an interval means multiplications and divisions per symbol, and for two decades it also sat under a dense patent thicket.

Jarek Duda's asymmetric numeral systems collapses the two-number interval into a single natural number as the state. In Asymmetric numeral systems (arXiv:0902.0271, 2009) and the follow-up subtitled entropy coding combining speed of Huffman coding with compression rate of arithmetic coding (arXiv:1311.2540, 2013), Duda reports "about 50% faster decoding than [Huffman] for 256 size alphabet, with compression rate similar to provided by [arithmetic coding]."

Two variants matter in practice:

• rANS (range): arithmetic formulas on the state, good for large alphabets.
• tANS (tabled): the entire state transition baked into a lookup table, giving a finite state machine with no multiplications at all.

The licensing turned out differently this time. Duda published ANS without patenting it, and when Google filed US application 2017/0164007 A1 covering an ANS-based coefficient coder, the USPTO rejected all claims and the application was abandoned, a fight the Electronic Frontier Foundation covered in August 2018.

Zstandard is where ANS went mainstream. RFC 8878 (Collet and Kucherawy, February 2021) documents the format and is explicit about the split: "Huffman is used to compress literals, while FSE is used for all other symbols," where "FSE, short for Finite State Entropy, is an entropy codec based on [ANS]." So a production codec runs Huffman from 1952 and tANS from 2013 side by side, each on the data it suits.

Meta's engineering blog announcing zstd in August 2016 claimed it "compresses substantially faster: ~3-5x" at zlib's ratio, and is "almost 2x faster at decompression." The current benchmark published in the zstd repository, on the Silesia corpus and a Core i7-9700K:

Adoption followed the numbers: Linux 4.14 (November 2017) added zstd to Btrfs and SquashFS, and Arch Linux switched its package format from xz to zstd in December 2019, reporting roughly 0.8% larger packages for roughly a 1300% decompression speedup.

The gotcha that catches people: an entropy coder is only as good as the probability model feeding it. Huffman on a well-modelled source beats arithmetic coding on a badly-modelled one every time. The coder collects the gap the model identifies; it cannot find that gap itself.

A current example of exactly that. Zhang et al., 70% Size, 100% Accuracy (arXiv:2504.11651, 2025), observe that the exponent field of BFloat16 neural network weights carries about 2.6 bits of entropy in an 8-bit field. Running plain Huffman coding over those exponents shrinks model weights by around 30%, bit-for-bit lossless. A 1952 algorithm, pointed at a distribution nobody had bothered to measure.