Codes as weighted trees
Suppose distinct symbols have nonnegative weights . We want to assign bit strings to the symbols so that heavily used symbols receive short strings, while keeping every encoded message uniquely decodable from left to right.
Definition 5.1.1
(Prefix code and weighted length)
A binary prefix code assigns each symbol a finite bit string, with no codeword a prefix of another. Its binary trie has a leaf for each symbol, and the depth of the leaf of symbol is the length of its codeword. The weighted length of the code (or of its tree ) is
We minimize this sum over binary prefix codes. If the weights are probabilities, it is the expected number of bits per symbol; if they are counts, it is the total weighted length. The problem assumes the symbol weights are given and says nothing about the cost of transmitting the codebook. The one-symbol convention is excluded here: an application must specify separately whether an empty codeword is permitted.
Why the two smallest weights can be siblings
Definition 5.1.2
(Full binary tree)
A binary tree is full when every internal node has exactly two children.
Every prefix-code tree can be made full. If an internal node has only one child, bypass it; descendant depths decrease by one and, because weights are nonnegative, cost cannot increase. Repeating yields a full tree with the same leaves. For fixed , there are finitely many full tree shapes and symbol assignments, so an optimal full tree exists. In a full tree with leaves there are internal nodes.
Lemma 5.1.3
(Two least weights can be deepest siblings)
Let and be two symbols with for every other symbol . Then some optimal full tree has and as sibling leaves at the maximum depth.
Proof
(Exchanging labels)
Take an optimal full tree. If a lighter leaf is shallower than a heavier leaf, swapping their labels changes the cost by , so it cannot increase it.
A deepest leaf has a sibling that is also a leaf: the sibling exists because the tree is full, and if it were internal it would have a deeper descendant. Let be such a pair of sibling leaves at maximum depth . Swap the labels of and the symbol at . Since has the least weight and is as deep as possible, the cost does not increase. Then swap with the symbol at ; now has least weight among the symbols other than , and again the cost does not increase. After both swaps are siblings at depth , and the cost is still minimal, so the tree is optimal.
Lemma 5.1.4
(Collapsing a sibling pair)
Let be a full tree in which leaves are siblings, and let be obtained by deleting them and treating their parent as a new leaf of weight . Then . Conversely, every tree for the reduced weights in which is a leaf expands to such a tree .
Proof
(One level of depth)
Let the parent have depth . Then and have depth in , so they contribute , while contributes in . All other leaves have the same depth in both trees. Subtracting gives the identity. Expanding a leaf of any tree into two children labeled is the inverse operation.
Theorem 5.1.5
(Huffman's merge rule is optimal)
Repeatedly merge two least-weight current items, replacing them by one item whose weight is their sum, until one item remains. The tree built this way minimizes among all binary prefix codes, whatever fixed rule breaks ties.
Proof
(Induction on the number of symbols)
For the only full tree has two leaves of depth , and the merge builds it.
Let , and let be the two items the first merge combines; they satisfy the hypothesis of the first lemma, because the merge takes two least weights. Let be the tree the procedure builds for the reduced weights (with in place of ); by induction is optimal for the reduced instance, with cost . The tree of the procedure on the original weights is with expanded, so by the second lemma.
By the first lemma, some optimal tree has as siblings. Collapsing them gives a tree for the reduced weights, so and
Since is optimal, is optimal as well.
Proof X-ray
Why a safe first choice suffices
The proof has two halves that use different hypotheses. The exchange half uses nonnegative weights exactly once, to bypass one-child nodes without increasing cost and so reduce to full trees; fullness is what guarantees that a deepest leaf has a leaf sibling at all. The swaps themselves use only the order of the weights: and make the product nonpositive. The collapse half uses no hypothesis on weights: it is an identity about depths.
The key move is to separate choosing from solving. The exchange lemma shows that the greedy choice, putting two least weights together at the bottom, is safe: some optimal tree contains it. The collapse identity then shows that the rest of the problem is the same problem with one fewer symbol, and its cost differs by the fixed amount , so optimizing the rest is exactly optimizing the reduced instance.
The argument closes by induction on , from the two-leaf base case. Ties cost nothing, because the first lemma holds for any pair of least weights, not for a particular one. The place where the argument would fail is the first lemma: merging two items that are not least breaks the inequality , and the merge-order example below pays for it.
Starting from singleton leaves and repeatedly merging the two smallest weights constructs such a tree. The final merge reaches one root; its left and right edges may be labeled and in either order. Each symbol is decoded at its leaf, so no codeword is a prefix of another.
Concept lensCombinatorial
Cost as a sum over internal nodes
A leaf at depth has exactly proper ancestors, all internal. Counting each leaf's weight once for every ancestor gives , summed over internal nodes , where is the total weight of the leaves below . Each merge creates one internal node whose weight is the merged weight, so the cost is the sum of all merged weights. Collapsing a sibling pair removes exactly one internal node, of weight , which is the collapse identity.
Worked examples
Worked example 5.1.6
(A trace of the merges)
Let the weights of be . Greedy merges into weight ; then the two smallest are , giving ; then give . One resulting code is
Its weighted length is . Equivalently, each merge adds its combined weight to the total, giving . Note that is the weight of the root, not the cost.
Counterexample mode
Not every sequence of merges is optimal
Merge weights and first, giving . Then merge the original with this , giving , and finally merge the original of weight with . The merge weights add to , so the resulting valid prefix code costs , not . Directly: has depth , depth , and depth , so the cost is . Being a valid prefix tree alone does not certify optimality: the merges must always take two least weights.
Worked example 5.1.7
(Ties give different optimal trees)
Let the weights be . The first merge combines the two s into weight , leaving three items of weight . If we merge the two original symbols of weight , giving , and then merge with , the merge weights are and every symbol has depth : . If instead we merge the new item with one symbol of weight , giving , and then merge that with the other symbol, the merge weights are again, but the depths are now : . Both trees are optimal, with different codeword lengths.
Worked example 5.1.8
(The smallest instance, with a zero weight)
Let with weights and . There is exactly one merge, of weight , and codewords and with weighted length . A zero-weight symbol still receives a codeword; the cost does not depend on its depth. This is the base case of the induction.
Cost and scope of the algorithm
Proposition 5.1.9
(Running time and space)
With a min-priority queue, the tree for symbols is built with insertions and rounds of two removals and one insertion. With constant-time weight comparisons and additions, this takes time and stored nodes and queue entries.
Proof
(Counting queue operations)
There are initial insertions, and each of the merges performs two removals and one insertion, so there are queue operations in total. Each costs on a heap, giving . The tree has leaves and internal nodes, which is storage.
Emitting all codewords takes additional time proportional to their total printed length, which can exceed . Finite-precision overflow, metadata for a codebook and coding an infinite stream are separate implementation issues.
Common mistakes
Common mistake
(Reading the root weight as the cost)
The weight of the root is the total weight of all symbols, which is in the trace. The cost is the sum of the weights of all internal nodes, here , or equivalently the sum of weight times depth over the leaves.
Common mistake
(Always attaching the next smallest symbol)
Merged nodes compete with symbols in the queue. A comb that repeatedly attaches the smallest unused symbol to the growing subtree is not Huffman's rule. For four symbols of weight the comb has depths and cost , but merging the pairs first gives depths and cost .
Nonnegativity of the weights is used to reduce to full trees, and the next example shows that it cannot simply be dropped.
Counterexample mode
Negative weights break the merge rule
Take weights , which the nonnegativity hypothesis excludes. The merge rule combines and into , then and into , so its cost is . Directly: the unmerged at depth and the others at depth give . But the prefix code with , , is valid and costs , which is smaller. With negative weights deep leaves can be profitable, and bypassing one-child nodes is no longer safe. The repaired statement is the one proved above: weights must be nonnegative.
Exercises with solutions
Quick check
(Can 0 and 01 both be codewords in a prefix code?)
Compare the two strings character by character.
Solution · Answer
No; 0 is a prefix of 01.
Quick check
(What weight replaces leaves of weights and when they are merged, and what does the merge contribute to the weighted length?)
Use the collapse identity.
Solution · Answer
Their parent has weight , and that merge contributes to weighted length.
Quick check
(If two weights tie, must the bit strings of an optimal code be unique?)
Think of swapping the two children of a node.
Solution · Answer
No. Ties and exchanging left and right children can give different optimal codes; the weighted cost stays optimal.
Quick check
(Why may a one-child node be bypassed even when some weights are zero?)
Compare the cost before and after shortening.
Solution · Answer
All weights are nonnegative, so shortening descendant codewords cannot increase the sum; with zero weights it may leave the cost unchanged.