That Huffman's code is short is a measurement. That no code is shorter is a theorem, and it rests on two lemmas: an optimal tree can always be rearranged so that the two lightest symbols are deepest siblings, and merging those two reduces the problem to one symbol fewer. The lab checks the conclusion the only way a lab can — by building every full binary tree on n leaves and trying every way of putting the weights on them.
Core ideas
Three ideas: why optimality needs an exchange argument rather than a calculation, how an induction on the number of symbols closes it, and what an enumeration over every tree can and cannot add.
The expected length of Huffman's code is arithmetic. The claim that no prefix code on the same weights is shorter ranges over every full binary tree and every way of placing the symbols on its leaves — on six symbols that is 42 shapes and 30,240 placements. No amount of looking at the code Huffman produced settles it, which is why the argument has to be about an arbitrary optimal tree rather than about this one.
If a heavier symbol sits deeper than a lighter one, swapping them cannot increase the cost: the change is (w_heavy − w_light)(depth_shallow − depth_deep), a product of a non-negative and a non-positive number. That one inequality is the engine of the first lemma, and it is the same move as the exchange argument on intervals, applied to positions in a tree instead of to positions in a schedule.
The panel builds every full binary tree on n leaves and tries every assignment of the weights, and reports the minimum. When that minimum equals Huffman's cost, the claim “no code is shorter” has been verified for this alphabet by a search that knows nothing about merging. It is still one alphabet. The lemmas are what cover the alphabets nobody typed.
The material
The exchange lemma, the reduction lemma, the induction they close, and what the enumeration over every tree adds and does not add.
For a full binary tree T whose leaves carry the symbols, write B(T) = Σ wᵢ · dᵢ, where dᵢ is the depth of symbol i. A prefix code corresponds to such a tree and its total bit count is B(T), so minimising the code is minimising B over trees and over assignments of the symbols to leaves.
Let x and y be two symbols of smallest weight. Some optimal tree has x and y as sibling leaves at maximum depth.
Take any optimal tree T and let a and b be two sibling leaves at maximum depth — they exist because the tree is full, so the deepest leaf has a sibling, and that sibling is also a leaf at the same depth.
Swap a with x. Writing d for depths, the cost changes by (w_a − w_x)(d_x − d_a). Since x is of smallest weight, w_a − w_x ≥ 0; since a is at maximum depth, d_x − d_a ≤ 0. The product is at most 0, so the cost did not increase, and T was optimal, so it did not decrease either.
Swap b with y in the same way. The result is an optimal tree in which x and y are sibling leaves at maximum depth.
□
Let x and y be two symbols of smallest weight and let z be a new symbol of weight w_x + w_y replacing them. If T' is an optimal tree for the reduced alphabet, then the tree T obtained by replacing the leaf z with an internal node whose children are x and y is optimal for the original alphabet.
First, the costs are related by a constant. In T, x and y sit one level below where z sat, so B(T) = B(T') − w_z d_z + (w_x + w_y)(d_z + 1) = B(T') + w_x + w_y, using w_z = w_x + w_y. The same identity holds for any tree of the reduced alphabet and its expansion.
Suppose some tree U for the original alphabet had B(U) < B(T). By the first lemma we may assume x and y are sibling leaves in U. Contract that pair into a single leaf z to get a tree U' for the reduced alphabet, with B(U') = B(U) − w_x − w_y.
Then B(U') = B(U) − w_x − w_y < B(T) − w_x − w_y = B(T'), contradicting the optimality of T'. So no such U exists and T is optimal.
□
The induction is now immediate. On two symbols the only full binary tree gives both a one-bit codeword and is optimal. For n symbols, Huffman's first merge takes the two lightest, the rest of its run is Huffman on the reduced alphabet, which by induction is optimal there, and the second lemma lifts that optimality back. So Huffman's code is optimal for every alphabet.
The panel does something the proof does not: it builds every full binary tree on n leaves and, for each, tries every assignment of the weights to its leaves, then reports the smallest total. The number of shapes on n leaves is the Catalan number C(n−1), so four leaves give 5 shapes, five leaves 14, and six leaves 42; with n! assignments each, that is 120, 1680 and 30,240 (shape, assignment) pairs respectively.
The lab opens on four equal weights, a:10, b:10, c:10, d:10. All 5 shapes and all 120 pairs are tried, the best is 80 bits, and Huffman's code costs 80. On the six-symbol alphabet the best of the 30,240 pairs is 224 bits, which is again what Huffman produced. On the skewed and Fibonacci alphabets, 170 and 25 bits respectively, matched both times.
Trying every assignment as well as every shape is deliberate, and it is where the check earns its place. A search that placed the heaviest weight on the shallowest leaf of each shape would be assuming the rearrangement inequality — the same inequality the first lemma is built on — and would therefore be checking the proof against itself. Enumerating the assignments assumes nothing, so the two can disagree, and on four alphabets they do not.
Seven leaves is 132 shapes and 5,040 assignments each, and the panel refuses rather than running it. When it refuses it prints why, and the expected length above stays exact: what is missing is the confirmation that nothing beats it. A page that silently dropped the check would look identical to a page that had run it, which is the failure mode this whole path is built against.
So the honest reading of this page has three layers rather than two. Measured: on the four shipped alphabets, the minimum over every shape and every assignment equals Huffman's cost — 80, 224, 170 and 25 bits. Proved: Huffman is optimal for every alphabet, by the two lemmas and the induction. Refused: on seven or more symbols the search does not run, and the page says which of the two sentences it can still stand behind.
Interactive
The merges, the exact expected length, and every tree it is measured against
Method
Four steps, and the first one is the one that decides whether the rest is a proof or a demonstration.
The proof takes an optimal tree T that nobody built and shows it can be rearranged. Starting from Huffman's own tree and observing that it looks reasonable is the error this whole course is about, and it is easy to make when the tree is in front of you on the screen.
The swap in the first lemma is justified by a product of two factors whose signs are known: a weight difference that is non-negative and a depth difference that is non-positive. No arithmetic on the actual numbers is needed, which is what makes the lemma hold for every alphabet.
The second lemma turns n symbols into n - 1 and relates the two costs by a constant, w_x + w_y. A reduction that changed the cost by something depending on the tree would not support an induction, and checking that the constant really is constant is the step worth writing out.
Run the enumeration on the alphabets it will take, and write down that it matched. Then write down the size at which it refused. An optimality claim supported only by alphabets small enough to enumerate is a claim about those alphabets.
Weights a:10, b:10, c:10, d:10. With four leaves there are only five full binary tree shapes, and with equal weights the assignment of symbols to leaves cannot change a shape's cost, so the five shapes can be costed directly.
Only the balanced shape reaches 80, and Huffman finds it. The other four shapes each put one symbol at depth 1 and two at depth 3, which is exactly the trade that pays off when the weights are skewed and costs 10 bits when they are not.
This is also the cleanest place to see what the optimality theorem does and does not promise. It promises that no tree beats 80, and that is true. It does not promise a saving: the fixed-length code also costs 80, and the panel reports a saving of 0 rather than hiding it.
For a faded rehearsal, predict how many shapes the six-symbol alphabet has before opening it. The supplied first move is the recurrence: a full binary tree on n leaves splits into a left subtree on k leaves and a right one on n − k, so the counts satisfy the Catalan recurrence and run 1, 1, 2, 5, 14. Say what the sixth term is, multiply by 6! for the assignments, and check both against the panel.
You should be able to justify the exchange swap by the signs of its two factors, derive the constant w_x + w_y relating a tree to its contraction, explain why the induction needs both lemmas rather than either alone, and say what remains unestablished when the panel refuses to enumerate.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.