Saramsha

No. 019  ·  5 October 2026

The Rarest Two, Every Time

A fixed-length code spends the same bits on every letter. Huffman's trick spends fewer on the common ones: take whatever is rarest, pair it with the next rarest, and repeat until one pile is left. Type anything below, then press play to watch its own code assemble itself, merge by merge.

Your text

—

About this piece

A code with no wasted bits

Write a message in plain ASCII and every character, however common, costs exactly eight bits — the letter e, which turns up in English roughly an eighth of the time, pays the same fare as z, which barely turns up at all. That is wasteful in a precise, measurable sense: if some symbols are far more likely than others, a code that gives the likely ones short bit-strings and the unlikely ones long ones will, on average, need fewer bits per character overall — provided it can still be decoded. A prefix code is what makes that decodable: no symbol's code may be the start of any other symbol's code, so a receiver reading bit by bit always knows the instant one code has ended, with no delimiter needed.

Finding the best such code was an open problem in 1951, when David Huffman was a graduate student taking Robert Fano's information theory course at MIT. Fano — who had himself devised a good, but not always optimal, way of building these codes by splitting symbols top-down into evenly weighted halves — offered the class a choice: sit a final exam, or solve the general problem of constructing a provably minimal one. Huffman took the second option, and rather than splitting from the top, found that building from the bottom always works: take the two least frequent symbols in the whole set, fuse them into one combined symbol weighing their sum, and repeat the search on what remains, now one symbol shorter. He published it in 1952 as "A Method for the Construction of Minimum-Redundancy Codes" — the algorithm running on this page, unchanged.

The idea that makes it provably best, not merely reasonable, is an exchange argument. In any optimal prefix code, the two rarest symbols must sit at the two deepest, sibling positions of the tree — because if either one sat higher, swapping it with whatever does sit at the deepest leaf could only shorten the total, contradicting optimality. So fusing the two rarest symbols first, and giving the combined pair's weight to a single stand-in symbol, never costs anything: whatever is optimal for the shorter list stays optimal once the stand-in is split back into its two children. Repeating that fact all the way down is the whole proof. Fano's top-down split has no such guarantee, which is why it can — rarely, but genuinely — land on a slightly longer code than Huffman's.

The tree above is read code-by-branch: starting at the top, a 0 means "the left branch," a 1 the right, and the string collected by the time you reach a symbol's tile is that symbol's code — short for the symbols that merged late, long for the ones fused in early at the bottom. That asymmetry is the entire point, and it is also why shuffling your text's letters, below, changes nothing about the total bits spent: the algorithm only ever looks at how often each symbol occurs, never at the order they arrive in. (A shuffle can still change which exact symbol gets a 0 versus a 1 when two of them are tied on frequency — ties have to be broken somehow, and that does not affect the total either.)

Huffman's code reaches the best possible result for its own rules, but those rules have a built-in ceiling: a code assembled from whole bits per symbol can't go below Shannon entropy — −Σ p log2 p, the theoretical floor Claude Shannon derived for how compressible a source can be, given here as "entropy" in the arithmetic panel. When every symbol's probability happens to be a power of one-half, Huffman hits that floor exactly; everywhere else, rounding each code to a whole number of bits leaves a little on the table, at most one bit per symbol in the worst case. Closing that last gap needs a different kind of code entirely — arithmetic coding, and its modern faster cousin range/ANS coding, which assign one fractional-bit-length code to an entire message at once instead of one whole-bit code per symbol. Both are now common, but Huffman's is simpler to build, simpler to decode fast, and good enough that it has stayed in daily use for seventy years: it is the final stage inside ZIP and gzip's DEFLATE, inside PNG, and inside JPEG and MP3, in each case cleaning up after an earlier transform has already done the hard work of making some values far commoner than others.

Everything here runs in your browser; nothing you type is sent anywhere. Ties in frequency are broken by which symbol has existed longest, which keeps the tree the same every time you reload the same text. A single repeated character is given the one-bit code 0 by convention, since no real code can be zero bits long. ?text=... in the address bar preloads a message. Space plays or pauses the build, ← → step through it one merge at a time, R shuffles the letters, and ? or I reopens this page.