Huffman Codes

Suppose we want to store or transmit a file of text drawn from some alphabet of symbols, letters being the obvious case. A fixed-length code assigns every symbol a bit string of the same length: with $6$ symbols we would spend $3$ bits each ($\lceil {\log }_{2}6\rceil =3$), regardless of how often each symbol appears. But real text is lopsided. In English, e and t are everywhere while q and z are rare. It is wasteful to spend as many bits on z as on e.

A variable-length code exploits this skew: give the frequent symbols short codewords and the rare symbols long ones, so the total bit count drops. Huffman's 1952 algorithm finds the variable-length code that compresses a given file as much as any such code possibly can, and it does so with a beautifully simple greedy rule.¹ This lesson is the payoff of the greedy method: a non-obvious algorithm, an elegant correctness proof, and a result used billions of times a day inside JPEG, MP3, gzip, and PNG.

Prefix-free codes

Variable-length codes carry a hazard. If e is 0 and t is 01, then the stream 001 is ambiguous (is it e e t? e ??) because the codeword for e is a prefix of the codeword for t. To decode unambiguously without separator symbols, we insist on a prefix-free code (also called a prefix code): no codeword is a prefix of any other.²

Prefix-freeness buys us instant, unambiguous decoding: read bits left to right, and the moment the bits so far match a codeword, that codeword is the only possible symbol, so emit it and start fresh. Remarkably, restricting to prefix-free codes costs nothing in compression: for any uniquely decodable code there is a prefix-free code at least as good, so we lose no optimality by considering only these.

Every prefix-free code corresponds to a binary tree. Symbols sit at the leaves; the path from the root to a leaf spells its codeword, taking 0 for a left edge and 1 for a right edge. Because symbols are only at leaves, no codeword can be a prefix of another: a prefix would mean one symbol's leaf lies on the path to another's, impossible when both are leaves. The depth of a leaf is its codeword's length.

The compression problem

Let the alphabet be $C$, and let symbol $c\in C$ occur with frequency $c.freq$ (its count, or its probability) in the file. In a code tree $T$, let $d_T(c)$ be the depth of $c$'s leaf, the number of bits in its codeword. The total number of bits to encode the whole file is the cost of the tree:

An optimal code's tree is always full — every internal node has exactly two children. (A one-child node wastes a bit: promote its subtree and every codeword beneath it shortens.) So with $n=\left|C\right|$ symbols, an optimal tree has $n$ leaves and exactly $n-1$ internal nodes.

Huffman's algorithm

Huffman's greedy insight is to think about the tree bottom-up, and to ask: which two symbols belong deepest in the tree? Surely the two least frequent ones, since they are the cheapest to bury: multiplying their long codewords by small frequencies costs little.³ So make the two rarest symbols siblings at the bottom, merge them into a single super-symbol whose frequency is their sum, and repeat on the smaller alphabet. Each merge fuses two nodes into one, so after $n-1$ merges a single tree remains.

A min-priority queue keyed on frequency makes the two least frequent cheap to extract.

Each iteration removes two nodes and inserts one, shrinking the queue by one; the single survivor after $n-1$ rounds is the root of the finished tree. Reading the tree from the root gives every symbol's codeword.

Building a Huffman tree by hand

Take a six-symbol alphabet with these frequencies (in thousands of occurrences), the classic CLRS example:

We repeatedly merge the two smallest frequencies:

1. Merge f$(5)$ and e$(9)$ → node $(14)$.
2. Merge c$(12)$ and b$(13)$ → node $(25)$.
3. Merge $(14)$ and d$(16)$ → node $(30)$.
4. Merge $(25)$ and $(30)$ → node $(55)$.
5. Merge a$(45)$ and $(55)$ → root $(100)$.

Watching the priority queue evolve makes the bottom-up construction concrete: each step extracts the two smallest weights and re-inserts their sum, so the queue loses one element per round until a single root survives.

The resulting tree, with left edges labeled 0 and right edges 1, is:

Reading root-to-leaf gives the codewords:

The frequent a gets a single bit; the rare e and f get four. The cost is

thousand bits. A fixed-length $3$-bit code would spend $3\cdot (45+13+12+16+9+5)=300$ thousand bits, so Huffman saves about $25\%$, and no prefix-free code does better.

Why Huffman is optimal

Huffman is a greedy algorithm, so its proof follows the template from the previous lesson exactly: a greedy-choice property proved by an exchange argument, then optimal substructure to close the induction.⁴

The greedy choice is safe

The intuition is the exchange argument in one sentence: the rarest symbols belong deepest, so pushing them down and pulling frequent symbols up can never cost more.

The two swaps are easiest to see side by side. In any optimal tree $T$ the deepest sibling pair holds some leaves $a,b$; the globally rarest symbols $x,y$ may sit higher up. Exchanging $x$ with $a$ and $y$ with $b$ sends the rare symbols to the bottom and lifts the more frequent ones — and the cost only drops, because each moved-down leaf is rarer and each moved-up leaf is more frequent.

Optimal substructure

Together the two lemmas give the theorem by induction on $\left|C\right|$: the base case of one symbol is trivial, and each merge is both safe (greedy choice) and composable (substructure). Huffman's algorithm produces an optimal prefix-free code. $■$

Running time

The cost is dominated by the priority-queue operations. Building the initial min-heap from $n$ symbols takes $O(n)$. The loop runs $n-1$ times, and each iteration does two $\text{Extract-Min}$s and one Insert, each $O(\log n)$ on a binary heap. Hence

If the frequencies arrive already sorted, two simple FIFO queues replace the heap (one of original leaves, one of merged nodes, both kept in nondecreasing frequency), and each extract two smallest is $O(1)$, giving an $O(n)$ algorithm. The $O(n\log n)$ bound, like activity selection's, is really the cost of getting the symbols into sorted order.

Where Huffman lives and where it doesn't

Huffman coding is optimal among codes that assign each symbol a whole number of bits independently. That last clause hides its one weakness: when a symbol's ideal codeword length ${\log }_2(1/p)$ is fractional (for a symbol of probability $0.9$, ideally $0.15$ bits), Huffman must round up to $1$ bit and loses ground. Arithmetic coding and range coding sidestep the whole-bit floor and can beat Huffman on highly skewed sources, which is why modern compressors often prefer them. Still, Huffman's simplicity, speed, and provable optimality within its class keep it embedded in DEFLATE (gzip, PNG, ZIP), JPEG, and MP3 to this day. It remains the textbook proof that a greedy algorithm, properly justified, can be exactly optimal, not merely a good heuristic.

Takeaways

• A prefix-free code lets a stream decode unambiguously; it is exactly a binary tree with symbols at the leaves, codeword length = leaf depth.
• The goal is to minimize $B(T)={\sum }_{c}c.freq\cdot d_T(c)$; optimal trees are full.
• Huffman's algorithm greedily merges the two least-frequent nodes via a min-priority queue, $n-1$ times, building the tree bottom-up.
• Optimality follows the greedy template: an exchange argument shows the rarest symbols belong deepest (greedy choice), and optimal substructure closes the induction.
• Running time is $O(n\log n)$, the cost of the heap operations, dropping to $O(n)$ when frequencies are pre-sorted.