Symptom

You are compressing a log file. The symbols are wildly skewed: INFO is 90% of the lines, WARN is 9%, ERROR and FATAL split the rest. Fixed-width two-bit codes give you exactly 2 bits per symbol, and entropy (T018) says the floor is about 0.53 bits. There is a factor of four sitting there.

So you assign short codes to common symbols. INFO gets 0, WARN gets 1, ERROR gets 01, FATAL gets 10. Then you try to decode 0101 and find it is INFO WARN INFO WARN, or ERROR ERROR, or INFO WARN ERROR… The stream is ambiguous and there is no way to fix it by adding a rule, because the ambiguity is structural: 0 is a prefix of 01.

Now you have two questions and they are different. First, which sets of codeword lengths are even possible for an unambiguous code? Second, given that constraint, which assignment is best? The first is Kraft’s inequality and it is the cleaner of the two. The second is Huffman’s algorithm, and the striking part is not that it works but that a greedy algorithm — the kind that usually gives you an approximation — turns out to be exactly optimal.

Statement

Kraft’s inequality. A prefix code over an alphabet of size $D$ with codeword lengths $\ell_1, \dots, \ell_n$ exists if and only if

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

Huffman’s theorem. For a source with symbol probabilities $p_1, \dots, p_n$, the Huffman code minimizes expected codeword length $\sum p_i \ell_i$ over all prefix codes. Combined with T018:

$$H(X) \le L_{\text{Huffman}} < H(X) + 1.$$

Three things worth separating here. Kraft is a statement about which length vectors are achievable, and it says nothing about which is good. Huffman picks the best one. And the $+1$ gap is the price of insisting that every codeword be a whole number of bits — the only thing standing between Huffman and the entropy floor, and the reason arithmetic coding exists.

Argument

Kraft, forward direction. Think of the code as a tree: each codeword is a leaf at depth $\ell_i$, and prefix-freeness means no codeword is an ancestor of another. In a complete binary tree of depth $L = \max \ell_i$, a leaf at depth $\ell_i$ rules out $2^{L - \ell_i}$ of the $2^L$ possible depth-$L$ nodes, and prefix-freeness means these sets are disjoint. So $\sum 2^{L-\ell_i} \le 2^L$, which is Kraft.

The probabilistic reading is nicer: walk down the tree flipping a fair coin. You reach the leaf for codeword $i$ with probability $2^{-\ell_i}$, and these are disjoint events, so they sum to at most 1. Kraft is just “probabilities of disjoint events add up.”

Kraft, converse. Given lengths satisfying the inequality, sort them increasing and assign codewords greedily as binary fractions: $c_i$ is the first $\ell_i$ bits of $\sum_{j<i} 2^{-\ell_j}$. The inequality guarantees you never run out of room, and sortedness guarantees prefix-freeness. So the inequality is not merely necessary; it is a complete characterization of which length vectors you may have.

Why entropy is a lower bound. Minimizing $\sum p_i \ell_i$ subject to Kraft, with the integrality dropped, is a Lagrange problem whose solution is $\ell_i = -\log_2 p_i$, giving $\sum p_i \ell_i = H(X)$ exactly. So the entropy floor is the Kraft constraint with the integers relaxed, and Huffman’s job is to round.

Huffman’s algorithm. Take the two least probable symbols, merge them into a node with the sum of their probabilities, and repeat until one node remains. Read off the tree. That is the whole thing.

Why greedy is exactly optimal. The proof is two exchange arguments, and both are worth the space because greedy algorithms are usually not optimal and the reason this one is comes down to two structural facts.

Fact one: an optimal code has the two rarest symbols as siblings at maximum depth. Suppose in an optimal tree a symbol $x$ with lower probability sits higher than a symbol $y$ with higher probability. Swapping them changes the cost by $(p_x - p_y)(\ell_y - \ell_x)$, which is $\le 0$ — the swap does not hurt. So some optimal code has the rarest symbols deepest. Further, an optimal tree has no unmatched leaf (you could promote it and save a bit), so the two deepest leaves are siblings, and we may take them to be the two rarest.

Fact two: merging is cost-preserving. Let $T$ be a code for the merged alphabet, where $x$ and $y$ are replaced by a single symbol $z$ with $p_z = p_x + p_y$. Expanding $z$ back into a pair of leaves costs exactly $p_x + p_y$ extra bits, regardless of where $z$ sits. So

$$\mathrm{cost}(T_{\text{expanded}}) = \mathrm{cost}(T) + p_x + p_y,$$

a constant offset. Minimizing one minimizes the other. Induct on alphabet size: Huffman’s merge step reduces the problem to a strictly smaller one whose optimal solution lifts to an optimal solution here.

That constant offset is the crux. Greedy algorithms fail when an early choice constrains later ones in a way that depends on the choice; here the merge changes the cost by an amount that does not depend on what the rest of the tree does, so the subproblem is genuinely independent.

The numbers. For the log file: $p = (0.9, 0.09, 0.005, 0.005)$. Entropy is $0.526$ bits. Huffman gives lengths $(1, 2, 3, 3)$ for a cost of $1.11$ bits per symbol — better than 2, and nowhere near 0.526, because no codeword can be shorter than one bit however likely it is. That is the $+1$ gap at its worst, and skewed distributions are exactly where it bites hardest.

Forbids

A prefix code with lengths violating Kraft. If someone proposes a code with lengths $(1,2,2,3)$ over a binary alphabet, $0.5+0.25+0.25+0.125 = 1.125 > 1$ and no such code exists. This is a one-line check on any proposed format.

Any prefix code beating Huffman on the same alphabet and probabilities. Huffman is not a heuristic. There is nothing left to find, and “we improved on Huffman” always means the model or the alphabet changed.

Beating entropy. $L \ge H(X)$ for any uniquely decodable code, not just prefix codes — the McMillan converse shows uniquely decodable codes satisfy Kraft too, so dropping the prefix property buys nothing. This is worth knowing because it closes an obvious escape route.

Does not forbid

It does not stop arithmetic coding from beating Huffman, and in practice everything does. Arithmetic and range coding encode the whole message as a single number in $[0,1)$, so symbols cost fractional bits and the total lands within 2 bits of entropy for the entire message rather than 1 bit per symbol. On the log-file distribution above that is 0.53 versus 1.11 — a 2x difference, not a rounding error. This is why modern compressors use rANS (Zstandard, LZFSE) or context-mixing arithmetic coders, and Huffman survives mainly where decode speed dominates. DEFLATE uses Huffman; Zstandard uses both, picking per block.

It does not fix the probability model, which is where the real gains are. Huffman is optimal given $p$. Order-0 Huffman on English text gets about 4.2 bits per character; a good context model gets under 2. Every serious compressor spends its effort on modelling, and the entropy coder is the cheap part. LZ77 plus Huffman beats Huffman alone because the LZ stage changes the alphabet from characters to matches, not because the coder improved.

It does not require probabilities to be known in advance. Adaptive Huffman (FGK, Vitter) updates the tree as it encodes, and two-pass Huffman ships the table. Both are used; JPEG and MP3 ship standard tables, and DEFLATE offers fixed, dynamic, and stored block types so the encoder can choose per block.

It does not say the Huffman tree is unique. Ties produce different trees with identical cost. Canonical Huffman codes exploit this: fix a tie-break rule so the decoder can rebuild the tree from the lengths alone, which is why JPEG and DEFLATE transmit only a list of code lengths and not the tree.

It does not apply when codeword costs are unequal or constrained. If symbols cost different amounts to transmit, the right answer is the Varn code; if you need a maximum codeword length — as JPEG does, capping at 16 bits — the length-limited problem is solved by the package-merge algorithm, not by Huffman, and it is genuinely a different algorithm giving a slightly worse code.

Boundary

  • The $+1$ is tight and it is about integers. A two-symbol source with $p = (0.99, 0.01)$ has entropy $0.08$ bits and Huffman must spend 1 bit. The loss is entirely the rounding, which is why blocking symbols together — coding pairs or triples — reduces the per-symbol penalty to $1/k$ and why arithmetic coding, which blocks the entire message, essentially removes it.
  • Shannon–Fano is the near miss. Fano’s top-down splitting was the state of the art when Huffman took the class, and it is not optimal. The direction of construction is the whole difference: bottom-up commits to the decisions that are forced, top-down commits to the ones that are not.
  • Kraft as a general tool. The inequality is really a statement about any assignment of disjoint probability mass, and it reappears in Kolmogorov complexity (T023) as the reason $\sum 2^{-K(x)} \le 1$, which is what makes the universal prior a probability distribution at all.
  • Optimal is not the same as good enough. Huffman is optimal over prefix codes for a memoryless source. Change any of those — memory, non-prefix, fractional bits — and there is room. Most practical progress comes from noticing which assumption is the wrong one, not from beating the theorem.
  • Where the greedy proof pattern generalizes. The two exchange arguments here are the matroid-greedy pattern: local optimality plus a subproblem that is independent of the choice made. Kruskal’s algorithm has the same shape, and recognizing it is how you tell in advance whether greedy will work.