Huffman Coding

Huffman coding is a lossless data compression and entropy-encoding algorithm within computation and algorithms that constructs a minimum-redundancy variable-length prefix-free code for a finite source alphabet Σ with known symbol probabilities or frequencies. Discovered in 1951 by MIT graduate student David A. Huffman as a term paper for Robert M. Fano's information theory course—surpassing the top-down Shannon–Fano coding algorithm developed by Claude Shannon and Fano—and published in the Proceedings of the IRE in 1952, Huffman's bottom-up greedy procedure repeatedly merges the two least probable symbols into a parent meta-symbol until a single full binary code trie remains.

By assigning shorter binary codewords to high-probability symbols and longer binary codewords to rare symbols while ensuring that no codeword is a prefix of any other codeword, Huffman coding achieves the minimum expected codeword length L = ∑ p_i l_i among all symbol-by-symbol uniquely decodable codes. Within computational complexity theory and information theory, the expected length of a binary Huffman code is bounded by the Shannon entropy H(X):

Consequently, Huffman coding (particularly in its lookup-table Canonical Huffman form) serves as the entropy-coding backend of compression and media standards—including DEFLATE (gzip, zlib, PNG, ZIP), bzip2 (downstream of the Burrows–Wheeler transform), JPEG, MP3, and genomic sequencing archives (CRAM, Spring).

Instantaneous Prefix-Free Codes and Binary Trie Representation

Let X be a discrete memoryless source over Σ = {s₁, ..., s_n} with probabilities P = (p₁, ..., p_n) summing to 1. A binary code C : Σ → {0, 1}⁺ assigns each symbol s_i a codeword C(s_i) of bit length l_i, with expected length L(C) = ∑_i=1..n p_i l_i. A code is prefix-free (instantaneous) if no codeword is a prefix of another; every binary prefix-free code corresponds to a binary trie whose n leaves at depths l₁, ..., l_n hold the source symbols.

Kraft–McMillan Inequality and the 1-Bit Redundancy Sandwich

Positive integers (l₁, ..., l_n) form the leaf depths of a binary prefix-free code (or any uniquely decodable code) if and only if they satisfy the Kraft–McMillan inequality:

Relaxing l_i ∈ ℝ gives the ideal fractional length l_i* = −log₂ p_i with expected value equal to the Shannon entropy H(X) = −∑ p_i log₂ p_i. Rounding up to integer Shannon code lengths l_i^S = ⌈−log₂ p_i⌉ satisfies Kraft's inequality with expected length < H(X) + 1. Because Huffman's algorithm minimizes L(C) over all prefix codes, H(X) ≤ L_Huff < H(X) + 1, achieving L_Huff = H(X) if and only if every p_i = 2^−k_i is dyadic.

Priority-Queue Merging Mechanics and van Leeuwen's Two-Queue O(n) Method

Given n symbols with weights w₁, ..., w_n, Huffman's algorithm builds an optimal full binary tree in n − 1 merges: (1) initialize n leaf nodes in a min-priority queue Q; (2) in each of n − 1 steps, extract the two minimum-weight nodes x and y, allocate a parent z with weight w(z) = w(x) + w(y), and insert z into Q; (3) return the final node as the root of T. Using a binary heap takes O(n log n) time, whereas van Leeuwen (1976) showed that maintaining two FIFO queues (Q₁ for sorted leaves, Q₂ for merged internal nodes produced in non-decreasing weight order) builds the tree in linear O(n) time once frequencies are sorted.

Two-Lemma Proof of Optimality: Greedy Choice and Optimal Substructure

1. Greedy-Choice Lemma (Sibling Property): Let x and y be two symbols with lowest probabilities p_x ≤ p_y ≤ p_i. In any optimal full prefix tree T, swapping the deepest sibling leaves a, b at depth d_max with x, y reduces or preserves expected length because (p_a − p_x)(d_max − depth(x)) ≥ 0, yielding an optimal tree T* in which x and y are deepest sibling leaves.
2. Optimal-Substructure Lemma: Contracting the sibling pair (x, y) into a meta-leaf z of probability p_z = p_x + p_y reduces expected length by p_x + p_y, so T is optimal on Σ if and only if the contracted tree T′ is optimal on (Σ \ {x, y}) ∪ {z}.

Canonical Huffman Coding and Length-Limited Package-Merge

Canonical Huffman coding (Schwartz & Kallick, 1964) transmits only the codeword lengths (l₁, l₂, ..., l_n) in the file header: sorting symbols by length l_i and then alphabetically reconstructs sequential binary codewords deterministically at the decoder. When a format caps maximum codeword length at L_max (for example, DEFLATE sets L_max ≤ 15 for fast lookup-table decoding), Larmore and Hirschberg's (1990) dynamic programming Package-Merge algorithm computes the optimal length-limited Huffman code in O(n · L_max) time.

When a single symbol dominates the alphabet with p₁ > 0.5, any symbol-by-symbol prefix code must still spend at least l₁ = 1 bit per symbol. Modern codecs overcome this 1-bit floor either by Preceding Huffman coding with Run-Length Encoding and the Burrows–Wheeler transform (as in bzip2), or by pairing Huffman coding of literals with Asymmetric Numeral Systems (ANS) as in Zstandard and the GA4GH CRAM v3.1 sequencing standard.

How does Huffman coding generalize to D-ary alphabets (D > 2)?

In D-ary Huffman coding, each merge replaces D nodes with 1 parent node, reducing the node count by D − 1 per step. To ensure that the root has a full set of D children, the initial alphabet size n must satisfy n ≡ 1 (mod D − 1), padded if necessary with 1 to D − 2 dummy zero-probability symbols before the first merge.

Why did Huffman's bottom-up method succeed where Shannon and Fano's top-down splitting failed?

Shannon–Fano coding splits the symbol set top-down into two subsets of nearly equal probability, which can force an uneven split two levels lower. Huffman's bottom-up construction guarantees via the Greedy-Choice Lemma that the two rarest symbols occupy the deepest sibling leaves in an optimal tree.

1. Huffman, D. A. (1952). "A method for the construction of minimum-redundancy codes." Proceedings of the IRE, 40(9), 1098–1101. https://doi.org/10.1109/JRPROC.1952.273898
2. Schwartz, E. S., & Kallick, B. (1964). "Generating a canonical prefix encoding." Communications of the ACM, 7(3), 166–169. https://doi.org/10.1145/363958.363991
3. van Leeuwen, J. (1976). "On the construction of Huffman trees." Proceedings of the 3rd International Colloquium on Automata, Languages and Programming (ICALP), 382–410. https://dl.acm.org/doi/10.5555/1739944.1739972
4. Vitter, J. S. (1987). "Design and analysis of dynamic Huffman codes." Journal of the ACM, 34(4), 825–845. https://doi.org/10.1145/31846.42227
5. Larmore, L. L., & Hirschberg, D. S. (1990). "A fast algorithm for optimal length-limited Huffman codes." Journal of the ACM, 37(3), 464–473. https://doi.org/10.1145/79147.79150