Huffman codes

Prefix-free codes

To compress a file we give each character a binary codeword and concatenate them. A prefix-free code (a.k.a. prefix code) is one where no codeword is a prefix of another. That guarantees unambiguous decoding: scan bits left to right, and the moment they match a codeword you have found that character — no backtracking needed.

Every prefix-free code is a full binary trie whose *leaves* are the characters: a left edge is a 0, a right edge is a 1, and a character's codeword is the path from the root to its leaf. The codeword length equals the leaf's depth.

Cost of a code

For a tree $T$ over alphabet $C$ with frequencies $c.freq$, the number of bits to encode the whole file is

$$B(T) = \sum_{c \in C} c.freq \cdot d_T(c),$$

where $d_T(c)$ is the depth of $c$'s leaf (its codeword length). An optimal code minimizes $B(T)$, so frequent characters should sit shallow (short codewords) and rare ones deep.

Worked example. With frequencies (in thousands) $a{:}45,\,b{:}13,\,c{:}12,\,d{:}16,\,e{:}9,\,f{:}5$ (CLRS Fig. 15.4), Huffman gives $a$ a length-1 codeword and $b,c,d$ length 3, $e,f$ length 4, so

$$B(T) = 45\cdot1 + 13\cdot3 + 12\cdot3 + 16\cdot3 + 9\cdot4 + 5\cdot4 = 224.$$

A 3-bit fixed-length code would cost $300$ — Huffman saves about 25%.

The greedy algorithm

Put every character into a min-priority queue keyed by frequency. Then repeat $|C| - 1$ times: extract the two lowest-frequency nodes $x$ and $y$, make a new internal node $z$ with $z.freq = x.freq + y.freq$ and children $x, y$, and insert $z$. The last node left is the root.

Building the heap is $O(n)$; each of the $n-1$ iterations does two EXTRACT-MINs and one INSERT at $O(\lg n)$ each, so the total is $\boldsymbol{O(n \lg n)}$.

Why it is optimal (exchange argument again). *Lemma 15.2 (greedy choice):* the two lowest-frequency characters $x, y$ can be made sibling leaves at maximum depth in some optimal tree — swap them down toward the deepest leaves; since they have the smallest frequencies, moving them deeper cannot increase $B(T)$. *Lemma 15.3 (optimal substructure):* merging $x, y$ into a node $z$ of frequency $x.freq + y.freq$ yields a smaller alphabet whose optimal tree, with $z$ re-expanded, is optimal for the original. Induction over the merges proves Huffman optimal.