Huffman Coding

7 min read#information

A greedy algorithm that builds the optimal prefix code — frequent symbols get short codewords, rare ones long.

Contents

Huffman Coding

Huffman coding is the classic algorithm for building an optimal symbol code: given how often each symbol appears, it produces the variable-length binary code with the shortest possible average length. Frequent symbols (like the letter e in English) get short codewords; rare symbols (z, q) get long ones. David Huffman invented it in 1952 as a term-paper assignment — and it has been quietly compressing the world's data ever since, inside ZIP, JPEG, MP3, and more.

The codes it produces are prefix codes: no codeword is a prefix of another. That property lets a decoder read a bitstream left to right and split it into symbols unambiguously, with no separators.

The greedy rule

The algorithm is disarmingly simple and provably optimal:

  1. Start with one leaf node per symbol, each holding its frequency.
  2. Repeatedly take the two least-frequent nodes and merge them under a new parent whose frequency is their sum.
  3. Stop when a single node — the root — remains.
  4. Read codewords off the tree: label each left branch 0 and each right branch 1, then spell out the path from root to each leaf.

The least-frequent symbols get merged first, so they end up deepest in the tree and earn the longest codewords. That is exactly what we want.

Watch the tree build itself

The sketch below runs the algorithm live. Leaves sit at the bottom with their frequencies. Step by step, the two lowest-frequency nodes are pulled together and joined under a new parent (the running merge is highlighted). When the root is reached, the finished codewords appear — short for the common symbols, long for the rare ones.

Huffman construction on six symbols. Each step merges the two least-frequent nodes; the resulting prefix codewords are read off as left=0 / right=1. The animation loops.

Why "greedy" lands on the optimum

It feels too easy that always-merge-the-two-smallest could be optimal — but it is, and the proof rests on one observation. In any optimal prefix code, the two least-frequent symbols can be taken to sit at the deepest level as siblings. Merging them first is therefore never a mistake; you can keep doing it, and induction carries the optimality all the way to the root. The result comes within less than one bit per symbol of the Entropy floor — and arithmetic coding closes even that small gap.

In a Huffman tree, which symbol receives the longest codeword?

See also