Motivation
A prefix code removes ambiguity from concatenated binary descriptions, but it does not by itself choose economical lengths. Giving common symbols short descriptions sounds plausible; proving that a particular greedy tree is best requires more than that intuition. We will identify a sibling pair that some optimum must contain, contract it, and solve a smaller problem.
The resulting algorithm is Huffman coding. Its output minimizes average length among binary prefix codes for a specified finite probability distribution. That statement does not minimize maximum length, guarantee a unique tree, or account for the cost of learning and transmitting the distribution. We will also distinguish lossless source compression from correction of channel errors.
Single-symbol descriptions have integer lengths, so their average can remain visibly above entropy. Encoding known-size blocks changes the distribution being coded and reduces the excess per original symbol. The argument will prove the rate claim and expose the exponential block alphabet, rather than presenting a large existential codebook as an efficient universal compressor.
Definitions
Definition 3.2.1
(Prefix code, trie and average length)
Let symbols have probabilities summing to one. A binary prefix code assigns finite bit strings so that none is a prefix of another. Write and . Its trie is the rooted tree whose edges carry bits and whose symbol strings are leaves. If , the empty string is allowed and has length zero; parsing then requires the symbol count or other framing information.
Definition 3.2.2
(Full binary tree and node weight)
For , a full binary tree has exactly two children at every internal node and its leaves carry the symbols. A leaf's depth equals its code length. The weight of a node is the sum of probabilities of all leaves below it. Swapping symbols changes the weighted cost but not the prefix property.
The entropy is . The preceding prefix-code chapter proved Kraft's inequality and its converse: integer lengths have a binary prefix realization exactly when . We use that proved construction, not an assumed coding theorem. All algorithmic weight comparisons below are exact; a bit-complexity implementation uses positive rational probabilities in binary representation.
Theorem/proposition
Theorem 3.2.3
(The Huffman merge rule is optimal)
Repeatedly merge two least-weight current nodes into a parent whose weight is their sum. Start with the symbol probabilities and finish with a single root. Label sibling edges zero and one in either order. The resulting code minimizes among all binary prefix codes for the given positive probabilities. Ties may be resolved arbitrarily.
Theorem 3.2.4
(Entropy bounds and exact equality)
For the optimal average length ,
Equality holds exactly when every is a power for nonnegative integers . For a one-symbol source the optimum and entropy are both zero.
Theorem 3.2.5
(Independent blocks approach entropy)
For an independent identically distributed source with this distribution, Huffman coding of the possible length- blocks has expected block length satisfying
The source is recovered exactly from the block codewords with known block framing. This theorem does not assert efficient construction in the block length, nor does it handle arbitrary dependent sources using the same product probabilities.
Proof sketch or proof idea
Reduce the optimization to full finite trees
Proof
(Reduction to finitely many full trees)
Start with any prefix trie for finitely many symbols. Remove branches containing no symbol. If an internal node has only one child, contract that edge. All descendant codewords shorten by one and remain prefix-free, so their positive total probability makes the average length strictly decrease. Repeating produces a full tree with exactly leaves.
A full tree with leaves has internal nodes: count edges both as twice the internal-node count and as total-node count minus one. Therefore its deepest leaf has depth at most . There are only finitely many such tree shapes and symbol assignments. An optimum exists among them, and no nonfull trie can improve it. This finite reduction avoids assuming without proof that an infimum of real weighted lengths is attained.
Put the two least probable symbols at a deepest sibling pair
Proof
(Greedy choice and optimal substructure)
Choose a deepest leaf. Its sibling must also be a leaf: an internal sibling would have a descendant still deeper. Let be two least probable symbols. Some optimal full tree can place them at these sibling positions.
Indeed, if currently has depth and a symbol occupies the chosen depth- position, swapping them changes cost by . Since the tree was optimal it remains optimal. Next swap into the other deepest sibling position; the same inequality applies and does not move . Ties cause zero changes and create no difficulty.
Contract these sibling leaves into a single symbol of probability . The cost drops by exactly , because both symbols lose one bit and every other length stays fixed. The contracted tree must be optimal for the merged distribution. Otherwise replacing it by a cheaper merged tree and expanding the two children again would improve the original optimum.
Conversely, take any optimal merged tree and expand its merged leaf into the two original children. Its cost is the merged optimum plus , the same as the original optimum just identified. Thus the greedy first merge is safe. Induction on the number of symbols proves the full algorithm, with the one-symbol empty tree as the base case.
Proof X-ray
What the exchange and the contraction each prove
The proof has two moves that answer different questions. The exchange step uses only and ; it shows that some optimum, not every optimum, has the two least probable symbols as deepest siblings, and ties make the cost change zero rather than negative. The existence of a deepest sibling pair uses fullness, supplied by the earlier reduction: in a nonfull trie a deepest leaf could be an only child.
The contraction step is where optimal substructure enters. Merging the siblings lowers the cost by exactly , an amount independent of the rest of the tree, and this constant shift lets optimality pass in both directions between the original and the merged instance. Induction on closes the argument; later merges act on subtree weights rather than on original probabilities, which is why the exchange step must be reapplied to each smaller instance.
The exchange-and-contraction pair is what makes the greedy rule safe; a plausible greedy rule without it can fail.
Counterexample mode
A balanced top-down split is not optimal
Claim: splitting the sorted symbols into two groups of nearly equal total probability, and recursing, gives an optimal prefix code. For probabilities , the most balanced first split is against , with totals and . Splitting the second group as against gives lengths and
Huffman merges , , and , with merge-weight sum ; its lengths are . The balanced split is therefore not optimal. The repaired statement is the theorem: merging two least-weight nodes from the bottom up is optimal.
Certify the average length by merge weights
Proof
(Merge weights and implementation cost)
The sum of all internal-node weights equals . Each leaf probability is counted once for every internal ancestor, and the number of those ancestors is its depth. In a Huffman construction the internal-node weights are exactly the weights created by the merges. Adding the merge weights therefore gives an independent cost certificate without listing every codeword.
A min-priority queue selects the two least weights and inserts their sum in logarithmic time per merge, for weight comparisons and tree nodes. This counts exact operations, not arbitrary-precision comparisons at zero cost. For rational probabilities, take the product of the input denominators as a common denominator . Its binary length is at most the sum of their input lengths. All node numerators are nonnegative integers at most , so arithmetic and comparisons have polynomial bit cost in the input size.
Writing all explicit bit strings can itself need quadratic total output length: there are leaves and each depth is at most . The tree representation avoids treating that output cost as part of the heap comparison count. No probability estimation or codebook transmission cost has been included.
Use Kraft and divergence to locate the optimum
Proof
(Kraft’s inequality and divergence)
For an arbitrary prefix code put and . These form a positive distribution. Nonnegativity of the previously proved divergence gives
Hence . Equality throughout requires and . Conversely, if the probabilities have those powers, Kraft's converse supplies the corresponding prefix lengths, with average exactly entropy. Huffman optimality then forces the same average.
For the upper bound use Shannon lengths . Their Kraft sum is at most , and each length is strictly smaller than . A prefix code with those lengths therefore has average strictly below . The Huffman optimum is no worse. The bound compares average lengths; it does not say Huffman uses these particular rounded lengths.
Change the symbol alphabet to known-size blocks
Proof
(Entropy of independent blocks)
For an independent block its probability is . Expanding the logarithm and summing over all blocks yields : the contribution of each coordinate is one copy of , since all other coordinate probabilities sum to one. Apply the just-proved one-alphabet bounds to this block distribution and divide by .
The construction is exact and prefix-free at the block level. The decoder walks the block-code tree until a leaf, emits that leaf's symbols and returns to the root. An incomplete final block needs padding and a recorded original length, or another separately specified convention. These framing costs are not silently zero for finite files. Also the list of possible blocks has size , so a direct Huffman construction is generally exponential in even though its excess rate tends to zero.
Worked examples
Worked example 3.2.6
(Read the optimum from three merges)
For probabilities , merge and into , then the two nodes into , then and into one. The sum of merge weights is . One code is in decreasing probability order, whose weighted lengths also give . The entropy is about , so the gap is positive and less than one. The greedy proof establishes optimality; merely observing that common symbols have shorter words would not.
Worked example 3.2.7
(Dyadic equality and its integer constraint)
For probabilities , the code has average , exactly the entropy. By contrast, three equiprobable symbols have optimal lengths one, two and two, giving average , whereas the entropy is . No three integer code lengths can give equality with these probabilities, because is not a reciprocal power of two. Any of the tied symbols may receive the shorter word.
Worked example 3.2.8
(Two-source-symbol blocks improve the rate)
For a binary source with probabilities , individual-symbol prefix coding costs one bit per symbol. Two-symbol blocks have probabilities . Their Huffman merge weights are , so the block cost is , or per original symbol. This is closer to entropy, about , while remaining above it. The gain uses a four-leaf block alphabet and independence; it does not arise from changing the already optimal two-leaf single-symbol tree.
Counterexamples and misconceptions
Even among optimal codes, the tree itself is not determined.
Counterexample mode
An optimal average need not determine the shape
For probabilities , a tied Huffman merge can produce four depth-two leaves, or depths one, two, three and three with the probability- symbol at depth one. Both averages are two. Thus an optimal average does not fix the maximum length or a unique tree. A length-limited coding problem adds a different constraint and needs another analysis.
Common mistake
(Zero-probability symbols change the problem)
Positive probabilities were an explicit hypothesis. If a zero-probability symbol is still required to have a distinct prefix description, it can affect the lengths assigned to the positive symbols. For example, probabilities one and zero still require two nonempty codewords if both labels must be decoded; deleting the impossible symbol permits the empty word and average zero. State which alphabet is being encoded before removing zero terms.
Common mistake
(Prefix-free is not error-correcting)
Prefix freedom is also not error correction. Flipping a transmitted bit can choose another branch and disrupt subsequent symbol boundaries. Entropy optimality under a source model supplies no distance guarantee, authentication or protection against such changes.
Practice
Quick check
(For probabilities , find Huffman merge weights and the optimal average.)
Merge equal weights in pairs.
Solution
Merge the four eighths in pairs to obtain two quarters, then merge them into one half, then merge the two halves. The internal weights are , summing to two. The lengths are one for the half-probability symbol and three for each eighth, also giving average two. These are the negative base-two logarithms of the probabilities, so entropy equality confirms the value.
Quick check
(Why does assigning the least probable symbols deepest justify only a first merge, rather than every later greedy step automatically?)
Ask what the smaller instance must satisfy after the first merge.
Solution
The exchange step establishes an optimal original tree with the chosen siblings. Only the contraction argument proves that its remaining tree solves the merged distribution optimally and that any optimal merged solution can be expanded back. Induction then legitimizes all later merges, whose weights are subtree sums rather than original probabilities.
Quick check
(Explain how a full tree can have maximal depth and what that says about writing all codewords.)
Count internal nodes on a root-to-leaf path.
Solution
A full tree has internal nodes and a root-to-leaf path cannot use more than all of them. A comb-shaped full tree attains depth . Summing the lengths of explicit strings can therefore be quadratic even though the tree has only linearly many nodes; the priority-queue comparison bound does not include that whole output.
Quick check
(For block length , how large must be to make the proved excess rate less than bit per symbol? What computational limitation remains?)
Use the excess bound .
Solution
The strict bound is excess less than , so already gives excess strictly below . The block alphabet has possible entries, which can make direct construction and storage impractical. A small excess theorem is not a practical complexity guarantee.
Quick check
(A dependent binary source alternates deterministically between zero and one after an initial fair bit. Why does the product-distribution block proof not apply?)
Compare the joint law of a block with the product of its marginals.
Solution
Each coordinate has a fair marginal, but a length- block has only two possible alternating words, each with probability one half. Its joint entropy is one bit, not bits. The independence step replacing joint probabilities by a product and entropy by a sum is false here. Coding the actual block distribution is a different, well-defined problem.