Huffman coding: Difference between revisions

Revision as of 00:48, 6 December 2024

Revision as of 13:11, 13 January 2025

Line 45:

== History ==

In 1951, [[David A. Huffman]] and his [[MIT]] [[information theory]] classmates were given the choice of a term paper or a final [[exam]]. The professor, [[Robert M. Fano]], assigned a [[term paper]] on the problem of finding the most efficient binary code. Huffman, unable to prove any codes were the most efficient,/ was about to give up and start studying for the final when he hit upon the idea of using a frequency-sorted [[binary tree]] and quickly proved this method the most efficient.<ref>{{Cite journal | last1 = Huffman | first1 = Ken | title = Profile: David A. Huffman: Encoding the "Neatness" of Ones and Zeroes | journal = [[Scientific American]] | pages = 54–58 | year = 1991 | url = http://www.huffmancoding.com/my-uncle/scientific-american}}</ref>

In doing so, Huffman outdid Fano, who had worked with [[Claude Shannon]] to develop a similar code. Building the tree from the bottom up guaranteed optimality, unlike the top-down approach of [[Shannon–Fano coding]].