Compression & Coding

Huffman Coding

Give frequent symbols short codes and rare ones long codes — the optimal prefix-free code, built by merging the two rarest.

During the build, the forest of trees merges two-lightest-first (the blue pair). When done, the tree's left/right edges (0/1) spell each symbol's code — shown in the table.

What you're seeing

To compress text, we want short bit-codes for common symbols and longer ones for rare symbols — but the codes must be prefix-free (no code is the start of another) so a stream decodes unambiguously. Huffman builds them bottom-up: start with one tree per symbol, weighted by frequency, and repeatedly fuse the two lightest trees into one. The frequencies you see merging are the running tree weights; when a single tree remains, reading 0 for each left branch and 1 for each right gives every symbol its code. Rare symbols end up deep in the tree (long codes), frequent ones shallow (short codes).

The rule

huffman(frequencies):
    make a leaf node for each symbol, keyed by frequency
    while more than one tree:
        a = extract the two
        b = least-frequent trees
        merge them under a new node of weight (a + b)
    code(symbol) = path from root: 0 = left, 1 = right

A priority queue makes "extract the two lightest" cost O(log n), so the whole build is O(n log n) — or O(n) if the frequencies are already sorted.

The invariant

The greedy choice is provably safe by an exchange argument: in some optimal prefix code, the two least-frequent symbols are siblings at the maximum depth. Why — in any optimal code, the two deepest leaves are siblings (otherwise you could move a leaf up and shorten the code), and you may as well put the two rarest symbols there, since swapping a rarer symbol to a deeper spot never increases the expected length. So merging the two rarest into one super-symbol and solving the smaller problem recursively loses nothing — by induction Huffman is optimal. The resulting average code length lands between the Shannon entropy H = Σ pᵢ log₂(1/pᵢ) and H + 1 bits per symbol: no prefix code can beat entropy, and Huffman comes within one bit of it. The readout shows your tree's bits-per-symbol sitting in exactly that band.

The cost

Buildbits/symbol HuffmanO(n log n)[H, H+1) Fixed-width—⌈log₂ n⌉

The savings grow with how skewed the frequencies are: uniform data can't be compressed (Huffman degenerates to fixed-width), while a sharply peaked distribution gets close to its entropy. Huffman's one limitation is that it spends a whole number of bits per symbol, so it can't dip below the entropy by the fractional bit that arithmetic coding recovers — but its simplicity keeps it everywhere.

In the wild

Huffman coding is the entropy-coding back end of an enormous amount of everyday data: the final stage of DEFLATE (so: gzip, zlib, PNG, and ZIP), the entropy step in JPEG and MP3, and a component of many codecs. Modern formats increasingly use arithmetic or range coding (and ANS in Zstandard / LZFSE) to squeeze out that last fraction of a bit, but Huffman — invented by David Huffman in 1952 as a student term-paper alternative to an exam — remains the canonical, fast, simple optimal prefix code.

Try this

Hit New frequencies a few times and watch the tree reshape: the most frequent symbol always ends up with the shortest code (nearest the root), the rarest the longest. Add more Symbols and the tree deepens — but the bits-per-symbol stays pinned between the entropy and entropy-plus-one, exactly as the theorem promises.

References

  1. Huffman, D. A. "A Method for the Construction of Minimum-Redundancy Codes." Proceedings of the IRE 40(9):1098–1101, 1952. The original.
  2. Cover, T. & Thomas, J. Elements of Information Theory, 2nd ed., §5 (Data Compression) — optimality and the entropy bounds. Wiley, 2006.
  3. Cormen, Leiserson, Rivest & Stein. Introduction to Algorithms, 4th ed. (CLRS), §15.3 (Huffman codes) — the greedy exchange-argument proof. MIT Press, 2022.