Source Coding: Huffman and Shannon-Fano With easy examples.

Source coding represents data with as few bits as possible by giving short codes to frequent symbols and long codes to rare ones — why a ZIP file shrinks. The two classics are Huffman coding (optimal, built bottom-up) and Shannon-Fano coding (top-down splitting). Both yield prefix codes, where no code is another's prefix, so decoding is unambiguous.

These algorithms live inside ZIP, JPEG, MP3 and fax machines. They also make entropy concrete — Shannon's proof that no lossless code averages fewer bits per symbol than H. Learning both shows the gap between an optimal algorithm and a merely reasonable one.

Key Concepts

• Entropy: the minimum average bits/symbol, H = −Σ p(i)·log2 p(i) — the target every code is graded against.
• Prefix code: e.g. {0, 10, 110, 111} decodes uniquely left-to-right; satisfies Kraft inequality Σ 2^(−li) ≤ 1.
• Huffman: repeatedly merge the two least probable symbols, label branches 0/1, read codes root-to-leaf. Provably optimal among prefix codes.
• Shannon-Fano: sort by probability, repeatedly split into halves of near-equal total probability (0/1 per half). Simpler, but not always optimal.
• Average length: L = Σ p(i)·l(i).
• Efficiency: η = (H/L) × 100%; redundancy R = L − H counts wasted bits/symbol.

Formulas

Entropy H = −Σ p(i) log2 p(i) sets the floor; average length L = Σ p(i) l(i) measures the code; η = H/L grades it. Huffman guarantees minimal L among prefix codes with H ≤ L < H + 1. Equality L = H occurs exactly for dyadic probabilities (1/2, 1/4, …). Shannon-Fano also satisfies L < H + 1 but can sit strictly above Huffman's L — the textbook contrast between optimal and merely good.

Worked Example

Huffman-encode A = 0.4, B = 0.3, C = 0.2, D = 0.1. Step 1: merge C + D (0.2 + 0.1) → CD = 0.3. Step 2: merge B + CD → 0.6. Step 3: merge A + 0.6 → root. Step 4: codes: A = 0, B = 10, C = 110, D = 111. Step 5: L = 0.4×1 + 0.3×2 + 0.2×3 + 0.1×3 = 1.9 bits/symbol. Step 6: H = −(0.4 log2 0.4 + 0.3 log2 0.3 + 0.2 log2 0.2 + 0.1 log2 0.1) ≈ 0.5288 + 0.5211 + 0.4644 + 0.3322 = 1.8465. Step 7: η = 1.8465/1.9 ≈ 97.2%. Fixed 2-bit coding needs 2.0 — Huffman saves 5% here, far more on skewed distributions.

Common Misconceptions

• "Huffman always reaches entropy." Only for dyadic probabilities; generally H ≤ L < H + 1 — optimal among prefix codes, not equal to H.
• "Shannon-Fano always matches Huffman." They often differ; Shannon-Fano's greedy splits can be strictly worse (the classic {0.35, 0.17, 0.16, 0.16, 0.16} counterexample).
• "Fixed-length codes compress fine." 8-bit ASCII uses 8 bits per character while English entropy is ~4–5 bits — Huffman-style coding nearly halves the size.

Real-World Applications

• ZIP/DEFLATE: LZ77 plus Huffman compresses files everywhere.
• JPEG: Huffman-codes the quantized DCT coefficients of every photo.
• MP3/AAC: Huffman squeezes the quantized audio spectrum.
• Fax (Group 3): modified Huffman codes runs of black/white pixels.

Source coding is applied probability: entropy sets the speed limit, Huffman drives at it by merging the rarest symbols first, Shannon-Fano shows a reasonable-but-imperfect strategy. Every zipped file and JPEG is these 1950s ideas — Shannon 1948, Huffman's 1952 term paper — still earning their keep.