Huffman Coding and the Greedy Merge

A prefix code assigns each symbol a bit string such that no code is a prefix of another. That property makes decoding unambiguous without delimiters: the decoder reads bits until they match a codeword, emits the symbol, and restarts. Huffman’s algorithm builds an optimal prefix code for a known symbol distribution by repeatedly merging the two least frequent nodes in a forest, and the whole argument for why that merge is safe fits in a paragraph. It is one of the few widely deployed algorithms whose optimality proof is elementary.

The cost being minimized

For a code with codeword lengths $\ell_1, \dots, \ell_n$ and symbol probabilities $p_1, \dots, p_n$, the expected number of bits per symbol is

$$ L = \sum_{i=1}^{n} p_i \ell_i $$

Shannon’s source coding theorem gives a lower bound: for any uniquely decodable code, $L \ge H(p)$, the entropy of the distribution in bits. The bound is not generally attainable with integer codeword lengths, and Huffman coding achieves the best integer-length code. A standard result bounds the gap: $H(p) \le L < H(p) + 1$, so Huffman coding is within one bit per symbol of the entropy. The slack comes from requiring every codeword to be a whole number of bits, which is a constraint on the code rather than on the source. For a distribution with two equiprobable symbols, entropy is 1 and Huffman assigns one bit each, so the bound is tight at zero gap; for a distribution with probabilities 0.9 and 0.1, entropy is about 0.469 and Huffman still assigns one bit per symbol, so the gap is about 0.531.

Kraft’s inequality constrains which length sets are feasible: a prefix code with lengths $\ell_i$ exists if and only if $\sum_i 2^{-\ell_i} \le 1$. The proof of Huffman’s optimality uses this in the form of a structural fact about trees rather than as an explicit constraint, but the inequality is what makes the search space finite.

Why a tree, and why the tree is full

A prefix code corresponds to a binary tree whose leaves are the symbols and whose root-to-leaf paths spell the codewords. Assigning 0 to a left edge and 1 to a right edge makes the correspondence exact, and the prefix property becomes the statement that no symbol sits at an internal node.

Two reductions shrink the search space before any greedy step is taken.

First, an optimal tree can be assumed full: every internal node has exactly two children. If an internal node had one child, contracting the edge would shorten every codeword below that node by one bit and leave the code valid, strictly reducing $L$ unless the node carried no leaves, in which case it is redundant. So an optimal tree has $n - 1$ internal nodes for $n$ leaves.

Second, an optimal tree can be assumed to have the two least probable symbols as siblings at maximum depth. This is the sibling property, and it is proved by exchange. Take any optimal tree and let $a$ and $b$ be the two symbols with the smallest probabilities. Let $x$ and $y$ be any two sibling leaves at maximum depth, which exist in a full tree with at least two leaves. Swap $a$ with $x$ and $b$ with $y$. The swap does not change the tree’s shape, so it does not change any codeword length; it only changes which symbol occupies which leaf. The change in cost is

$$ (p_a \ell_x + p_x \ell_a) - (p_a \ell_a + p_x \ell_x) = (p_a - p_x)(\ell_x - \ell_a) $$

Since $a$ has minimum probability, $p_a - p_x \le 0$, and since $x$ is at maximum depth, $\ell_x - \ell_a \ge 0$. The product is at most zero, so the swap does not increase cost. The same holds for $b$ and $y$. An optimal tree therefore exists in which the two rarest symbols are siblings at maximum depth.

The merge and its correctness

Given that structure, the algorithm is forced. Any optimal tree has the two rarest symbols as siblings at maximum depth, so their parent is a leaf-free node whose subtree contributes a fixed cost: each of the two symbols pays one extra bit, so the pair contributes $p_a + p_b$ beyond the cost of the subtree rooted at their parent. Replacing the pair by a single meta-symbol of probability $p_a + p_b$ produces a smaller instance of the same problem, and an optimal tree for the smaller instance, with the meta-symbol expanded back into the two leaves, is optimal for the original. Optimal substructure plus the sibling property gives the greedy choice property, and induction on the number of symbols finishes the proof.

The algorithm:

import heapq

def huffman_lengths(freq):
    # freq: dict symbol -> positive weight (count or probability)
    heap = [(w, i, (s,)) for i, (s, w) in enumerate(freq.items())]
    heapq.heapify(heap)
    lengths = {s: 0 for s in freq}
    counter = len(heap)
    while len(heap) > 1:
        w1, _, g1 = heapq.heappop(heap)
        w2, _, g2 = heapq.heappop(heap)
        # every leaf in both groups gains one bit of depth
        for s in g1 + g2:
            lengths[s] += 1
        heapq.heappush(heap, (w1 + w2, counter, g1 + g2))
        counter += 1
    return lengths

The tuple’s second field is a tie-breaker so that comparisons never fall through to the symbol group, which may not be orderable. Ties in weight are arbitrary and produce different but equally optimal trees. With a binary heap the running time is $O(n \log n)$ for $n$ symbols; with a two-queue method, exploiting the fact that merged weights are non-decreasing, it is $O(n \log n)$ for the initial sort plus $O(n)$ for the merges.

Note that the code above accumulates lengths rather than building the tree, which is enough for computing $L$ and for the length-limited variant discussed below. Concatenating the two symbol groups on each pop costs time proportional to the group sizes, so this particular version is quadratic even though the merge sequence itself is not; a tree built with parent pointers keeps the merge phase at $O(n \log n)$. A real encoder needs parent pointers or an explicit tree; a decoder needs the length sequence or the tree itself.

The numbers that matter in practice

Huffman coding is used inside DEFLATE (RFC 1951), which compresses with LZ77 first and then Huffman-codes the literals and match lengths. Two details of that standard show how the theory meets an implementation.

DEFLATE limits codeword lengths to 15 bits. An unrestricted Huffman code can produce a codeword of length up to $n - 1$ for $n$ symbols, which for a 286-symbol literal/length alphabet means a worst case of 285 bits, and a decoder that reads one bit at a time would need a 285-bit buffer. The 15-bit cap is not a property of Huffman coding; it is a constraint the format imposes, and satisfying it requires a different algorithm. Length-limited Huffman coding is solved by the package-merge method in $O(n L)$ time for maximum length $L$, or by a boundary-packing approach; both produce an optimal code subject to the cap, and both can be worse than unconstrained Huffman.

DEFLATE also transmits the code lengths themselves, run-length encoded, because the decoder cannot reconstruct the tree from the data. For small blocks the cost of the length description can exceed the savings from a better code, which is why the format allows a stored (uncompressed) block type and why encoders choose per block.

The 15-bit limit interacts with the entropy bound in a specific way: a code capped at 15 bits cannot give a symbol of probability below $2^{-15}$, roughly $3 \times 10^{-5}$, its ideal length of $-\log_2 p$ bits, because that ideal length is above the cap. For such distributions the code is forced to spend more bits on rare symbols than the entropy would suggest. A byte stream whose symbol distribution is that skewed therefore carries redundancy in its Huffman stage that no rearrangement of the code can remove while the 15-bit cap holds.

Adaptive and canonical forms

Two variants matter for implementation.

Adaptive Huffman coding rebuilds the tree as symbols arrive, using the frequency counts observed so far, so no distribution needs to be transmitted. The cost is that the tree must be updated after each symbol, and a naive rebuild is $O(n)$ per symbol. The standard incremental update maintains the sibling property as an invariant and restores it by swapping nodes after each increment; its work is proportional to the depth of the leaf just read, which is the length of that symbol’s codeword. The decoder performs the identical updates in the identical order, so the two stay synchronized without any side channel.

Canonical Huffman codes assign codewords to symbols deterministically from the length sequence alone: sort symbols by length, then by symbol value, and assign consecutive binary values with the standard shift rule. The advantage is that only the lengths need to be stored or transmitted, not the tree structure or the actual codewords, and the decoder can reconstruct the exact code. This is what makes the DEFLATE length transmission sufficient, and it is why the format can describe a code in a few hundred bits.

Limitations that survive optimality

Huffman coding is optimal for a known, fixed distribution and a symbol-by-symbol model. Both qualifications are load-bearing.

If the distribution is estimated from a small sample, the code is optimal for the estimate, not for the source, and the gap can be large. A code built from 100 observed symbols estimates each probability from 100 trials, so the estimate for a symbol of true probability $p$ has standard error $\sqrt{p(1-p)/100}$: about five percentage points for a symbol whose probability is near one half, and a much larger error relative to the value itself for a rare symbol. With such estimates the expected length can exceed the entropy of the true distribution by more than the one-bit bound allows, and the excess grows as the sample shrinks. Arithmetic coding avoids the integer-length penalty entirely and approaches the entropy to within a few bits per message rather than per symbol, at the cost of a slower and more delicate implementation.

The symbol-by-symbol restriction is the larger one. Huffman coding assigns a whole number of bits to each symbol independently, so it cannot exploit correlation between adjacent symbols. Removing that correlation before the Huffman stage, as DEFLATE does with its match-finding pass, is one response; modelling the context and coding with an arithmetic coder is another. Both move work out of the Huffman stage rather than improving it.

Finally, the greedy merge is correct only for the expected length objective with independent symbol costs. If the objective is not the expected codeword length, for instance if the goal is to minimize the longest codeword rather than the average, or if the cost of a codeword grows faster than linearly in its length, the merge is no longer optimal and the problem becomes a different one. The exchange argument fails at the cost-preservation step, exactly as it does for 0/1 knapsack.