Begin forwarded message:

> From: James Koppel <darmaniiii / yahoo.com>
> Date: May 11, 2007 9:21:35 PM CDT
> To: submission / rubyquiz.com, submission / rubyquiz.com
> Subject: Please Forward: Ruby Quiz Submission
>
> This is my solution to Ruby Quiz #123.
>
> I found the description given on the site woefully incomplete.  
> Specifically, the example tree would have lead me to believe that  
> all Huffman trees would take that shape. Luckily, there were many  
> other sources available to clear up the confusion, as well as  
> provide the necessary algorithm for creating Huffman trees.
>
> It fulfills the extra credit, storing the last tree made into a  
> file using the default serialization.
>
> $serialized_tree_file = "huffmantree.dat"
>
> class HuffmanTreeNode
>   attr_accessor :value, :weight, :left, :right
>
>   def initialize(value, weight, left=nil, right=nil)
>     @value = value
>     @weight = weight
>     @left = left
>     @right = right
>   end
>
>   def char_code(c)
>     return "" if leaf?
>     if @right.value.include? c
>       "1" + @right.char_code(c)
>     else
>       "0" + @left.char_code(c)
>     end
>   end
>
>   #For Huffman tree algorithm
>   def +(oth)
>     HuffmanTreeNode.new(value + oth.value, weight + oth.weight,  
> self, oth)
>   end
>
>   def leaf?
>     !(left || right)
>   end
>
>   def padding_character
>     return @value if leaf?
>     @right.padding_character
>   end
> end
>
> #Algorithm for creating a Huffman tree:
> #Take the two nodes with the smallest weights (frequencies)
> #Replace them with a node containing said nodes as children and with
> #weight equal to the sum of their weights (purpose of + method)
> #Repeat untril 1 node is remaining. That is the root of your  
> Huffman tree
> def create_huffman_tree(nodes)
>   return nodes.first if 1 == nodes.length
>
>   nodeArr = nodes.sort_by{|n| n.weight}
>   create_huffman_tree(nodeArr[2..-1] << (nodeArr[0] + nodeArr[1]))
> end
>
> def encode(str)
>
>   tree = create_huffman_tree(
>    str.split(//).zip(str.split(//).map{|c|
>     str.count(c)}).uniq.map{|x| HuffmanTreeNode.new(*x)})
>
>   #Serialization
>   File.open($serialized_tree_file, "w") do |f|
>     Marshal.dump(tree, f)
>   end
>
>   str += tree.padding_character
>
>   str.split(//).map {|c| tree.char_code(c)}.join
> end
>
> def decode(encoded)
>   tree = nil
>   File.open($serialized_tree_file) do |f|
>     tree = Marshal.load(f)
>   end
>
>   decoded = ""
>
>   #Removing any formatting
>   encoded.gsub!(/[^01]/,"")
>
>   #Removing padding character
>   encoded.sub!(/#{tree.char_code(tree.padding_character)}0*?$/,"")
>
>   node = tree
>
>   encoded.each_char do |c|
>     if c == "0"
>       node = node.left
>     else
>       node = node.right
>     end
>
>
>     if node.leaf?
>      decoded += node.value
>      node = tree
>     end
>   end
>
>   decoded
> end
>
> def format_encoded(encoded, original)
>   while encoded.length % 8 != 0
>     encoded += "0"
>   end
>   puts "Encoded: "
>
>   ebytes = encoded.length / 8.0
>
>   encoded.gsub!(/([01]{8})/, '\1 ')
>   encoded.gsub!(/(([01]{8} ){5})/, '\1\n').gsub!("\\n","\n")
>   puts encoded
>
>   puts "Encoded bytes:" , ebytes.to_i
>   puts "\nOriginal: ",original
>   puts "Original bytes: ", (obytes = original.length)
>
>   puts "Compressed: " + ((obytes - ebytes)/obytes * 100).round.to_s  
> + "%"
> end
>
> #Using optparse to get a -d/-e was too messy. Too much work for  
> what it is.
> puts "Encode(e) or decode(d)"
> if gets.chomp == "e"
>   puts "Enter text to encode"
>   format_encoded(encode(gets.chomp), $_.chomp)
> elsif $_.chomp == "d"
>   puts "Enter bytes to decode"
>   puts decode(gets.chomp)
> end
>
>
>
> Example:
>
> ...>ruby Huffman.rb
> Encode(e) or decode(d)
> e
> Enter text to encode
> Would you be so kind as to encode this?
> Encoded:
> 00110101 00000010 11100011 00001010 00001100
> 01111001 11011010 11001111 11110001 11000110
> 01101101 01111101 01011110 00010010 01011100
> 11100111 11000111 11111110 11001011 11100000
> Encoded bytes: 20
>
> Original: Would you be so kind as to encode this?
> Original bytes: 39
> Compressed: 49%
>
> ...>ruby Huffman.rb
> Encode(e) or decode(d)
> d
> Enter bytes to decode
> 00110101 00000010 11100011 00001010 00001100 01111001 11011010  
> 11001111 11110001 11000110 01101101 01111101 01011110 00010010  
> 01011100 11100111 11000111 11111110 11001011 11100000
> Would you be so kind as to encode this?
> ...>
>
> Luggage? GPS? Comic books?
> Check out fitting gifts for grads at Yahoo! Search.