James Gray
5/13/2007 3:00:00 PM
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.