Graft the lightest frequencies into a bottom-up prefix tree that achieves Shannon's entropy limit.
- Extract the two lowest-weight nodes and combine them into a composite branch
- Compare the resulting prefix tree against fixed-width and Shannon-Fano codes
- Calculate the exact bits-per-symbol cost incurred by premature merges
After thisYou can construct provably optimal prefix-free compression dictionaries for any discrete probability distribution.
Short on timeThe HuffmanMerge interactive tree builder in §2
Six Letters on a Wire
3 minthe hook
At a billion symbols, a one-bit gap is 125 megabytes. Every gzip file, PNG, and JPEG carries a Huffman table, and that table is where the gap gets paid.
Six symbols wait on the board, each carrying a fixed frequency of occurrence. Pair any two roots and merge them: the tree branches out, labels its edges with 0 and 1, and accumulates the weight of their junction into a running bill.
The picture is the grafting orchard: each merge grafts the two lightest trees onto one new stem, and that stem carries the summed weight of every fruit above it. A fruit pays for every stem between it and the root, so a graft made too high can never be taken back.
Before making your first merge: if you mistakenly fuse the heaviest symbol (A = 40) with anything else, what minimum penalty will you pay across every encoded symbol?
Huffman's rule: merge the two lightest roots, E (5) and F (5). Any other pair is allowed — the panel will price it.
H = 2.204 · L* = 2.25 · Σ so far = 0 · the shaded band is H to H + 1.
One axis, in bits per symbol. H is the Shannon entropy of this distribution (Shannon 1948), a lower bound for any prefix code. L* is what Huffman's rule achieves. The shaded band runs from H to H + 1: no binary prefix code can cost less than H, and one built two symbols at a time never costs a whole bit more.
| symbol | weight | pᵢ | prefix | ℓᵢ | pᵢℓᵢ |
|---|---|---|---|---|---|
| A | 40 | 0.4 | — | 0 | 0 |
| B | 25 | 0.25 | — | 0 | 0 |
| C | 15 | 0.15 | — | 0 | 0 |
| D | 10 | 0.1 | — | 0 | 0 |
| E | 5 | 0.05 | — | 0 | 0 |
| F | 5 | 0.05 | — | 0 | 0 |
| Σ | 100 | 1 | 0 |
The forest is not a single tree yet, so the ℓᵢ column counts only the edges from a leaf up to its current root. Those are prefixes, not code words. The Σ row will equal L only when one tree remains.
Six roots to start. Merge any pair; the axis and the running total update at once. Huffman's own choice is marked while the hint is on.
Watch the running total; with the greedy hint off, merge A = 40 early, finish greedily, and L ends at 2.45, never back at 2.25.
The running total is bits per symbol, and the axis underneath carries three markers: the entropy, the cost Huffman’s rule achieves, and your current cost. The shaded band runs from up to .
NextWhy does an unmarked binary bitstream lead to catastrophic ambiguity without prefix rules?
The Ambiguity of Unmarked Streams
2 minthe trap
The ask is a code: one distinct bit string per symbol, so that the encoded stream is short and decodes without separators. Common symbols should get short strings, so you are minimising the average length over all assignments of strings.
Brute force would try every assignment. The reason it is the wrong picture is that the strings are not independent — some assignments of lengths cannot be realised by any prefix-free code at all. The question is which lengths are allowed and which tree attains the best ones.
NextHow does Kraft's inequality bound the leaf depths of every binary code tree?
The Geometry of Prefix-Free Trees
2 minthe invariant
A prefix-free code, one where no code word begins another, is exactly a binary tree with the symbols at the leaves. The path from the root to a leaf spells that symbol’s code word: left is 0 and right is 1. So the code and the tree are one object, and the length is the leaf’s depth.
Prefix-freedom is then automatic. A symbol sits at a leaf, no leaf is an ancestor of another, so no code word is a prefix of a different one, and decoding walks the tree reading bits until it lands on a leaf.
The payoff of the tree view is a second way to add up the cost. Each leaf is counted once for every internal node above it, so regrouping the sum by internal nodes gives an identity.
The panel is this identity in motion: every merge creates one internal node, and the running total is the weight of that node added in. When one tree remains the total is the average code length, and until then it is a partial sum.
NextWhy does an early non-optimal merge levy a permanent fractional penalty per symbol?
Pinioned Between Shannon and Kraft
2 minthe algebra
Shannon 1948. The entropy of the source is
and no uniquely decodable code has average length below . For a prefix code the depths must satisfy Kraft’s inequality (Kraft 1949),
and McMillan 1956 showed the same inequality holds for every uniquely decodable code, prefix or not.
Together those give the floor. Any lengths obeying Kraft satisfy , so the axis cannot drop below the marker: every tree the panel can build has valid depths, and valid depths cost at least .
Huffman 1952. Merging the two lightest roots, over and over, produces a tree of minimum weighted path length .
The reason is an exchange argument. Take any optimal tree; its two least probable symbols can be made siblings at the deepest level without raising the cost, by swapping them with the deepest pair. So some optimal tree merges the two lightest first, and recursion finishes the proof.
That bound and the floor sit one bit apart. Choosing the lengths costs at most for each symbol and still obeys Kraft, so a prefix code exists with . Huffman’s rule is optimal, hence
Both ends of that inequality are honest in different ways. The floor is a theorem about all codes; the ceiling is a theorem about the greedy tree, and the gap between them can be as large as a whole bit.
1 minboss round
On the board H = 2.2037 and Huffman's cost is L* = 2.25. Across sources, how large can the gap L* − H be forced?
NextHow does the greedy two-lightest rule guarantee the minimal expected code length?
The Cost of Disobedience
2 minthe simulation
Go back to the board and build the code yourself. Turn the hint off and merge a heavy root with a light one first, then finish greedily; the axis shows your accumulated cost drifting above the marker, and the final total is worse than the rule’s.
Concretely, grafting the weight-40 tree onto a weight-5 tree first costs 45 bits of merged stem weight before any other graft, and the greedy finish lands at 2.45 against the rule’s 2.25. That 0.20-bit spread is the greedy rule’s value made visible, and no order does better.
Reset, turn the hint back on, and merge the two marked lightest roots each time. The lengths come out 1, 2, 3, 4, 5, 5 for the weights 40, 25, 15, 10, 5, 5, and the total stops exactly on the marker.
The chart below leaves the single board and sweeps a family of sources. For each size it plots the entropy of a Zipf source, the cost Huffman’s rule achieves on it, and the ceiling .
A Zipf source of m symbols: entropy, optimal Huffman cost, and the one-bit ceiling, in bits per symbol.
The Huffman curve threads between the entropy curve and the ceiling the whole way. At the Zipf probabilities 0.48, 0.24, 0.16, 0.12 have ideal lengths close to the whole-number lengths 1, 2, 3, 3, so the gap nearly closes to 0.008 bits; elsewhere it holds a small fraction of a bit.
Heavier sources do not change the story. The entropy grows like and the optimal code keeps paying almost exactly that, which is why the chart is three near-parallel lines.
NextWhat integer-bit constraint prevents Huffman from reaching Shannon's true entropy?
The Engine Inside Every Archive
2 minsystems
Every general-purpose compressor runs a Huffman stage. DEFLATE, the format inside gzip and PNG, sends a Huffman table for its literals and then a second one for its match lengths and distances, all built by this merge. JPEG quantises then Huffman-codes; MP3 does the same on its spectral coefficients.
The rule generalises without changing character. Merging the lightest roots at a time gives optimal -ary codes, and when the code must fit a fixed field width, the package-merge method of Larmore and Hirschberg 1990 finds the best length-limited tree in nearly linear time.
The Tyranny of the Integer Bit
The gap is an artefact of whole-bit code words. When a symbol’s probability is far from a power of a half the nearest dyadic length overshoots, and no prefix code can split a bit.
On the two-symbol 0.99/0.01 source the rare symbol carries almost all of the entropy — 6.64 bits of surprise worth 0.066 of the total. Yet it still costs a full bit, so the average length is 1 against an entropy of 0.0808.
Arithmetic coding removes the artefact by coding a whole message into one number instead of one symbol at a time, reaching the entropy in the limit (Rissanen 1976). It wins precisely where Huffman loses, which is why modern compressors keep both and pick per block.
Lineage & Attributions
- Shannon 1948 — A Mathematical Theory of Communication: the entropy and the lower bound on the length of any decodable code.
- Kraft 1949 — the inequality satisfied by the depths of a prefix code, the constraint on which lengths a tree can realise.
- Fano 1949 — the top-down Shannon–Fano construction, the earlier method Huffman’s rule improves on.
- Huffman 1952 — A Method for the Construction of Minimum-Redundancy Codes: merge the two lightest roots, and the exchange lemma that makes the result optimal.
- McMillan 1956 — the extension of Kraft’s inequality to all uniquely decodable codes, not only prefix codes.
- Gallager 1978 — Variations on a theme by Huffman: the redundancy of Huffman codes, and the bound analysed.
- Rissanen 1976 — arithmetic coding, the method that reaches the entropy the one-bit bound leaves behind.
- Larmore–Hirschberg 1990 — package-merge, the length-limited Huffman tree, for codes constrained to a fixed bit width.