Huffman Coding: How an MIT Student Found a Compression Method Still Used 75 Years Later

In 1951, David Huffman, a graduate student at the Massachusetts Institute of Technology (MIT), was given a problem that even Claude Shannon and his teacher Robert Fano had failed to solve. He had to find the most efficient way to encode symbols using binary codes of variable length while taking the frequency of each symbol into account.

For several months, Huffman tried one approach after another, but no solution emerged. Eventually, he was about to discard his notes and start preparing for his final exam when he suddenly had an insight.

Instead of building the coding tree from the top down, he decided to go in reverse: start from the bottom and repeatedly combine the two least frequent symbols.

That is how Huffman coding was born — an algorithm that produces the minimum average code-word length among all binary prefix codes for a given set of symbol frequencies.

Seventy-five years later, the algorithm is still used in formats such as ZIP, GZIP, JPEG, and MP3.