Huffman Coding Origin Story
Now almost 70 years old, the Huffman coding origin story is one of my favorites.
In 1951 David A. Huffman and his classmates in an electrical engineering graduate course on information theory were given the choice of a term paper or a final exam. For the term paper, Huffman's professor, Robert M. Fano, had assigned what at first appeared to be a simple problem. Students were asked to find the most efficient method of representing numbers, letters or other symbols using a binary code. Besides being a nimble intellectual exercise, finding such a code would enable information to be compressed for transmission over a computer network or for storage in a computer’s memory.
Huffman worked on the problem for months, developing a number of approaches, but none that he could prove to be the most efficient. Finally, he despaired of ever reaching a solution and decided to start studying for the final. Just as he was throwing his notes in the garbage, the solution came to him. "It was the most singular moment of my life," Huffman says. "There was the absolute lightning of sudden realization."
That epiphany added Huffman to the legion of largely anonymous engineers whose innovative thinking forms the technical underpinnings for the accoutrements of modem living—in his case, from facsimile machines to modems and a myriad of other devices. "Huffman code is one of the fundamental ideas that people in computer science and data communications are using all the time," says Donald E. Knuth of Stanford University, who is the author of the multivolume series The Art of Computer Programming.
Huffman says he might never have tried his hand at the problem—much less solved it at the age of 25—if he had known that Fano, his professor, and Claude E. Shannon, the creator of information theory, had struggled with it. "It was my luck to be there at the right time and also not have my professor discourage me by telling me that other good people had struggled with this problem," he says.
An excerpt from the September 1991 issue of Scientific American. Full text available at huffmancoding.com.
There's so much to like about this.
- An all is lost moment followed by a breakthrough.
- An epiphany that only came once he stepped back.
- A mentor that challenged him without undue pressure.
- Permanent recognition and glory for contributing his best work even though he didn't receive monetary rewards.