Huffman Coding — Mathematics Knowledge System

Overview

Huffman coding is a lossless data compression algorithm that produces an optimal prefix-free code for a given symbol probability distribution. Invented by David Huffman in 1952, the algorithm greedily builds a binary tree bottom-up by repeatedly merging the two least probable symbols into a single node. The resulting code assigns shorter bit strings to more probable symbols and longer ones to rarer symbols. Huffman codes are optimal among all prefix-free codes: no other prefix-free code achieves a lower expected code length. They are widely used in compression formats including DEFLATE (used by gzip and PNG), JPEG, and MP3.

Intuition

Imagine weighing letters by frequency: 'e' is heavy (common), 'z' is light (rare). Huffman coding says: pair up the two lightest letters, treat their combined weight as a new 'super-letter', repeat until one tree remains. Each merge step assigns a 0/1 bit at a branch. Tracing the path from root to leaf gives the codeword. Light (rare) symbols end up deep in the tree with long codewords; heavy (frequent) symbols are near the root with short codewords. The greedy merging of lightest pairs guarantees optimality.

Formal Definition

Definition

Given a source alphabet {x₁, …, xₙ} with probabilities {p₁, …, pₙ}, the Huffman algorithm produces a prefix-free code C* minimizing expected length L(C) = ∑ pᵢ ℓ(xᵢ). The algorithm:

L(C^*) = \min_{\text{prefix-free } C} \sum_{i=1}^n p_i \ell_i

Huffman optimality

H(X) \leq L(C^*) < H(X) + 1

Entropy bound on Huffman code length

\text{Huffman: repeatedly merge two nodes of smallest weight}

Algorithm (informal)

Notation

Notation	Meaning
$\ell(x)$	Length of Huffman codeword for symbol x
$L(C^*)$	Expected length of optimal Huffman code

Theorems

Theorem 1: Huffman Optimality Theorem

The Huffman algorithm produces a prefix-free code C^* that minimizes the expected codeword length L(C) = \sum_i p_i \ell_i over all prefix-free codes. That is, L(C^*) \leq L(C) for every prefix-free code C.

Theorem 2: Huffman Code Length Bound

For the Huffman code C^* of source X with entropy H(X), H(X) \leq L(C^*) < H(X) + 1.

Worked Examples

1
Sort by probability: A=0.4, B=0.3, C=0.2, D=0.1.
$\{A:0.4,\ B:0.3,\ C:0.2,\ D:0.1\}$
2
Merge the two smallest: D(0.1) + C(0.2) = DC(0.3). New set: {A:0.4, B:0.3, DC:0.3}.
$\{A:0.4,\ B:0.3,\ DC:0.3\}$
3
Merge the two smallest: B(0.3) + DC(0.3) = BDC(0.6). New set: {A:0.4, BDC:0.6}.
$\{A:0.4,\ BDC:0.6\}$
4
Merge last two: A(0.4) + BDC(0.6) = root(1.0). Assign 0/1 to branches.
$\text{root}(1.0)$
5
Trace codewords: A=0, B=10, C=110, D=111.
$A\to 0,\ B\to 10,\ C\to 110,\ D\to 111$
6
Compute expected length.
$L = 0.4(1)+0.3(2)+0.2(3)+0.1(3) = 0.4+0.6+0.6+0.3 = 1.9 \text{ bits}$

✓ Answer

Huffman code: A→0, B→10, C→110, D→111. Expected length = 1.9 bits. Entropy H(X) ≈ 1.846 bits, so efficiency is very high.

Practice Problems

Easyapplication

Build a Huffman code for {a:0.5, b:0.25, c:0.125, d:0.125} and compute the expected length.

Mediumproof writing

Sketch the optimality proof of Huffman coding: why does the greedy merge always produce an optimal tree?

Common Mistakes

Common Mistake

Thinking Huffman coding always achieves exactly H(X) bits per symbol.

Huffman codes achieve between H(X) and H(X)+1 bits per symbol. Exact equality occurs only when all probabilities are negative powers of 2.

Common Mistake

Confusing Huffman coding with arithmetic coding.

Huffman assigns one codeword per symbol; arithmetic coding can approach H(X) more closely by encoding blocks of symbols with fractional bits per symbol.

Quiz

Historical Background

David Huffman developed his algorithm as a student in Robert Fano's information theory course at MIT in 1951. Fano had his own (suboptimal) coding scheme (Fano coding, developed with Shannon) and challenged students to either prove it optimal or find something better. Huffman discovered the greedy bottom-up tree construction, which produces strictly optimal codes. Ironically, Huffman chose not to take the final exam so he could focus on the coding problem — and succeeded.

1948
Shannon-Fano coding introduced (top-down, near-optimal but not provably optimal).
Claude Shannon, Robert Fano
1952
Huffman publishes 'A Method for the Construction of Minimum-Redundancy Codes', proving optimality.
David Huffman
1970s
Adaptive Huffman coding (dynamically updates tree as symbols are seen) developed.
Faller, Gallager, Knuth
1980s
DEFLATE combines Huffman coding with LZ77, used in gzip and PNG.
Phil Katz

Summary

Huffman coding builds an optimal prefix-free code by greedily merging the two least probable symbols into a combined node, bottom-up.
The resulting code minimizes expected codeword length L = ∑ pᵢ ℓᵢ over all prefix-free codes.
Expected length satisfies H(X) ≤ L(Huffman) < H(X)+1; equality holds when all probabilities are powers of 1/2.
Huffman codes are used in DEFLATE (gzip, PNG), JPEG, and MP3 as the entropy-coding final stage.

References

PaperHuffman, D.A. (1952). A Method for the Construction of Minimum-Redundancy Codes. Proceedings of the IRE, 40(9), 1098-1101.
BookCover, T. and Thomas, J. (2006). Elements of Information Theory, 2nd ed. Wiley. Ch. 5.
WebsiteWikipedia — Huffman coding