Huffman Coding (1952): The Optimal Prefix Code Born from an MIT Assignment

Claude Shannon's 1948 work founded information theory and defined entropy:

H = −Σ p(x) log₂ p(x)

Entropy is the average information per source symbol in a probabilistic model. The source coding theorem gives an asymptotic limit for long block encodings; it does not say that every finite file must be at least exactly H bits per symbol.

Shannon and Robert Fano developed a top-down coding approach now called Shannon–Fano coding, but that construction is not optimal for every probability distribution.

David A. Huffman was a graduate student in Robert Fano's information-theory course at MIT. Later accounts describe an assignment choice between taking a final examination and writing a report that found the most efficient binary code.

Huffman discovered a bottom-up construction that minimises average codeword length among binary prefix codes for the given symbol weights. His four-page paper, “A Method for the Construction of Minimum-Redundancy Codes,” appeared in the September 1952 issue of Proceedings of the IRE.

The classroom choice and the story of an insight while discarding notes come from later recollections, not from the original paper itself.

Given symbols and probabilities, repeatedly combine the two least frequent nodes:

1. Create one leaf for each symbol.
2. Select the two nodes with the smallest weights.
3. Join them under a parent whose weight is their sum.
4. Repeat until one root remains.
5. Label the two outgoing edges 0 and 1.

A 45%, B 13%, C 12%, D 16%, E 9%, F 5%

F(5)  + E(9)  → FE(14)
C(12) + B(13) → CB(25)
FE(14) + D(16) → FED(30)
CB(25) + FED(30) → BCDEF(55)
A(45) + BCDEF(55) → root(100)

One valid tree assigns lengths 1, 3, 3, 3, 4, and 4. Its average length is:

L = 0.45×1 + 0.13×3 + 0.12×3 + 0.16×3 + 0.09×4 + 0.05×4
  = 2.24 bits/symbol

The entropy of this distribution is about 2.21988 bits/symbol. The Huffman code is optimal among binary prefix codes for the distribution; “close” describes its distance from the entropy bound, not uncertainty about its prefix-code optimality.

An optimal tree can place the two lowest-probability symbols as deepest siblings. Combining them creates a smaller instance of the same problem. Repeating that reduction proves the greedy construction by induction.

The scope matters. Huffman assigns an integer number of bits to each symbol's prefix codeword. Arithmetic coding instead represents an entire message as a narrowing interval, allowing a non-integer average number of bits per source symbol over the full message.

RFC 1951 defines DEFLATE as an LZ77-style sequence representation combined with Huffman coding. It defines three block types:

• uncompressed blocks,
• blocks using the fixed Huffman codes specified by the RFC, and
• blocks carrying dynamic Huffman code lengths.

DEFLATE is used by gzip, zlib, PNG, HTTP Content-Encoding: gzip, and as one common ZIP compression method. ZIP supports several methods, including stored entries, so ZIP is not synonymous with DEFLATE. A DEFLATE stream also does not build a new Huffman tree for every block.

JPEG

A common baseline sequential DCT JPEG pipeline transforms samples, quantises coefficients, and entropy-codes the result with Huffman codes. ISO/IEC 10918-1 also includes arithmetic coding, so “JPEG always uses Huffman” is too broad. Colour interpretation and common RGB/YCbCr conventions also involve application profiles such as JFIF rather than one universal step imposed on every JPEG coding process.

MP3

MPEG Layer III uses specified Huffman code tables as part of coding quantised spectral values. Huffman coding is one stage in a much larger perceptual audio codec.

HPACK

HTTP/2 HPACK can represent header fields through static and dynamic table indexes. A string literal may use the fixed Huffman table in RFC 7541 Appendix B or be sent without Huffman coding. In that table, 'a' is 5 bits, ':' is 7 bits, and 'A' is 6 bits. Compression savings depend on the strings and table state, so no one percentage applies to all traffic.

Jarek Duda published asymmetric numeral systems work in 2009, and adoption expanded during the 2010s. Zstandard uses both Huffman coding and the ANS-family Finite State Entropy technique, but not every compressed block must exercise both.

RFC 8878 permits literals to be raw, run-length encoded, or Huffman-compressed. Huffman weights can be represented directly or compressed with FSE. Literal-length, offset, and match-length symbols have predefined, RLE, FSE-compressed, and repeat-table modes.

• Huffman coding is optimal for the stated binary prefix-code problem.
• Its greedy algorithm repeatedly merges the two least-weighted nodes.
• Entropy is a model-based average limit, not a per-file magic size.
• DEFLATE, JPEG, MP3, HPACK, and Zstandard use Huffman coding within different, optional structures.
• Arithmetic coding and ANS avoid the per-symbol integer-codeword constraint in different ways.