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\cdot 1+13\cdot 3+12\cdot 3+16\cdot 3+9\cdot 4+5\cdot 4=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 $\mathbf{O}(\mathbf{n}\lg \mathbf{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.