Prefix Codes, the Kraft Inequality, and Why Huffman Is Optimal

A code assigns a binary string to each symbol of an alphabet. If the strings are concatenated into one stream, the decoder must be able to find the boundaries between them, and the cheapest way to guarantee that is to make no codeword a prefix of another. That single constraint costs at most one bit per symbol relative to the entropy bound, and the construction that meets the bound is a greedy merge that can be implemented in a few lines.

The constraint that makes decoding deterministic

Consider codes for three symbols: A = 0, B = 01, C = 1. The string 001 is ambiguous between A A C and A B, because 0 is a prefix of 01. A prefix-free code forbids that: no codeword may be an initial segment of another. Decoding then proceeds by walking the tree from the root and emitting a symbol whenever a leaf is reached, with no lookahead and no backtracking.

Prefix-free is sufficient but not necessary for unique decodability. The code A = 0, B = 01, C = 10 is not prefix-free, yet every concatenation is uniquely parseable: a 0 must begin A or B, and it begins B only when the following bit is 1 and the bit after that is not. No other parse exists, so the code is uniquely decodable in spite of the shared prefix. The McMillan inequality shows, however, that any uniquely decodable code can be converted to a prefix code with the same multiset of codeword lengths. So restricting attention to prefix codes loses nothing in achievable expected length, and it buys a decoder that is a table lookup per bit.

The tree view makes the cost accounting exact. A binary tree with leaves at depths $\ell_1, \ldots, \ell_n$ satisfies

$$\sum_{i=1}^{n} 2^{-\ell_i} \le 1$$

This is the Kraft inequality. Each leaf at depth $\ell$ occupies a fraction $2^{-\ell}$ of the total probability mass of an infinite binary tree, and the fractions must not overlap. The sum is exactly 1 for a complete tree, less than 1 when some leaves are missing, and greater than 1 for any set of lengths that cannot be realized. The inequality is also sufficient: any lengths satisfying it can be assigned to a tree, by repeatedly splitting the shallowest available node.

For the uniform distribution over eight symbols, lengths of 3 satisfy the bound with equality and the expected length is 3 bits, equal to the entropy. For a distribution where one symbol has probability 1/2 and the rest share the remainder, lengths of 1, 2, 3, 3 satisfy $\tfrac12 + \tfrac14 + \tfrac18 + \tfrac18 = 1$.

Huffman’s greedy merge

Huffman’s algorithm builds the tree bottom-up. Start with a leaf per symbol, each carrying its probability. Repeatedly remove the two nodes with the smallest weights, create a parent whose weight is their sum, and insert it. After $n-1$ merges one node remains, and the depth of each leaf is its codeword length.

import heapq

def huffman_lengths(freqs):
    """freqs: dict symbol -> positive weight. Returns dict symbol -> bit length."""
    heap = [(w, i, (s,)) for i, (s, w) in enumerate(freqs.items())]
    heapq.heapify(heap)
    lengths = {s: 0 for s in freqs}
    uid = len(heap)
    while len(heap) > 1:
        w1, _, g1 = heapq.heappop(heap)
        w2, _, g2 = heapq.heappop(heap)
        for s in g1:
            lengths[s] += 1
        for s in g2:
            lengths[s] += 1
        heapq.heappush(heap, (w1 + w2, uid, g1 + g2))
        uid += 1
    return lengths

The counter in the tuple breaks ties by insertion order so that the heap comparison never needs to compare symbol tuples, which would fail for mixed types. The algorithm is $O(n \log n)$, dominated by the heap operations, or $O(n)$ after sorting with a two-queue implementation: the merged weights form a nondecreasing sequence, so the two queues can be merged in linear time.

The optimality proof is an exchange argument in two steps. First, in any optimal tree the two least probable symbols can be taken to be siblings at maximum depth: if a deeper leaf exists elsewhere, swapping it with a shallower one cannot increase the weighted path length because the shallower leaf has at least as much probability. Second, contracting those two siblings into a single leaf with their combined probability yields an optimal tree for the reduced alphabet, so an optimal solution to the smaller problem extends to an optimal solution of the original. Inducting on alphabet size gives the result. The greedy step is therefore not a heuristic; it is forced by the structure of any optimum.

What the expected length is worth

For a code with lengths $\ell_i$ and symbol probabilities $p_i$, the expected length $L = \sum p_i \ell_i$ satisfies

$$H(X) \le L < H(X) + 1$$

The lower bound follows from the Kraft inequality and Gibbs’ inequality: the cross-entropy $\sum p_i \ell_i$ is minimized over lengths satisfying the Kraft constraint exactly when $\ell_i = -\log_2 p_i$, giving $H(X)$, and any other feasible length assignment is worse. The upper bound comes from choosing $\ell_i = \lceil -\log_2 p_i \rceil$, which satisfies Kraft and overshoots each term by less than one bit.

The one-bit slack is real and not merely an artefact of the proof. A source with two symbols of probability 0.999 and 0.001 has entropy about 0.0114 bits, but every prefix code needs at least one bit per symbol, so $L = 1$. The overhead is roughly 0.99 bits, or about 88 times the entropy. This is the motivation for Arithmetic Coding and Interval Subdivision, which escapes the integer-length constraint by coding whole messages into a single number and approaches $H$ from above with error bounded by a few bits per message rather than per symbol.

The slack also shrinks in a different way: for a block of $k$ symbols coded jointly, the redundancy is below $1/k$ bit per symbol, because the entropy of the block is $kH$ for an independent source and the ceiling penalty is paid once per block. Blocking is the other route to the entropy bound, and it is what makes Huffman coding competitive in practice despite the per-symbol penalty.

Canonical codes and the length-limit problem

A Huffman tree is not unique: ties in the merge order produce different trees with the same expected length. For transmission, the tree does not need to be sent at all if both sides agree on a canonical assignment. Given the sorted list of codeword lengths, the canonical construction assigns the first codeword of each length by shifting the previous codeword left by one and incrementing, skipping over shorter lengths. DEFLATE uses exactly this scheme, transmitting a Huffman-coded sequence of lengths and deriving the codes from it.

The maximum length of a codeword is bounded in practice, and that bound creates a real problem. In DEFLATE a code length is represented by a 4-bit symbol, so no codeword may exceed 15 bits. A Huffman tree for a highly skewed distribution can produce lengths beyond that: with Fibonacci-like probabilities the deepest leaf can be far deeper than 15. Two remedies exist. The first is to flatten the distribution by adding a small constant to every frequency before building the tree, which bounds the maximum depth but sacrifices optimality. The second is the package-merge algorithm, which finds the optimal length-limited code in $O(nL)$ time for limit $L$, by solving a coin-collector style dynamic program over the length budget. Length-limited optimal codes are the standard response in both cases. The format constrains only what the decoder must accept, not how the lengths were chosen, and a length-limited Huffman tree is strictly better than a flattened one at the same limit.

A related constraint appears in the decoder’s data structures. A canonical Huffman decoder can be a single-level lookup table indexed by the next $L$ bits, with entries for short codes pointing at the symbol and entries for long codes pointing at a secondary table. The table size is $2^L$ entries, so $L = 15$ costs 32768 entries, which is why some formats cap code length well below the number of symbols.

Where prefix coding stops paying

Huffman coding is optimal among prefix codes for a known, fixed, memoryless distribution. Each of those three qualifications corresponds to a way it fails.

Unknown distribution. The code must be transmitted or estimated. Sending a table of $n$ frequencies costs on the order of $n \log n$ bits, which can exceed the savings for short messages. Adaptive variants update the tree as symbols arrive, at the cost of rebuilding it; the frequency of rebuilds determines the overhead.

Memory. For a source with dependencies, coding symbols independently ignores the structure. The entropy rate of an order-1 Markov source can be far below its order-0 entropy, and no assignment of per-symbol lengths can capture the difference. Dictionary methods described in LZ77, LZ78, and the Shift from Symbols to Substrings exploit repeated substrings instead, and they do so without a probability model.

Nonstationarity. A code built for the average distribution is suboptimal for any local segment whose statistics differ. Block-adaptive schemes rebuild the model per block, and the block size trades model cost against adaptation speed.

There is one more limitation worth naming. Huffman coding cannot assign a codeword of length zero, so an alphabet of one symbol still costs one bit per symbol under a naive implementation. Real formats special-case the single-symbol alphabet, and the special case is a reminder that the model assumes at least two outcomes.

The connection to the entropy bound is not merely asymptotic. For any distribution, the expected length of a Huffman code is within one bit of the entropy, and the gap is the cost of rounding the ideal lengths $-\log_2 p_i$ up to whole bits, which no prefix code can avoid for an alphabet of two or more symbols. That residual is what later methods such as arithmetic coding and context modelling are designed to remove.