Huffman coding

Encoding frequent symbols with few bits

In a French text, "e" is far more frequent than "z". Why encode them with the same number of bits? Huffman coding exploits this simple idea: give short codes to frequent symbols and long codes to rare symbols. On average, the message takes fewer bits.

Building the Huffman tree

A binary tree is built from the bottom up. You start from the symbols with their frequencies, and at each step you merge the two smallest frequencies into a node, until a single tree remains.

Frequencies: A=5  B=2  C=1  D=1

step 1: merge C(1) and D(1) -> node (2)
step 2: merge B(2) and (2)   -> node (4)
step 3: merge A(5) and (4)   -> root (9)

resulting tree:              (9)
                            /    \
                       A(5)      (4)
                                /    \
                             B(2)    (2)
                                     /   \
                                  C(1)   D(1)

codes (left=0, right=1):
   A = 0        (1 bit,  the most frequent)
   B = 10       (2 bits)
   C = 110      (3 bits)
   D = 111      (3 bits, the rarest)

An unambiguous code

The genius of the method: no code is the beginning of another (this is called a prefix code). A stream of bits can therefore be decoded without separators: 0 10 0 110 reads unambiguously as A, B, A, C. This property follows directly from the fact that the symbols sit at the leaves of the tree.

The gain

With the example above, encoding A B A C D costs 1+2+1+3+3 = 10 bits with Huffman, versus a fixed 2 bits per symbol (also 10 bits here for 5 symbols), but on a long text where A dominates, the savings become significant and approach the entropy of the source.

Classic pitfall

Huffman is optimal among codes that assign a whole number of bits per symbol, but it matches the entropy perfectly only if the frequencies are powers of 1/2. To do even better, arithmetic coding is used, which frees itself from the whole-number-of-bits-per-symbol constraint.