Huffman Coding: Building the Optimal Prefix Code

Give common symbols short codes

The core idea of Huffman coding, published by David Huffman in 1952 as a class assignment, is not new — Morse code already gives 'E' a single dot because it is the most common English letter. Huffman's contribution was an algorithm that finds the provably optimal assignment of variable-length binary codewords to a fixed alphabet, given the frequency of each symbol, subject to the constraint that codewords use a whole number of bits.

Building the tree bottom-up

Every symbol starts as its own tiny tree, a single leaf node weighted by its frequency, sitting in a priority queue keyed by weight. The algorithm then repeats one simple step until only one tree remains:

while more than one tree remains in the queue:
  a = pop the tree with the SMALLEST weight
  b = pop the tree with the next SMALLEST weight
  merge a and b under a new internal node
  new node's weight = weight(a) + weight(b)
  push the merged node back into the queue

the last remaining tree is the Huffman tree

Once the tree is built, every symbol's code is simply the path from the root to its leaf, reading 0 for "go left" and 1 for "go right" at each step. Symbols merged early — the rarest ones — end up deep in the tree with long codes; symbols that survive many rounds without being merged sit near the root with short codes.

Why the codes never collide: prefix-free

Because every symbol lives at a leaf of the tree, and no leaf is an ancestor of another leaf, no symbol's code can ever be a prefix of another symbol's code. This property — called prefix-free (or, misleadingly, a "prefix code") — is what lets a decoder read a bitstream with zero separators between codewords: it walks down from the root one bit at a time, and the instant it lands on a leaf, that symbol is unambiguous, no lookahead required. Reset to the root and repeat for the next symbol.

How close to optimal, really?

Claude Shannon's source coding theorem sets a hard lower bound on the average number of bits per symbol needed to encode a source: the entropy, H = -Σ p_i·log₂(p_i), summed over each symbol's probability p_i. Huffman coding is provably optimal among codes that use a whole number of bits per symbol, and it always lands within one bit of the entropy per symbol — often exactly at it when the frequencies happen to be powers of one-half. Its one structural weakness is exactly that "whole number of bits" restriction: a symbol with probability 0.99 should ideally cost only about 0.0145 bits, but Huffman can never give it less than 1 bit. For very skewed distributions this gap is real, and arithmetic coding and range coding close it by encoding a whole sequence of symbols into one shared fractional-bit stream instead of one codeword per symbol.

Where it is actually used

Huffman coding, or a close variant, is the entropy-coding stage inside DEFLATE (used by ZIP, gzip and PNG), JPEG, and the classic MP3 format — in every case, an earlier stage of the pipeline does the actual pattern-finding (LZ77 matching, DCT quantization) and hands the results, now heavily skewed toward certain values, to a Huffman stage that squeezes out the remaining statistical redundancy. Modern formats like Brotli, Zstandard and newer JPEG variants have largely moved to range or asymmetric numeral system coding for that final stage, precisely to close the one-bit gap Huffman cannot.

Frequently asked questions

Try it live

Everything above runs in your browser — open Huffman Coding and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.