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

Ruby Quiz <james@grayproductions.net> writes:

> The quiz this time is to write a program to implement a compression
> program using Huffman encoding.

I'd like to comment on and regularize a few of the "extra credit"
portions.

First off, without knowledge of the tree, one can't decode the Huffman
encoding given in the quiz since the message:
  I want this message to get encoded!
encodes to the same thing as:
  V jnag guvf zrffntr gb trg rapbqrq!

So, with a Huffman encoding one always needs to know the tree
structure when doing the decoding.  This means that usually what one
does with Huffman encoding is use some big training database to build
up your tree, and then one re-uses the same tree again and again.

Therefore, I want to add these switches:

-d       Decoding mode.  (Default is encoding)

-T file  Generate tree and store it to file.  Do not produce other
         output. 

-t file  Use file to retrieve your tree. (for either encoding or
         decoding)

-i file  Use file as input instead of reading command line arguments

-o file  Use file as output instead of writing to standard output
         (Note: compression statistics should still be written to
          standard output.  file should contain only the message)

Also, I'll note that the quiz description can give a false impression
of Huffman encoding and how to build up the tree.  For example, after
reading that I'd forgive anyone who thought that Huffman encoding
always assigned to each letter a code of some number of 1s followed
by a zero, except the least frequent letter which is assigned a code
of all 1s.  In fact, it only works out to that for certain frequency
distributions.

Although I don't want to spoil things I'll point at the section
labeled "Basic technique" in the wikipedia article on Huffman coding
(http://en.wikipedia.org/wiki/Huffman_coding) and mention that I won't
quite be using the algorithm they mention there, but will be using
something vaguely similar.  (That is, I will be building the tree from
the bottom up rather than the top down)

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