Huffman Coding

The code is built for this message, not for the language.

1. Choose a short phrase and tally each letter, spaces included.
2. Write each symbol on a small card with its count.
3. Lay the cards out in a row, lowest count first.

One move, applied until nothing is left to merge.

1. Take the two cards with the SMALLEST counts.
2. Place a new card above them whose count is the sum of the two.
3. Return that new card to the row and re-sort.
4. Repeat until a single card remains — that is the root.

The path from the root to a symbol IS its code.

1. Label every left branch 0 and every right branch 1.
2. For each symbol, read the labels from root down to that card.
3. Write out your code table.
4. Encode the message and count the total bits.

Three codings of one message, measured.

1. Count the bits your Huffman code needed.
2. Encode the same message with a fixed 5-bit code per symbol and count.
3. Now try a message where every symbol appears equally often.

David A. Huffman published the algorithm in 1952, from work done as a graduate student at MIT in 1951. Robert Fano — who with Claude Shannon had devised an earlier top-down method — offered his class a choice between a final exam and solving the problem of finding the most efficient code. Huffman took the problem, worked at it for months, and was on the point of giving up when the bottom-up merging idea arrived. Fano and Shannon had both attempted it top-down; building the tree from the rarest symbols upward is what makes it optimal.

What optimal means here, precisely: no other code that assigns a whole number of bits to each symbol independently can do better. It is not the shortest possible encoding of the message in general — arithmetic coding beats it by escaping the whole-number-of-bits restriction, and methods that spot repeated PHRASES rather than repeated symbols beat it on text that repeats itself.

Where it is used: as a stage inside JPEG, PNG, MP3 and the DEFLATE algorithm behind ZIP and gzip. Those formats first transform the data so that its symbol distribution becomes lopsided, then let Huffman harvest the imbalance. Deployed at that scale, it is likely among the most-executed algorithms in existence.

Its place in the family: tally marks record every occurrence at equal cost; Morse weights by the language's general statistics; Huffman weights by this message's own statistics and proves it cannot be improved on within its rules. Each buys efficiency by knowing more about the data in advance — the theme running through every coding approach in this catalogue.