Differences between version 2 and predecessor to the previous major change of HuffmanCoding.
Other diffs: Previous Revision, Previous Author, or view the Annotated Edit History
| Newer page: | version 2 | Last edited on Saturday, February 22, 2003 5:17:01 am | by AristotlePagaltzis | Revert |
| Older page: | version 1 | Last edited on Friday, February 21, 2003 5:41:34 pm | by PerryLorier | Revert |
@@ -1,19 +1,20 @@
-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.
+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+ :)
-Mr
Huffman was sitting in
the audience,
and actually achieved it, creating '
Huffman Coding
' and
an A+ :)
+:This sounds like an UrbanLegend to me. [
Huffman]
was not
the one invented entropy driven compression; [Shannon]
and [Fano] did that. [
Huffman]
'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
HuffmanCoding is a PrefixFreeCode, which means that no code is a prefix of another one.
an example HuffmanCoding might be
|0| A
|101| B
|11|C
-AAAAAACAACAABA
+
AAAAAACAACAABA
-would be encoded as:
-00000011 00110010 10
+would be encoded as
-for a total of 18 bits, instead of 28 bits if you used 2 bits per charactor.
+ 00000011 00110010 10
-ArithmeticEncoding was invented later and allowed you
use partial bits to store charactors, but
has been under patent by [IBM].
+for a total of 18 bits, compared to the 28 bits required for a straightforward 2 bits per character encoding.
+
+
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].
