Huffman coding

Why Morse code gives the letter E a single dot

Huffman coding gives common symbols short codes and rare ones long codes, so messages shrink. Morse code does this by hand: E, the most common English letter, is one dot. Huffman's 1952 recipe finds the best such code.

Take the 8-letter message AAAABBCD. With a fixed 2 bits per letter it takes 16 bits. Huffman gives A the code 0, B the code 10, C 110 and D 111, so the message takes 14 bits.

Huffman coding

Every PNG image and .gz download is packed with Huffman codes

ZIP files, gzip and PNG images all use DEFLATE. It first replaces repeated chunks with short back-references, then Huffman-codes the result so the most common bytes get the shortest bit patterns.

Baseline JPEG photos also use Huffman coding as their final step, to pack the numbers that describe each block of the image.

Huffman coding

Merge the two rarest letters until only one tree is left

Count each symbol, then keep joining the two smallest counts. In AAAABBCD, C(1) and D(1) make 2, that joins B(2) to make 4, then A(4) to make 8. Label left branches 0 and right 1; each path from the top is a code.

Because every letter sits at a leaf of the tree, no code is the start of another code. This prefix-free property means the bits 010110 can only split as 0 | 10 | 110, which is ABC, so no separators are needed.

It is optimal because the two rarest symbols must sit at the deepest level of the best tree. Making them siblings costs nothing, and the merge turns the problem into a smaller one with one fewer symbol.