Proving Huffman Coding Correctness
You'll learn why Huffman's greedy strategy of repeatedly merging the two lowest-frequency symbols is guaranteed to produce an optimal prefix-free code.
The Core Idea
Huffman coding builds an optimal binary tree by always choosing the two least-frequent symbols to merge. But why does this greedy choice work? The proof relies on two key insights:
-
In any optimal tree, the two lowest-frequency symbols must be siblings at the deepest level. If they weren't, we could swap them with siblings at the deepest level and get an equal or better encoding—meaning the original wasn't truly optimal.
-
Once we merge the two lowest-frequency symbols, we have a smaller problem with the same structure. The merged node acts as a single symbol with combined frequency, and we can recursively apply the same logic.
The Exchange Argument
Imagine an "optimal" tree where the two rarest symbols aren't paired together at maximum depth. We can swap positions with whatever symbols are there. Since rarer symbols should have longer codes (they appear less often), moving them deeper can only improve or maintain the total cost. This contradiction shows our greedy choice is safe.
After merging the two lowest-frequency symbols into one "super-symbol," we have a smaller problem. If the solution to this smaller problem is optimal (by induction), and our greedy choice was safe, then the overall solution must be optimal too.
Why It Matters
This proof combines optimal substructure (solving smaller problems optimally) with the greedy choice property (locally optimal decisions lead to global optimum). Huffman's algorithm demonstrates that greedy approaches can be proven correct when the problem structure supports them.
Key Takeaway: Huffman coding's correctness follows from proving that pairing the two lowest-frequency symbols is always safe (exchange argument) and that this reduces to an optimal subproblem (optimal substructure).