Lesson · Greedy Algorithms and Matroids · Huffman codes

Huffman Codes

Huffman's algorithm is greedy in an unusual direction: it builds the tree from the leaves upward, and the choice it commits to is which two symbols become siblings. The expected codeword length is a fraction and the lab prints it as one. The code is checked prefix-free pairwise rather than trusted to the construction, and a message is encoded and decoded again, because a code that is short and wrong looks exactly like a code that is short and right.

Open the interactive lesson Practice

merge the two lightest weights; the merged node's weight is their sum n symbols → n − 1 merges → a full binary tree, every internal node with 2 children expected length = total bits / total weight, an exact fraction a:45 b:13 c:12 d:16 e:9 f:5 → 224 bits over weight 100 → 56/25 against 3 bits for a fixed-length code over six symbols: a saving of 19/25 prefix-free, checked pair by pair; and the message decodes back to itself

The merges, the tree, and the fraction they produce

Core ideas

What this lesson establishes

Three ideas: what a prefix code buys, why the expected length is a fraction rather than a decimal, and why a round trip is worth more than a length.

A prefix code can be decoded without separators

A code is prefix-free when no codeword is a prefix of another. That is what lets a decoder read a bit stream left to right and commit to a symbol the moment it has seen one: no lookahead, no separators, no ambiguity. Every full binary tree with the symbols at its leaves gives a prefix code, because a leaf's path cannot be a prefix of another leaf's path. The panel still checks it pairwise, because a check that trusts the construction checks nothing.

The expected length is a ratio of two integers

Multiply each symbol's weight by the length of its codeword, add, and divide by the total weight. On the opening alphabet that is 224 bits over a total weight of 100, which is 56/25 exactly. The panel prints 56/25 first and 2.240 beside it as a rounding of the printing at three places. The fraction is the number; the decimal is a convenience, and on a path where two codes can differ in the third place that distinction earns its keep.

A round trip catches what a length cannot

A shorter code is not a better code if it cannot be read back. The panel encodes a message you type, decodes the resulting bits, and prints whether what came out is what went in. On the opening alphabet abcdef encodes to 18 bits and decodes back exactly. The check is cheap and it is the only thing on the page that would notice a code that was short because it was wrong.

The material

Merging upward, and the code that falls out

The algorithm, the tree it builds, the exact expected length, and the three checks that stand between a short code and a correct one.

Definition · The coding problem

Given symbols with positive integer weights, assign each a binary codeword so that no codeword is a prefix of another, minimising the total Σ wᵢ · |cᵢ| — the number of bits needed to write a text in which each symbol appears with its weight as a count. Dividing that total by Σ wᵢ gives the expected codeword length.

Definition · Huffman's algorithm

Put every symbol in a collection as a single-node tree with its weight. Repeatedly remove the two lightest trees, join them under a new node whose weight is their sum, and put that node back. After n - 1 merges one tree remains; label left edges 0 and right edges 1, and each leaf's root-to-leaf path is its codeword.

The greedy commitment is the merge. Once two trees have been joined, the symbols beneath them stay at the same depth relative to each other forever, and nothing later reconsiders it. What makes this an unusual greedy algorithm is the direction: the choice is made at the leaves, where the rarest symbols are, and the consequence — the codewords — is read off at the end.

Example · Six symbols, five merges

The lab opens on a:45, b:13, c:12, d:16, e:9, f:5. The merges are f + e = 14, then c + b = 25, then 14 + d = 30, then 25 + 30 = 55, then a + 55 = 100. The codewords come out a = 0, c = 100, b = 101, f = 1100, e = 1101, d = 111, with lengths 1, 3, 3, 4, 4 and 3. Total bits 224, total weight 100, expected length 56/25.

The heaviest symbol got the shortest codeword and the two lightest got the longest, which is the whole idea, and it is worth checking against the alternative: a fixed-length code over six symbols needs 3 bits each, so it spends 300 bits on the same text. The saving is 19/25 of a bit per symbol, which the panel prints as a fraction as well.

The saving is a fact about the distribution, not about the algorithm

Run the same algorithm on four equal weights, a:10, b:10, c:10, d:10. Every codeword comes out two bits, the expected length is exactly 2, a fixed-length code over four symbols is also 2, and the saving is 0. Huffman did nothing wrong; there was nothing to do. A reader who has only ever seen the skewed example carries away “Huffman compresses” as a property of the algorithm, and it is a property of the input.

The other direction is on the panel too. On a:60, b:20, c:10, d:5, e:5 the common symbol gets one bit and the two rarest get four, and the expected length falls to 17/10 against a fixed-length cost of 3. Same algorithm, three different distributions, savings of 19/25, 13/10 and 0.

Where a preset's caption is wrong

The Fibonacci-weight instance, a:1, b:1, c:2, d:3, e:5, produces the deepest tree five leaves can have: depths 4, 4, 3, 2, 1, so the tree is a path and the rarest symbols need four bits. Both of those are true and the panel prints them. The caption's reason is not: it says each merge is exactly the next weight, and the merged weights are 2, 4, 7, 12 against symbol weights 1, 1, 2, 3, 5. Only the first merge matches. After 1 + 1 = 2 the collection holds two twos, and the next merge takes both of them rather than the two and the three.

Theorem · Kraft's equality for a Huffman code

For a code produced by this algorithm on n symbols with codeword lengths ℓ₁, …, ℓₙ, the sum Σ 2^(−ℓᵢ) equals exactly 1.

A prefix code can only ever satisfy Σ 2^(−ℓᵢ) ≤ 1 — each codeword of length ℓ rules out a 2^(−ℓ) share of the space of infinite bit strings, and the shares are disjoint. Equality means nothing is left over: every bit string has a prefix that is a codeword. Huffman achieves equality because the tree it builds is full, every internal node having two children, and a full tree leaves no unused branch.

That gives a quick sanity check by hand. On the opening code the lengths are 1, 3, 3, 4, 4, 3 and the sum is 1/2 + 1/8 + 1/8 + 1/16 + 1/16 + 1/8, which is 1. On the equal-weight code four lengths of 2 give 4 · 1/4 = 1. A code whose lengths sum to less than 1 has a branch going nowhere and can be shortened; one that sums to more than 1 is not a prefix code at all.

The three checks, and what each one would catch

codesPrefixFree compares every pair of codewords, so a code that happened to be built wrongly would be caught even though the tree construction guarantees it. encodeSyms and decodeBits run the message out and back, and the panel prints the decoded text. And the decoder refuses rather than guesses: append a proper prefix of the longest codeword to a valid bit stream and it returns nothing, because the leftover bits cannot be spent.

Measured on this page: on the six-symbol alphabet, 224 bits over weight 100, expected length 56/25, saving 19/25, prefix-free confirmed pairwise, and abcdef encoded to 18 bits and decoded back unchanged. Proved on this page: Kraft's sum is exactly 1 for any code this algorithm produces. What is not on this page is the claim that no code is shorter, and that is the next thing to establish rather than something the fraction above implies.

Interactive

Huffman's code, and the proof that nothing shorter exists

The merges, the exact expected length, and every tree it is measured against

Choose the alphabet, and step through the merges

The merge slider replays the construction one join at a time and highlights the two trees being joined. The expected length is printed as a fraction first; the decimal beside it is a rounding of the printing at three places, not a second number.

Alphabet

Symbols and weights, written name:weight

A message to encode and decode again

Merge1

Symbols—

Expected bits per symbol—

A fixed-length code costs—

Prefix-free—

Round trip returns the message—

At the minimum over every tree—

A symbol is a:45. Each step merges the two lightest remaining weights, and the tree is what the merges built. The expected length is total bits / total weight — an exact fraction, printed as one. The last figure enumerates every full binary tree on this many leaves and every way of assigning the weights to them, so “Huffman is optimal” is checked here rather than cited.

Method

Building and checking a code by hand

Five steps. The last two are the ones a reader in a hurry skips, and they are the ones that catch mistakes.

Sort, then merge the two lightest, then re-insert

Write the weights in a row. Take the two smallest, write their sum above them joined by a fork, and put the sum back into the row. Repeat until one weight remains. Ties may be broken any way; different tie-breaks give different trees and the same total cost.

Read the codewords off the paths, not off the order of merging

Label every left edge 0 and every right edge 1 and walk from the root to each leaf. The length of a codeword is the depth of its leaf, which is the number of merges that symbol was carried through.

Compute the total as a sum of products, then divide

Σ wᵢ · ℓᵢ first, as an integer; then divide by Σ wᵢ. Doing it the other way round, averaging decimals, loses the exactness that lets two codes be compared.

Check Kraft's sum is exactly 1

Add 2^(−ℓᵢ) over the symbols. Anything less than 1 means a wasted branch and a code you can shorten; anything more means the lengths do not describe a prefix code at all. This is a two-line check that catches an arithmetic slip in the depths.

Encode something and decode it back

A length is a number and a round trip is a demonstration. Type a message into the panel and read the decoded line: it is the only check on the page that would notice a short code that cannot be read.

Merges, fractions, and what the checks catch

Score 0 / 0

Choose the answer you can justify.

The six-symbol alphabet, merged by hand

Weights a:45, b:13, c:12, d:16, e:9, f:5. At each step take the two smallest remaining weights, whether they are symbols or earlier merges.

step collection two lightest merged 1 45 13 12 16 9 5 5 and 9 14 4 left 2 45 13 12 16 14 12 and 13 25 3 left 3 45 16 25 14 14 and 16 30 2 left 4 45 25 30 25 and 30 55 1 left 5 45 55 45 and 55 100 done symbol weight codeword bits weight x bits a 45 0 1 45 c 12 100 3 36 b 13 101 3 39 f 5 1100 4 20 e 9 1101 4 36 d 16 111 3 48 total 100 224 expected length 224 / 100 = 56/25 = 2.240 to three places fixed length 3 bits per symbol over six symbols = 300 bits saving 3 - 56/25 = 19/25 bits per symbol Kraft 1/2 + 1/8 + 1/8 + 1/16 + 1/16 + 1/8 = 1

Five merges for six symbols, and the count is not a coincidence: each merge reduces the collection by one and the process ends at one tree, so n symbols always take n - 1 merges and produce a tree with n - 1 internal nodes.

Step 3 is the one worth watching. The lightest two are 14, a merged node, and 16, a symbol. Merged nodes compete with symbols on equal terms from the moment they are created, which is why the tree is not simply a sorted caterpillar and why the algorithm cannot be replaced by sorting the symbols once.

For a faded rehearsal, do a:1, b:1, c:2, d:3, e:5 by hand before running it. The supplied first move is 1 + 1 = 2, leaving 2, 2, 3, 5. Say what the remaining three merges are, what depth each symbol ends at, and what the expected length is as a fraction — and then say whether the merged weights reproduce the input sequence, which is what that instance's caption claims.

Common mistakes

Averaging the codeword lengths instead of weighting themThe expected length is Σ wᵢ ℓᵢ / Σ wᵢ, not the mean of the lengths. On the opening alphabet the mean length is 18/6 = 3 and the expected length is 56/25, which is 2.24 — a difference of three quarters of a bit per symbol, and the entire point of the algorithm.

Believing Huffman always compressesOn four equal weights the saving is exactly zero and the panel says so. The algorithm is optimal on every input and useful only on skewed ones, and those are different statements. Quoting a compression figure without quoting the distribution it came from is quoting a measurement as though it were a bound.

Taking the Fibonacci caption's reason at face valueThat instance really does produce the deepest tree five leaves allow, and the rarest symbols really do need four bits. But the merged weights are 2, 4, 7, 12 and the caption says each merge is the next input weight, which stops being true at the second merge. Read the merge table: it is the run, and the caption is not.

Check your understanding

✓

Finish when you can build the tree, produce the exact expected length as a fraction, and check the result three ways without looking anything up.

You should be able to merge by hand and get the same tree shape the panel draws, compute Σ wᵢ ℓᵢ and divide, verify Kraft's sum is 1, explain what the round trip catches that a length does not, and say why a saving of zero on equal weights is not a failure.

Note: Everything on this page is about the code the algorithm produced. None of it says that no other code is shorter, and the fraction 56/25 is perfectly consistent with some cleverer tree reaching 55/25. Establishing that no such tree exists is a separate argument with two lemmas behind it, and “Why Huffman Is Optimal” both proves it and checks it against every tree.