| Rev | Author | # | Line |
|---|---|---|---|
| 2 | AristotlePagaltzis | 1 | Rumour goes that a professor once said to his class that they'd get an A+ in a course if they could invent a better compression method than dictionary compression(?), believing the problem to be impossible. Mr Huffman was sitting in the audience, and actually achieved it, creating 'Huffman Coding' and an A+ :) |
| 1 | PerryLorier | 2 | |
| 3 | HuffmanCoding is a PrefixFreeCode, which means that no code is a prefix of another one. | ||
| 4 | |||
| 5 | an example HuffmanCoding might be | ||
| 6 | |0| A | ||
| 7 | |101| B | ||
| 8 | |11|C | ||
| 9 | |||
| 2 | AristotlePagaltzis | 10 | AAAAAACAACAABA |
| 1 | PerryLorier | 11 | |
| 2 | AristotlePagaltzis | 12 | would be encoded as |
| 1 | PerryLorier | 13 | |
| 2 | AristotlePagaltzis | 14 | 00000011 00110010 10 |
| 1 | PerryLorier | 15 | |
| 2 | AristotlePagaltzis | 16 | for a total of 18 bits, compared to the 28 bits required for a straightforward 2 bits per character encoding. |
| 17 | |||
| 18 | ArithmeticEncoding which was invented later is even able to use partial bits to store characters. It is not in common use since it has been under patent by [IBM]. | ||
| 7 | AristotlePagaltzis | 19 | |
| 20 | See also http://datacompression.info/Huffman.shtml | ||
| 5 | PerryLorier | 21 | |
| 22 | ---- | ||
| 7 | AristotlePagaltzis | 23 | |
| 8 | AristotlePagaltzis | 24 | This sounds like an UrbanLegend to me. DavidHuffman was not the one invented entropy driven compression; [Claude Elwood Shannon|http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Shannon.html] and RobertMFano did that. [DavidHuffman]'s contribution was to come up with an algorithm to create an optimal dictionary given a set of weights for a set of symbols which results in the minimum possible length of the encoded data stream. --AristotlePagaltzis |
| 5 | PerryLorier | 25 | |
| 26 | It's possibly a bit of an UrbanLegend, but he did design it for a term paper, I think anyone that invents an efficient compression method such as HuffmanCoding for a term paper deserves an A+ no matter what :) --PerryLorier | ||
| 6 | JohnMcPherson | 27 | |
| 28 | I seem to recall that the professor of that class gave students the option of a mix of papers and exam, or they could "bet" their whole course grade on a single paper. DavidHuffman chose the paper option and came up with it very shortly before the paper was due... -- JohnMcPherson |
lib/blame.php:177: Warning: Invalid argument supplied for foreach() (...repeated 3 times)