Huffman coding

A source emits five symbols with probabilities 0.25, 0.25, 0.20, 0.15 and 0.15. A fixed-length code assigns every symbol a three-bit string, because two bits name only four strings, and therefore consumes 3 bits per symbol, while a Huffman code consumes 2.30 bits on average; the entropy of the source is 2.2855 bits [S:36:111]. The difference between the code and the entropy is 0.0145 bits per symbol.

How do you construct the shortest code? You assign the most probable symbols the shortest strings, and you ensure that no string is the beginning of another, so that a decoder can determine where each symbol ends. That is the central idea, and the remainder of this section converts it into a procedure and explains why the procedure cannot be improved. !Each symbol's ideal length log${}_2(1/p)$ against the whole number of bits the code gives it. c needs 2.32 bits and gets 2, a shortfall of 0.32; d and e need 2.74 and get 3, an excess of 0.26 each. Weighted by probability the shortfall and the excesses nearly cancel, leaving an average of 2.300 bits against the entropy floor of 2.2855, a gap of 0.0145 bits. Status: re-simulated.

Two rules. A prefix code is a code in which no codeword is the beginning of another codeword. That property lets a decoder read a stream from left to right without separators, because when the decoder sees a complete codeword it emits the corresponding symbol and starts again. A code without the property would force the decoder to look ahead and guess where each symbol ends, which is exactly the ambiguity that the prefix condition removes. !The stream 0110111 read from the left. The decoder takes 01 and emits c, then 10 and emits b, then 111 and emits e, giving cbe. No codeword is the start of another, so the first complete match is the only possible reading. A code that also gave 0 to a symbol would have to choose between 0|110|111 and 01|10|111 before it could emit anything. Status: re-simulated.

A Huffman code is the prefix code you obtain by repeatedly merging the two least probable symbols, and it is optimal among codes that encode one symbol at a time [S:36:114]. No other prefix code has a smaller average length for the same source; the proof is an exchange argument: it swaps a deep leaf with a more probable symbol and shows that the average cannot rise.

Picture the code as a tree. Each symbol sits at a leaf, the end of a branch, and the root is the single starting point. The construction proceeds backwards from the leaves. Start with each symbol as a leaf, merge the two least probable leaves into a new leaf whose probability is their sum, and repeat until one leaf remains. Then read the tree from the root, where each left branch adds 0 and each right branch adds 1 [S:36:114].

A deeper leaf costs more bits, and the symbol that occurs least can afford the longest string, so the two least probable symbols must sit at the bottom of the tree. Merging those two leaves gives them the same suffix, the same tail of the codeword, and postpones the choice between them to the final bit. Any other choice would move a longer codeword onto a more probable symbol, which raises the average length [S:36:114].

Worked example. Take the five symbols a, b, c, d and e with probabilities 0.25, 0.25, 0.20, 0.15 and 0.15. Merge d and e into a leaf with probability 0.30, then merge c and a into a leaf with probability 0.45; merge b with the de leaf, giving 0.55, and finally merge the two remaining leaves, 0.45 and 0.55, into the root.

An average length weights each codeword length by the probability of its symbol, so the three short codewords contribute two bits and the two long ones contribute three:

$$L=2(0.25+0.25+0.20)+3(0.15+0.15)=2.30$$

The average is 2.30 bits, while the entropy is 2.2855 bits, so the code is 0.0145 bits above the floor and no prefix code for this source can do better.

Where the extra bit comes from. The ideal length for a symbol with probability p is ${\log }_2(1/p)$, which is rarely a whole number. A prefix code must use whole bits, so it cannot match every ideal length: in the table above, c gets 2 bits where its ideal is 2.32, and d gets 3 where its ideal is 2.74. The shortfall for c and the excess for d partly offset, and rounding every ideal length up would cost less than one extra bit, so the average stays below the entropy plus one.

Decoding is also straightforward in practice: take the string 0110111, and the decoder reads 01 and emits c, then 10 and emits b, then 111 and emits e, so the result is cbe. Since no codeword is a prefix of another, the decoder never has to guess where a codeword ends.

The method costs four things. The extra bit can dominate when the entropy is near one bit per symbol, and Huffman ignores the context: it gives each symbol one codeword no matter which symbols came before, so it cannot use the predictability of text [S:36:113]. It is optimal only among symbol codes, and for many applications a coder that handles blocks or contexts performs better [S:36:113]. It also requires the probabilities in advance, so a changing source forces a new tree, and recomputing the tree for every change is correct but expensive. Sending the tree to the decoder costs bits of its own [S:36:113].

The formal statement. Let a source have probabilities $p_1,\dots ,p_n$ on an alphabet of n symbols. A binary prefix code assigns a string to each symbol so that no string is the beginning of another. If $l_i$ is the length of the string for symbol i, the average length is $L={\sum }_i{p}_i{l}_i$. The Huffman procedure returns a prefix code whose L is minimal among all prefix codes for that source, and among all uniquely decodable codes as well [S:34:235].

The derivation. The proof rests on one exchange. Take an optimal tree and look at its deepest leaves, which come in a sibling pair. If the two least probable symbols are not that pair, swap the least probable symbol with one of the deep leaves. The swap moves the rarer symbol deeper and the more probable symbol shallower, so the average length cannot increase [S:1:186]. A second swap does the same for the second least probable symbol.

Now the two least probable symbols are siblings at maximum depth. Contract that sibling pair into one leaf whose probability is their sum. Any code for the contracted source extends to a code for the original source by adding one bit to each of the two symbols, and the average lengths differ by exactly the sum of their probabilities. The problem therefore reduces to a smaller alphabet with the same structure. Repeating the argument proves that the greedy merge is optimal, by induction on the alphabet size. The induction is the step this layer states rather than writes out, because it repeats the exchange verbatim.

The edge case. Ties break the uniqueness of the answer, not its optimality. When several symbols share a probability, different merge orders produce different trees and different individual codewords, while the average length stays the same [S:1:185]. A one-symbol alphabet is the degenerate case: the tree is a single leaf, the empty string is the code, and the average length is zero. L1's sentence that every symbol gets a string fails there, and the entropy is zero as well, so the bound still holds.

What L1 hid, and why that was safe. L1 called Huffman "the shortest code" and left the qualifier implicit. The optimum is over codes that encode one symbol at a time and use whole bits. Drop the whole-bit restriction and arithmetic coding gets within two bits of the information content of the entire message, not within one bit per symbol [S:36:127]. L1's qualifier was safe because the section compared symbol codes only.

Where the analogy breaks. The tree picture suggests that you can build it from the root by splitting the alphabet into two nearly equal halves. That greedy top-down method is not optimal. MacKay gives a seven-symbol source where the balanced split costs 2.53 bits and Huffman costs 1.97 [S:36:112]. The intuition that probable symbols deserve short strings is correct; the construction has to run from the leaves upward.

Original sources. Huffman developed the algorithm in 1951 as a PhD student at MIT, solving a problem Fano had posed to his information theory class [S:1:184]. The later journal publication is a separate fact and is not on that page. MacKay states the algorithm on p.99 and gives the exchange proof in the solution to Exercise 5.16 on pp.105–106: swapping a deepest leaf with a more probable symbol changes the expected length by $(p_a-p_c)(l_c-l_a)\le 0$, so the two least probable symbols may be taken as maximum-depth siblings [S:36:111] [S:36:118]. Polyanskiy and Wu give the theorem in the same form and note that it holds among all uniquely decodable codes, not only prefix codes [S:34:235].

An open question. Huffman's optimality is settled for a known distribution. The question he leaves is stated in Polyanskiy and Wu: can a code achieve entropy for a class of sources without knowing which member produced the data, and what redundancy does that cost [S:34:235]? Lempel-Ziv answers the first half for ergodic sources, where it is provably optimal [S:34:236]. What remains open is the price for sources outside that class, such as non-stationary or adversarial sources. A universal code with a proved redundancy bound for such a class, matched by a lower bound, would settle it.

A frontier result. Arithmetic coding drops the integer-length restriction and stays within two bits of the information content of the whole message [S:36:127]. That removes the extra bit that dominates when the entropy is near one bit per symbol. Asymmetric numeral systems appear alongside both in Murphy's list of standard lossless coders [S:62:281].

The cost of the table. Huffman's input is a probability for every symbol, and the decoder needs the same table. In a file format the table travels with the data, so a large alphabet spends bits on the model before it spends any on the message [S:36:113]. Adaptive schemes avoid the header and pay in computation instead.

Why this still matters. A symbol code is a model plus a table. The model decides the probabilities, and the table stores them; both must be right before the merge helps. That split is the reason compression and modelling are one subject.

What to read next. Read MacKay Chapter 5 for the Kraft inequality and the exchange proof [S:36:111], then Chapter 6 for arithmetic coding [S:36:125]. Read Polyanskiy Chapter 10 for the theorem and Chapter 13 for universal codes [S:34:235]. The pair shows why the symbol code is the right first answer and the wrong last one.