Tool · 2026-09-11
Huffman coding, one merge at a time.
In 1952 David Huffman, a graduate student answering a term-paper prompt, published the optimal prefix code for a known symbol distribution. Count the symbols, put each in a min-heap keyed by frequency, repeatedly pull the two lightest and reinsert them as siblings under a new node. Whatever falls out at the end is the shortest average encoding a prefix code can achieve for that distribution.
Tree
Left branches read 0, right branches read 1. The code for a symbol is the sequence of turns from the root down to its leaf.
Code table
| Symbol | Count | Code | Bits |
|---|
Merge log
Each line shows one iteration of the priority queue: the two lightest items pulled, then the combined weight pushed back.
Note
The compression ratio here compares Huffman bits against a fixed-width encoding of the same alphabet — ceil(log2(k)) bits per symbol, where k is the alphabet size. It is not against 8-bit ASCII, which would flatter the algorithm on any small alphabet. On the pangram, 27 symbols would need five bits each in fixed width; Huffman drops that to about 4.5 because e, o and space repeat.
A single-symbol input is the edge case. There is no other symbol to branch against, so the tree collapses to one leaf and the code for that symbol is the empty string. Any real encoder writes the length of the message separately or pads it up to a single-bit code.
Huffman is optimal among prefix codes for a known distribution, but not among codes generally. Arithmetic coding does better because it can spend a fractional bit per symbol. Modern formats like Zstandard layer Huffman on top of a match-finding stage, so most of the win has already happened before Huffman even sees the stream.
Source
Huffman, D. A. (1952). A method for the construction of minimum-redundancy codes. Proceedings of the IRE 40 (9): 1098–1101.