Huffman Coding

Optimal prefix codes by merging the two rarest symbols.

The idea

Huffman coding produces the binary code of least average length for a set of symbols with known frequencies. A fixed-length code spends the same number of bits on every symbol; giving the frequent symbols shorter codewords costs less on average, provided the decoder can still tell where one codeword ends and the next begins.

A prefix code guarantees that. It assigns each symbol a binary codeword so that no codeword is an initial segment of any other. Reading the stream left to right, the first codeword the bits match is the only one they can match, so each symbol is decoded with no lookahead.

Prefix codes correspond exactly to binary trees. Place the symbols at the leaves, label each left branch $0$ and each right branch $1$, and read a symbol's codeword off the path from the root to its leaf. No leaf lies on the path to another leaf, so no codeword is a prefix of another.

Huffman's algorithm chooses the tree.

Algorithm.

Algorithm: Huffman Coding Input: the symbols with their frequencies Output: a prefix code of least average codeword length 1. make each symbol a one-node tree, weighted by its frequency 2. join the two trees of smallest weight under a new parent, weighted by the sum of theirs 3. if more than one tree remains, go to step 2 4. return the code read off the final tree // codeword = path from root to leaf

Deep leaves carry long codewords, so the rare symbols sink while the frequent ones stay near the root, and no prefix code achieves a smaller average codeword length.

Ways to work on it

• Walkthrough. Prefix codes from a tree and Huffman's idea.
• Practice. Read a codeword from the Huffman tree.
• Hardest. Construction order and expected codeword length.

Not sure where to start? Take the ten-question placement test.