The optimal code that is beaten

Huffman coding is optimal. The theorem is genuine, the proof is three lines of exchange argument, and it has been in every textbook on the subject since 1952.

An arithmetic coder beats it by a factor of nearly nine on a stream this page will show, and no theorem is violated. Both statements are exactly true, and the way they fit together is a lesson about reading a theorem rather than a lesson about coding.

The claim, in full #

What the theorem says is that among prefix codes that assign a whole number of bits to each symbol independently, no code has a lower expected length than Huffman’s.

Every clause in that sentence is load-bearing, and two of them are the ones that get dropped.

“Prefix code” — no codeword is a prefix of another, so a decoder can read bits until it recognises one and never needs a separator. That is what makes a code decodable without punctuation, and it is what forces whole numbers of bits.

“Each symbol independently” — the code is a fixed table from symbol to bit string, consulted once per symbol.

Neither clause is a technicality. Together they say the cost per symbol is an integer, and an integer cannot be 0.152.

That is the same structure as the bound with a precondition found inside a graph algorithm’s guarantee, and the same structure as in place is a claim found inside “sorts in place”. A quoted result is correct; the conditions under which it was proved have been dropped in transmission; and the dropped conditions are exactly where the interesting behaviour is.

Where it bites #

The gap is entirely in the dominant symbol. It carries 90% of the stream’s occurrences and is overcharged by 0.848 bits on each of them, and $0.9 \times 0.848 = 0.763$, which is very nearly the whole 0.535-bit gap once the other symbols’ bargains are subtracted.

Huffman’s guarantee is $[H, H+1)$, and on this distribution the $+1$ is not slack — it is the answer. When $H$ is 3 the guarantee is worth having, since one bit above three is 33%. When $H$ is 0.115 it is worth nothing at all, since one bit above 0.115 is a factor of nine.

The measurements down the skew:

The right-hand column tracks the second column to three decimal places all the way down. The third column stalls.

Notice which coder loses at the top of the table #

At $p = 0.125$ — a uniform alphabet — Huffman spends 3.000 and arithmetic coding spends 3.002.

Arithmetic coding loses. Not by much, and the reason is worth stating because it is the only honest way to present the comparison: the coder has to flush its interval at the end of the stream, which costs a couple of bits, and its adaptive model spends its first few hundred symbols learning a distribution Huffman was told.

A figure showing arithmetic coding winning everywhere would be a figure with a bug in it, and the gate asserts both halves for that reason: that arithmetic coding beats Huffman by at least 5% on the skewed source, and that it does not beat it by more than 2% on the uniform one. A check that only demanded the win would pass a coder that was cheating.

The escape Huffman has of its own #

The precondition says a whole number of bits per symbol. It does not say what a symbol is.

Code the stream in pairs. The alphabet of eight becomes an alphabet of 64, each pair’s probability is the product of its parts’, and the rounding loss is still at most one bit — but now it is one bit per pair, which is half a bit per symbol. Code in triples and it is a third.

Measured on the skewed source at $p = 0.9$, with $H_0 = 0.7544$:

The gap falls faster than $1/k$ — it should be bounded by $1/k$ and it beats that, because blocking also lets the code exploit the fact that runs of the dominant symbol are common.

At blocks of four the gap is 0.010 bits, which is where arithmetic coding sits. Huffman can reach the floor. The price is in the second column: the alphabet grows as $\sigma^k$, the code table grows with it, and a table of 362 entries for an alphabet of eight is already awkward. At $k = 8$ over 256 symbols it is $2^{64}$ entries, which is why nothing does this in general and why it is a real technique only when the alphabet is tiny.

The escape arithmetic coding takes instead #

Arithmetic coding does not assign codes to symbols at all. It represents the whole message as a single number in $[0, 1)$, narrowing an interval by each symbol’s probability in turn, and emits the shortest binary fraction inside the final interval.

The final interval’s width is $\prod p_i$, so the number of bits needed to name a point inside it is $-\log_2 \prod p_i = \sum -\log_2 p_i$ — the ideal cost, with no rounding anywhere, because no individual symbol ever gets its own codeword to round.

A symbol of probability 0.9 narrows the interval by a factor of 0.9, which costs 0.152 of a bit. Not one bit and not zero — 0.152, accumulating with the next symbol’s until enough have gathered to emit a whole one.

The coder implemented here is the integer version, with the standard pending-bits handling for the carry, and it is checked by round trip rather than by inspection. The encoder’s total is required to stay under $2^{16}$ so that range × cum stays inside a double’s exactly-representable integers, and that bound is asserted rather than assumed: losing precision there produces a coder whose output does not decode, which is the failure the round-trip check exists to find.

The interval, worked #

Start with $[0, 1)$ and an alphabet where a has probability 0.9 and b has 0.1, laid out in that order.

Coding a narrows the interval to $[0, 0.9)$. Coding another a narrows it to $[0, 0.81)$. A third gives $[0, 0.729)$. Coding b at that point gives $[0.6561, 0.729)$, of width 0.0729.

To transmit the message it is enough to name any number inside the final interval, and a binary fraction inside an interval of width $w$ needs about $-\log_2 w$ bits. Here $-\log_2 0.0729 = 3.78$, which is exactly $3 \times 0.152 + 3.32$ — the three cheap symbols and the one expensive one, added up with no rounding at any step.

A Huffman coder on the same four symbols spends four bits, one per symbol, and cannot spend fewer because it has only two codewords and both are one bit long.

The saving is not that arithmetic coding is cleverer about any individual symbol. It is that it never has to finish a symbol. A cost of 0.152 bits is carried in the width of an interval until enough of them accumulate to justify emitting a bit, and the accumulation is what a symbol boundary destroys.

The carry, which is where implementations go wrong #

The infinite-precision version above is not implementable, and the integer version has one genuinely awkward case.

As the interval narrows, its top bits stop changing and can be emitted and shifted out — that is the renormalisation that keeps the arithmetic in range. The awkward case is an interval like $[0.4999, 0.5001)$: straddling a half, so the leading bit is not yet decided, and narrowing without ever resolving.

The standard answer is pending bits. When the interval sits inside the middle quarter, the encoder records that one bit is owed without knowing its value, halves the interval about the midpoint, and continues; when the leading bit is finally resolved it emits that bit followed by the opposite bit once per pending count. The encoder here does exactly this, and the count it keeps is what the round-trip check is holding to account.

It is worth naming because it is the part that cannot be checked by inspection. An encoder that mishandles the carry produces output that is shorter — bits it owed and never paid — and decodes to something else. Nothing but a round trip finds it, which is why the round trip is a gate assertion rather than a test somebody ran once.

Why real Huffman codes transmit lengths #

One more implementation fact, because it decides what the header in the next essay costs.

A Huffman code is normally shipped as a canonical code: the lengths are sent, and both sides rebuild the actual bit patterns from them by a fixed rule — sort by length, then by symbol, and assign consecutive integers. Two coders that agree on the lengths agree on the code, so nothing but the lengths has to cross the wire.

That is a real saving. Sending the tree costs its structure; sending the lengths costs about five bits per symbol present, which is what huffmanEncode’s header charges here. It is also what makes ties in the construction harmless in practice: two different Huffman trees with the same length multiset produce the same canonical code.

Every coder here is a predictor #

There is a way of reading all of this that makes the rest of the field one subject rather than three.

A coder spends $-\log_2 p$ bits on a symbol it assigned probability $p$. The only way to spend fewer bits is to have assigned a higher probability — which is to say, to have expected the symbol more. So every compressor is a predictor, and its bit count is the scorecard of how well it guessed.

Huffman’s predictor is a frequency table: it expects each symbol at its overall rate and nothing else. Arithmetic coding uses the same predictor and merely spends its verdicts more precisely, which is why the two agree on the uniform stream and differ only where the predictions are lopsided enough that rounding matters.

Read that way, this essay is about the spending and the rest of the field is about the predicting. The next essay changes the predictor from “how often does this symbol occur” to “how often does it occur after these three”, and the floor falls by a factor of four; the one after that replaces the predictor with a window of recent text and no probabilities at all. Neither of them improves on arithmetic coding’s spending, because there is nothing left to improve — 0.763 against a floor of 0.759 is the end of that road.

The staircase, three ways #

The gap between Huffman and the entropy is a function of the skew, and the skew is one axis of three.

The third variation is the control: the same alphabet, the same skews, a quarter of the stream. It is the one that separates what is measured here from what is computed.

Then why did anything ship Huffman #

Two reasons, and only one of them is technical.

Speed. A Huffman decoder is a table lookup and a shift. An arithmetic decoder is a multiply, a divide and a data-dependent renormalisation loop per symbol. On the hardware of the 1990s the difference was an order of magnitude, and DEFLATE — which is gzip, zip, PNG and HTTP’s Content-Encoding — chose Huffman for it.

Patents. Arithmetic coding was encumbered from the late 1970s to the early 2000s, and the encumbrance is the reason JPEG’s arithmetic mode exists in the standard and in almost no decoder. That is not an algorithmic fact and it shaped which algorithms a generation of programmers ever saw.

Both reasons expired. What replaced Huffman is not arithmetic coding either — it is asymmetric numeral systems, which reaches the same fractional-bit precision with table lookups instead of arithmetic, and which is in Zstandard, in LZFSE and in AV1. The trade that made Huffman the right answer for thirty years was decoder speed against bits, and ANS took the trade off the table.

The test is whether any symbol passes a half #

The staircase can be read off a single number, which is worth having because it turns “is Huffman good enough here” from a benchmark into an arithmetic check.

A symbol of probability $p$ is worth $-\log_2 p$ bits and is charged at least one, so it is overcharged by $1 + \log_2 p$ — a quantity that is positive exactly when $p > \tfrac12$. Weighted by how often the symbol arrives, the loss it forces is at least

$$p\,(1 + \log_2 p)$$

At $p = 0.9$ that is 0.763 bits per symbol, which is very nearly the whole measured gap of 0.535 once the other symbols’ bargains are netted off. At $p = 0.5$ it is exactly zero. Below a half it is negative, which is to say the constraint is not binding at all and whatever gap remains is ordinary rounding, spread across the alphabet and small.

So the diagnostic is one line: find the most frequent symbol’s share, and if it is under a half, a prefix code is close to the floor. No coder has to be run, no stream has to be compressed, and the answer covers the whole family of prefix codes rather than any particular one. Every plate in this essay is that inequality drawn.

Blocking only the symbol that needs it #

Blocking works and its cost is an alphabet of $\sigma^k$, which is why nothing does it in general. The section above says where the loss actually is, and it points at a cheaper version.

The loss is concentrated in one symbol. So block that symbol and leave the rest alone: replace each run of the dominant symbol by a single token naming the run’s length, and code the resulting stream of tokens and ordinary symbols with an ordinary prefix code.

The alphabet grows by the number of distinct run lengths rather than by a power. On the skewed source at $p = 0.9$ the mean run is ten and the runs rarely exceed a few dozen, so an alphabet of eight becomes an alphabet of forty or fifty — against 362 for blocks of four, and against $8^4 = 4{,}096$ if every combination had to be represented. And the gain is most of what full blocking bought, because the tokens carry exactly the structure that was being wasted: a run of ten costs one codeword instead of ten.

Two things make this more than a trick. It is what bzip2 does between move-to-front and its entropy coder, for precisely the reason this essay gives — the transform’s output is 70% zeroes, one symbol past a half, and a prefix code overcharges every one of them. And it generalises: where a run length has a known geometric distribution, the token can be coded by a Golomb code whose parameter comes from the run rate, which is a prefix code tuned to the exact shape the dominant symbol produces.

The general form is worth the sentence. Blocking is the escape from the one-bit floor, its cost is alphabet growth, and the growth need only be paid where the floor actually binds — which the inequality above locates exactly.

What this essay is an instance of #

This is filed under what is taught wrongly, and the wrong thing is not the theorem. It is a habit of quoting.

“Huffman coding is optimal” is what gets said. “Huffman coding produces the optimal symbol-wise prefix code for a known distribution” is what is true, and the two differences do all the work: drop the first and arithmetic coding looks impossible; drop the second and the header the next essay is about becomes invisible.

The site has this shape three times now and the three are worth reading together. Quicksort “sorts in place” — in $\Theta(\log n)$ auxiliary space, not $\Theta(1)$. Dijkstra is $O(E \log V)$ — with a precondition on the queue that the pseudocode does not state. Huffman is optimal — among a class of codes that the sentence does not name.

In all three the compressed version is not false, it is incomplete in a direction that hides the interesting case, and the interesting case is where the next algorithm comes from. An arithmetic coder is what somebody built after noticing which clause could be dropped.

There is a practical test for this that costs nothing and is worth applying to any optimality claim: ask what the theorem’s competitors were. Optimal among what? Huffman’s competitors are symbol-wise prefix codes. Comparison sorting’s floor competes among algorithms that only compare. The Bloom filter’s bound competes among structures answering one particular question at one particular error rate. Every one of those answers is a set, and every set has an outside — and the outside is where the improvement is, every time, in all three fields on this site that have a floor in them.