Entropy and compression

If you had to encode a stream of symbols as short a bit string as possible, how compact could you make it? The answer depends only on how often each symbol appears. Common symbols deserve short codes; rare ones can afford long ones. And there is a hard floor on how well you can do when each symbol is coded separately with a prefix-free code, independent of any cleverness in your encoder. That floor is Shannon entropy, and it is set entirely by the probabilities.

Watch the readouts. On the default distribution, symbol A shows up 40% of the time, B 30%, C 20%, D 10%. Shannon entropy comes out to 1.846 bits per symbol. That is the average number of bits per symbol that any encoder can hope to reach, computed from the formula H equals the negative sum of p times log base 2 of p over all symbols. It is the theoretical lower bound. Directly underneath it, the figure shows a real Huffman code built from these same probabilities, and the average length of that code, weighted by probability, comes out to 1.900 bits per symbol. Huffman is off by 0.054 bits per symbol from the entropy floor. The gap readout shows this directly, and it is never negative.

Now change the distribution. Drag toward a set of probabilities that are exact powers of one-half, like 0.5, 0.25, 0.125, 0.125, and something clean happens: the gap closes to zero. Huffman meets entropy exactly, both landing at 1.750 bits per symbol. This is not luck. Huffman assigns integer-length codes, and when every probability is already 1 over some power of two, the ideal code lengths are integers to begin with, so Huffman can hit them precisely. Drag to uniform 0.25 each and you get another clean landing: both readouts settle at 2.000 bits, which is exactly log base 2 of 4, the cost of naming one option out of four with no information to exploit. Skew hard toward one symbol, say 0.7, 0.15, 0.10, 0.05, and entropy drops below 1.4 bits per symbol because the outcome is now much more predictable; Huffman rises past 1.4 to about 1.45, and the gap widens past 0.1. The three regimes cover the full picture: Huffman meets entropy when probabilities cooperate, sits above it when they do not, and the size of the gap depends on how far the probabilities are from powers of one-half.

The line the gap traces is not a matter of finding a smarter per-symbol code. Huffman is already optimal in that category: no other code that assigns a fixed bit string per symbol can do better on average. What entropy is measuring is the information content of the distribution itself, in bits, and any per-symbol encoder is stuck rounding those bits up to the nearest integer. That rounding is the whole story of the gap. Compressors that appear to beat this bound do it by refusing to encode one symbol at a time: they code against the lower conditional entropy of a source whose symbols predict each other. Shannon's bound is not beaten; the bound itself is lower for a correlated source. They exploit context between symbols, or they encode long blocks with fractional bit costs. The floor for what you can see here, one symbol at a time with an integer number of bits, is the entropy of the symbol probabilities above.

Honesty notes. The alphabet here is tiny and contrived, four symbols with hand-picked default probabilities. What is real is the math on top: Shannon entropy is computed live from the current probabilities, the Huffman code is built live by the standard algorithm of repeatedly merging the two lowest-probability nodes, and the average code length is a weighted sum over the code lengths the figure actually shows. Moving a slider renormalizes the others proportionally, using a tested function, so the table always sums to 1 without any display trick. And note the scope of the bound. Huffman is optimal among per-symbol prefix codes; the "you cannot beat entropy" limit shown here is the per-symbol limit, not an absolute floor on all compression. Real compressors do better by taking advantage of context and longer-range structure between symbols, which this figure does not model.

Watching the gap close