From an existence bound to a construction
The previous entropy unit constructs a prefix code whose expected length is less than one bit above entropy. That is a useful guarantee, but it need not give the shortest possible expected length for the given source. Huffman's construction solves this finite optimization problem by repeatedly joining two least-probable symbols or groups. We will prove why that local choice can occur in a global optimum, rather than treating a short example as proof.
Let a source have distinct required symbols with probabilities and . The probabilities describe one symbol; no independence between successive symbols is needed to minimize the one-symbol objective below. A zero-probability symbol may be omitted only when the coding specification does not require a codeword for that symbol.
Definition 6.1.1
(Binary prefix code, code tree and expected length)
A binary prefix code for symbols assigns to each a finite binary word of length such that no codeword is a prefix of a different codeword. Its expected length is
A code is optimal for if no binary prefix code for the same symbols has smaller expected length. A code tree is a rooted binary tree whose edges to a left child are labeled and to a right child ; a prefix code corresponds to the tree whose leaves are the codewords, and is the depth of the leaf of . A tree is full if every internal node has exactly two children.
Expected length can be read off the tree in a second way, which turns out to describe Huffman's algorithm exactly.
Concept lensCombinatorial
Expected length as a sum over internal nodes
Give each internal node of a code tree the weight , the total probability of the leaves below . Then
The leaf of at depth has exactly proper ancestors, all internal, so is counted times on the right. In Huffman's algorithm each merge creates one internal node whose weight is the merged weight, so the expected length of the Huffman tree is the sum of its merge weights. Collapsing a sibling pair of weights into their parent removes exactly one internal node, of weight , and leaves every other internal weight unchanged.
Trees and the greedy rule
Represent a finite prefix code by its code tree. If and all probabilities are positive, an optimal tree has no internal node with only one child: removing that node and moving its subtree up one edge strictly decreases the weighted length. For the one-symbol case, the empty word has length zero; the receiver must know the symbol count separately, since an empty stream does not reveal it.
Huffman's algorithm starts with a leaf of weight for each symbol. While more than one tree remains, choose two trees of smallest current weight, make them the children of a new parent, and give the parent their combined weight. At the end label each pair of child edges and . The root-to-leaf words are a prefix code. Equal weights may be broken arbitrarily; different choices can give different optimal codes.
Why a greedy merge is safe
The optimality proof has two lemmas. The first places two least probable symbols where the first merge puts them; the second shows that merging them reduces the problem to one with fewer symbols without losing optimality.
Lemma 6.1.2
(Two least probable symbols can be deepest siblings)
Let and . There is an optimal prefix code whose tree is full and in which two symbols of smallest probability label sibling leaves of maximal depth.
Proof
(Existence, then exchange)
Existence. If an internal node has a single child, delete and attach its child subtree in its place. Every leaf below rises one level, so strictly decreases, and the leaves still form a prefix code. Hence every prefix code is beaten or matched by a full tree. A full binary tree with leaves has internal nodes, so there are finitely many full trees with labeled leaves; one of them, , minimizes among them and is therefore optimal among all prefix codes.
Deepest siblings. Let be the maximal leaf depth of and a leaf at depth . Since , is not the root, and since is full, has a sibling . If were internal, a leaf below would have depth greater than . So is a leaf at depth .
Exchange. Suppose some symbol at a leaf outside has , where are the probabilities of the labels at ; say the maximum is attained at . Exchange the labels at the leaf of and at . Since , the change in expected length is
so the tree stays optimal and full. Each exchange strictly decreases , and there are finitely many labelings, so after finitely many exchanges no such exists. Then both labels at are at most every other probability: they are two smallest probabilities , ties included.
The second lemma compares the original instance with the instance obtained by treating the two smallest symbols as one.
Lemma 6.1.3
(Collapsing a least probable pair)
Let , let be two symbols of smallest probabilities , and let be the instance with symbols obtained by replacing by one new symbol of probability . Write for the optimal expected length. Then
and if is optimal for , the tree obtained by giving the leaf two children labeled is optimal for .
Proof
(Expand for one inequality, collapse for the other)
Expanding. Let be any tree for with at depth . Giving the children yields a tree for with expected length . Hence .
Collapsing. By the previous lemma there is an optimal tree for in which are sibling leaves at depth . Replacing them by their parent, now a leaf labeled at depth , gives a tree for with expected length . Hence .
The two inequalities give . If is optimal for , its expansion has expected length , so it is optimal for .
With both lemmas in hand, the theorem follows by induction on the number of symbols.
Theorem 6.1.4
(Optimality of the two-smallest merge)
For a finite source with positive probabilities, the tree produced by this rule minimizes expected length among all binary prefix codes. For the tree consists of the single root and the codeword is empty.
Proof
(Induction on the number of symbols)
For every word has length at least zero, so the empty word is optimal, and Huffman's algorithm returns the root alone.
Let and assume the theorem for symbols. The first merge joins two leaves of smallest probabilities . From then on the algorithm treats the merged tree as a single item of weight , so its remaining merges are exactly a run of Huffman's algorithm on , with the same tie choices. That run produces a tree for , and the final tree for is with the leaf expanded into . The instance has positive probabilities summing to one, so is optimal by the induction hypothesis, and the collapsing lemma shows its expansion is optimal for . Both lemmas hold for any choice of two smallest probabilities, so the proof does not rely on a particular tie-breaking rule. ∎
Proof X-ray
Where each ingredient enters the induction
Finiteness is used once, to guarantee that a minimizing full tree exists; without it, the exchange step would have no optimum to modify. Positivity makes the removal of a unary node a strict improvement, so every optimum is full; the later steps only need that some optimum is full, which survives zero weights because the removal never increases .
The non-obvious move is the exchange. It does not say every optimal tree has as deepest siblings; it modifies one optimum until it does. That single tree supplies the collapsing inequality , while expansion of an arbitrary tree supplies the reverse inequality. Neither direction alone would show that Huffman's tree is optimal.
The induction closes because the reduced instance is again a source with positive probabilities summing to one, now with symbols, and because Huffman's run on after its first merge is literally Huffman's run on . A rule that does not reduce to the same rule on a smaller instance, such as the top-down splitting in the counterexample below, gets no help from this argument.
The proof is about the tree; the cost of building it depends on the data structure that holds the current trees.
Proposition 6.1.5
(Running time with a binary heap)
Assume unit-cost comparison and addition of weights. With the current trees kept in a binary-heap priority queue keyed by weight, Huffman's algorithm on symbols performs merges and heap operations after building the heap, in time overall.
Proof
(Counting heap operations)
Building the heap of leaves takes time by bottom-up heapification. Each merge reduces the number of trees by one, so there are exactly merges. Each merge uses two extract-min operations and one insertion, each costing because the heap never holds more than items, and creating the parent costs . The total is . A final traversal of the nodes computes all depths in time; writing every codeword out explicitly costs bit operations, which can be of order for a very skewed source.
Exact rational weights and their encoding can require additional bit-complexity analysis. A naive implementation that repeatedly sorts or scans the active trees may use a different number of operations.
Work through a four-symbol source
Worked example 6.1.6
(Four symbols with distinct probabilities)
Take probabilities for . Merge and to weight ; the two smallest are now this group and , both , so merge them to weight ; then merge with . One valid labeling is
Their lengths are , so bits per symbol. The merge weights give the same value: . The entropy is approximately bits. By contrast, independently rounding upward gives lengths and expected length . Both methods yield prefix codes; the entropy construction's near-optimal bound does not claim its particular lengths minimize .
A decoder follows edges until it reaches a leaf, emits that symbol, and returns to the root. For example, decodes as , namely . This assumes a known code tree and a complete valid encoded bitstream. Communicating the tree, framing messages and handling corrupted bits are additional costs or problems.
The second example shows what ties can and cannot change.
Worked example 6.1.7
(Ties that change the length profile)
Take for . The first merge is forced: give . Now three trees weigh , namely , and .
If we merge with , the weights become ; merging with gives , and the root joins it to . The lengths are and .
If instead we merge with , the weights become ; merging with gives , and the root joins it to . The lengths are and .
Both runs are valid, both are optimal by the theorem, and their expected lengths agree, but the multisets of lengths differ: the longest codeword has four bits in one and three in the other. Exchanging left and right edge labels alone changes codewords without changing any length. Optimality concerns expected length, not a unique bit assignment or a unique length profile.
The last example covers the two extremes of the comparison with entropy.
Worked example 6.1.8
(A dyadic source and a skewed two-symbol source)
For the merges have weights , and , so bits, with lengths . Here every , so equals the entropy bits exactly.
For with the only merge produces lengths , so bit, while
Huffman's code is still optimal: every prefix code for two required symbols has both lengths at least one. The gap of almost one bit is the price of coding one symbol at a time with whole-bit lengths, not a failure of the greedy rule.
Common mistakes
A plausible alternative builds the tree from the root downward instead of from the leaves upward.
Counterexample mode
Balanced top-down splitting is not optimal
Claim: sort the symbols by probability, split the list into two contiguous parts of as nearly equal total probability as possible, give the parts first bits and , and recurse; the result is optimal. Take for . The top split is with totals and ; the other splits give differences and . Then splits as , with difference against . The lengths are and . Huffman merges , , , and finally , giving lengths and . The top-down rule has no exchange-and-collapse argument behind it; optimality is guaranteed for the bottom-up merge of two smallest weights.
The other two errors concern how the merge rule is applied and what its optimality promises.
Common mistake
(Chaining each new group with the next symbol)
In the four-symbol example the merged group happens to be joined with the next symbol every time, but that is not the rule. Merged weights go back into the pool. For four symbols of probability , chaining gives lengths and , whereas Huffman merges the two pairs separately and gives lengths and .
Common mistake
(Optimal on average is not shortest for every message)
Huffman's code minimizes the expected length per symbol. Particular messages can be longer than under another code: with the four-symbol code, takes bits, while a fixed two-bit code takes . On average the Huffman code still wins, with against bits per symbol.
Exercises
Quick check
(For probabilities , perform the merges and find the expected length.)
Solution · Answer
Merge the two weights, then merge with . The lengths are and bits, which equals the entropy because the source is dyadic.
Quick check
(Why does a single-symbol source have expected length zero under the empty-word convention, and what extra information does decoding need?)
Solution · Answer
Its only leaf is the root, so its word has zero bits. The receiver needs an independently specified number of symbols; an empty stream alone does not reveal that number.
Quick check
(For the four-symbol example, decode using the displayed code.)
Solution · Answer
Parse , obtaining .
Quick check
(Suppose two symbols with probabilities are assigned depths . Calculate the change in expected length if their labels are exchanged.)
Solution · Answer
The new minus old length is . Moving the smaller weight deeper cannot increase the objective.
Further reading
MIT OpenCourseWare: Huffman Codes and CMU: Introduction to Data Compression discuss optimal prefix coding.