Please Forward: Ruby Quiz Submission

ruby-talk
1

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.

ยทยทยท

Begin forwarded message: