One Bit Too Many
Huffman coding is provably optimal and famously within one bit of entropy. On the right source that one bit is a twelve-fold overhead.
What it is
A source that emits the same symbol 99% of the time. Its entropy is 0.080 bits per symbol. Huffman coding spends 1.000.
The upper panel draws every code word as a column. Width is how often that symbol occurs, the blue block is how many bits it deserves (−log₂p), the red line above is how many it gets. The red area is the waste.
The lower panel is what happens when you code several symbols at a time instead of one. Tap to hold.
How it works
Standard Huffman: merge the two lightest nodes until one remains, then read off code words by walking down.
The tests check the things that make it a code (prefix-free, Kraft sum exactly 1, round-trips, commonest symbol gets the shortest word) and the thing that makes it good (never below entropy, never a whole bit above it).
Blocking is the interesting part. Group the text into k-character chunks, treat each chunk as a single symbol, build a code for those. The per-symbol cost is the per-block cost over k.
What surprised me
“Within one bit of entropy” is the line everyone remembers about Huffman, me included, and I had it filed under tight. It’s tight in absolute terms and worthless in relative ones.
| block size | bits per symbol | over entropy | distinct blocks |
|---|---|---|---|
| 1 | 1.0000 | 1151% | 2 |
| 2 | 0.5147 | 544% | 4 |
| 4 | 0.2722 | 241% | 11 |
| 8 | 0.1566 | 96% | 39 |
| 12 | 0.1214 | 52% | 80 |
| 14 | 0.1114 | 39% | 106 |
Twelve times the ideal size, and the guarantee is fully satisfied. 1.0 really is within one bit of 0.08. The bound is on the difference, nobody promised anything about the ratio, and when entropy is far below one bit the difference is the whole story.
For contrast, the same code on ordinary English text: entropy 4.193 bits per character, Huffman 4.240, an overhead of 1.1%. Same algorithm, same guarantee, a thousandfold difference in how much it matters. Huffman’s reputation was earned on sources like the second one.
The fix is blocking, and the second surprise was how slowly it works. The overhead falls like 1/k, so halving it means doubling the block, and doubling the block roughly doubles the number of distinct symbols needing a code word.
At blocks of 14 I am still 39% over the entropy and already carrying 106 code words for a source with two symbols in it. To get within 5% I’d need blocks of about 100 and a code book too large to be worth having.
That’s a fairly complete argument for arithmetic coding, arrived at from the wrong end. Huffman isn’t beaten by a cleverer tree. No tree can spend a fraction of a bit, and the only way to buy fractions with whole bits is to make the symbols so large the fraction goes small next to them.
What I would do next
Implement arithmetic coding on the same source and check it lands within a fraction of a percent of 0.080 with no block structure at all.