Huffman codes with examples

A Huffman code is an optimal variable-length prefix code: for a given set of symbol probabilities, no other symbol-by-symbol code has a smaller average length $\bar L$. Frequent symbols get short code words.

Procedure:

1. List the symbols in decreasing order of probability.
2. Combine the two lowest probabilities into a new probability equal to their sum.
3. Put the sum in the reordered list, as high as possible among equal values.
4. Repeat until only two (then one) probabilities remain.
5. Going back from the last stage, assign 0 to one branch and 1 to the other at each merge; a symbol's code is the sequence of bits on its path.

Example: five symbols A–E with $P = \{0.4, 0.2, 0.2, 0.1, 0.1\}$.

Reduction (sum of two lowest moved up as high as possible):

$$\begin{aligned} \bar L &= 0.4(2)+0.2(2)+0.2(2)+0.1(3)+0.1(3) = 2.2\ \text{bits/symbol} \\ H &= 2.1219\ \text{bits/symbol}, \qquad \eta = \frac{2.1219}{2.2} = 96.45\% \end{aligned}$$

A fixed-length code would need 3 bits (efficiency 70.7 %). No code word is a prefix of another, so "0001110" decodes uniquely as 00 | 011 | 10 = A, E, B. Huffman coding is used in JPEG, MP3 and ZIP.