power-law: Huffman Coding - creation or an accident?

David A. Huffman, was the creator of Huffman Coding.

While getting his masters degree in 1951, a professor gave his students the option of solving a difficult problem instead of taking the final exam. The problem was to find the most efficient binary code. Opting for what he thought was the easy way out, David tried to find a solution to the “smallest code” problem. What his professor didn’t tell him is that no one at that time knew the best solution. As the term drew to a close, David realized he’d have to start studying for the exam and started throwing away his scratchings on the problem. As one of the papers hit the trash can, the algorithm came to him.

He published the paper “A Method for the Construction of Minimum Redundancy Codes” describing his algorithm in 1952. This came to be known as Huffman Coding. He even outdid his professor, who had worked with information theory inventor Claude Shannon to develop a similar code. Huffman avoided the major flaw of the suboptimal Shannon-Fano coding by building the tree from the bottom up instead of from the top down. At the time he didn’t consider copyrighting or patenting it, because it was just an algorithm, and he didn’t make a penny off of it. Because of its elegance and simplicity, it is described in many textbooks and several web pages. Today derivative forms of Huffman Coding can found in common electronics and web pages (for example, the Jpeg image file format).

He eventually became a professor at UCSC School of Engineering. Later, his interest turned to the complex mathematical properties of zero-curvature surfaces. “Proofs” of his concepts led to elegant paper foldings which belie their complex mathematical origins. Some of them have even been displayed in art museums.

Here are three examples of his work.