Experiment № 065 · The story
Short Words for Common Things
Why I picked it
Because the origin story is too good to leave alone. In 1951 Robert Fano gave his MIT information theory class a choice: sit the final exam, or write a term paper finding the optimal way to assign codes to symbols. Fano didn't mention that he and Shannon had already failed at it. David Huffman, twenty-five, spent months on it, got nowhere, and was throwing his notes away when the answer arrived — and it arrived because he stopped building the code the way everyone else did. Shannon and Fano had worked top down, splitting the alphabet into halves of roughly equal probability. Huffman went bottom up: find the two rarest symbols, and whatever else is true of the best code, those two must sit deepest and be siblings. Merge them, treat the pair as one symbol, repeat. Sixty-odd experiments in, I wanted one where the whole algorithm fits in a sentence and still comes with a proof of optimality — and one that is running, right now, inside every JPEG and every zip file on your machine.
What I enjoy about it
That the queue does the thinking. The strip of trees is kept sorted by weight, so the next merge is always the leftmost pair — there is no search anywhere, no comparing of alternatives, no backtracking. Just take the two smallest, over and over. And nothing has a code until the very last merge: the bits are read off the finished tree from the root down, so a letter's code is not decided at any point, it is a consequence of how many merges happened above it. Watch where the common letters end up — a hair below the root, one or two bits deep — while the ones that appear twice sink to the floor. The moment I like best is the fixed-width toggle on the eight-equal preset: Huffman spends exactly three bits per symbol, saves absolutely nothing, and is still provably optimal. When every symbol is equally surprising, there is no cleverness available. That's not a failure of the algorithm; it's the algorithm telling you the truth about your data.
Something you might take away
Price should track surprise. Shannon's entropy says a symbol of probability p is worth −log₂p bits and no fewer, and Huffman gets within one bit of that floor without ever computing a logarithm — it just lets frequency decide depth. But look at the almost all one letter preset: the floor is around a third of a bit per symbol, and Huffman still pays a full bit, because the cheapest code it is allowed to write is one bit long. That gap isn't inefficiency, it's the granularity of the format — and it is the entire reason arithmetic coding, which lets a symbol cost a fraction of a bit, exists at all. So when something optimal still looks expensive, the question worth asking isn't whether the algorithm is smart enough. It's what unit you've been forced to pay in.