How compression shrinks a message

Give every letter the same number of bits and the rare letters cost as much as the common ones. A Huffman code spends fewer bits on the letters you use most, found with one repeated move: merge the two rarest symbols, then do it again.

A code is a tree

A binary code gives each character of an alphabet a string of 0s and 1s. It is prefix-free if no codeword is the beginning of another; Erickson notes Morse code fails: E (one dot) starts the codes for I, S and H. That makes decoding unambiguous: read bits until they match a codeword, emit that character, repeat. Any prefix-free code is a binary tree with the characters at the leaves: left for 0, right for 1, the root-to-leaf path spells the codeword — so codeword length is leaf depth.

Why it matters

A message's encoded length is the sum, over characters, of frequency × depth. Equal-depth leaves ignore the frequencies. Erickson's worked example is a 170-letter self-describing sentence by Lee Sallows, using 20 distinct letters, in which E appears 26 times, S 27 times, and Z once. A fixed-width code — the comparison is ours, not the book's — needs 5 bits per symbol, so 850 bits for the sentence. Huffman brings that to 649, and Erickson proves no prefix-free code does better on that message. The saving is the gap between "how many symbols?" and "how often does each appear?"

Merge the two rarest

Erickson states the algorithm in one line: merge the two least frequent letters and recurse. Each character starts as its own tree, weighted by frequency. Take the two lightest — ties broken arbitrarily — and make them children of a new node weighing their sum. In the book's sentence, Z (1) and D (2) merge first into a node of weight 3. That node rejoins the pool as a character, and the step repeats. After 19 merges the 20 letters sit in one tree, and the record of merges is the code tree. Every merge pushes both subtrees one level deeper, so a character merged early — a rare one — ends deep with a long codeword; one merged late stays shallow. In the book's tree, A (3 occurrences) has a six-bit code and S (27) a three-bit one.

Since ties can go either way, Erickson points out, one set of frequencies has several different Huffman codes, with different codeword lengths for individual letters. But the total encoded length is the same for all: 649 bits for the sentence, whichever tie-break you take. With a priority queue, the construction takes O(n log n) time for n characters.

Why greed works here

Greedy rules need proof, and this one gets an exchange argument. First, in some optimal tree the two rarest characters, x and y, are siblings at the deepest level: any optimal tree has two sibling leaves at maximum depth, and swapping x into one trades a rare character downward for a commoner one upward, which cannot raise the cost. Second, once x and y are siblings, treat their parent as a single character of weight f[x] + f[y]. Erickson shows the full tree's cost equals the smaller tree's cost plus f[x] + f[y] — a constant — so minimising one minimises the other. Induction on alphabet size gives the theorem, stated as the book states it: every Huffman code is an optimal prefix-free binary code.

In short

A prefix-free code is a tree; codeword length is leaf depth; encoded size is summed frequency × depth. Merging the two lightest trees repeatedly puts rare characters deep and common ones shallow. An exchange argument makes the first merge safe, a cost identity every later one, so the result is the shortest prefix-free encoding of that message.