From: Daniel Martin <martin@...>
Date: 2007-05-12T21:50:33+09:00
Subject: Re: [QUIZ] Huffman Encoder (#123)

Ruby Quiz <james@grayproductions.net> writes:

> 	Encoded Bytes:
> 	25
> 	
> 	Original:
> 	I want this message to get encoded!
> 	Original Bytes:
> 	35
> 	
> 	Compressed:  28%

I'll note that this phrase includes 16 distinct characters (" ", "!",
"I", "a", "c", "d", "e", "g", "h", "i", "m", "n", "o", "s", "t", "w").
Even if you add a special "end-of-data" character, that's only 17
distinct characters, so you would expect any Huffman code to perform
at least as well 5 bits per character; since your code is in theory
being developed to encode this exact phrase, I'd expect better
performance than that.

At 5 bits per character, if you add a special "end of data" character
to the end of the phrase so that you're encooding 36 values, that's
only 180 bits of output.  180 bits fits into 23 bytes.

I'm pointing out that the initial reference code probably has a bug in
its algorithm, since it does even worse than a naive
5-bits-per-character encoding.

For what it's worth, my current Huffman encoder when tuned to that
phrase alone compresses it into 18 bytes; when tuned to
http://norvig.com/big.txt (a large chunk of English text) it still
manages to compress that phrase to 22 bytes.

-- 
s=%q(  Daniel Martin -- martin@snowplow.org
       puts "s=%q(#{s})",s.to_a.last       )
       puts "s=%q(#{s})",s.to_a.last