ハフマン圧縮してみる

みんなが大好きであろう「ハフマン圧縮」をRubyでそれっぽく書いてみる。
 
ハフマン圧縮についてはこちら
画像圧縮アルゴリズム
 
Rubyで書くとこんな感じか

class Huffman
  def initialize(str)
    @targetWord = str
  end

  def encode
    @encode_table = get_encode_table(@targetWord)
    @targetWord.scan(/./).inject(""){|res, i| res+=@encode_table[i]}
  end

  def get_encode_table(target)
    #文字列を出現数順に並び替え
    @uniq_asce_ary = target.scan(/./).inject(Hash.new(0)){|res, h| res[h] += 1; res}.to_a.sort{|h, s|s[1]<=>h[1]}.inject([]){|res, a| res<<a[0]}
    make_tree(@uniq_asce_ary, tree=[], tree_table={})
    tree_table
  end

  def make_tree(data_ary, tree, table, index=0, nest="")
    return tree if data_ary.length <= index
    if data_ary.length-1 == index
      table[data_ary[index]] = nest+"1"
      return tree[1]=data_ary[index]
    end
    unless tree[0]
      table[data_ary[index]] = nest+"0"
      tree[0] = data_ary[index]
      return make_tree(data_ary, tree, table, index+1, nest)
    else
      table[data_ary[index]] = (nest+="1")+"0"
      tree[1] = [data_ary[index]]
      return make_tree(data_ary, tree[1], table, index+1, nest)
    end
  end
end

huffman = Huffman.new(ARGV[0])
puts "圧縮文字列 : #{ARGV[0]}"
puts "byte : #{ARGV[0].unpack('B*')[0].scan(/.{8}?/).length}"
puts "byte : #{ARGV[0].unpack('B*')[0].scan(/.{8}?/).join(' ')}"
puts "after byte : #{huffman.encode.scan(/.{8}?/).length}"
puts "after byte : #{huffman.encode.scan(/.{8}?/).join(' ')}"

 
動かすとこんな感じか
 

ruby huffman.rb hoooooogeeeee
圧縮文字列 : hoooooogeeeee
byte : 13
byte : 01101000 01101111 01101111 01101111 01101111 01101111 01101111 01100111 01100101 01100101 01100101 01100101 01100101
after byte : 2
after byte : 11100000 01101010

 
さすがハフマン。。。といいたいところだけど。
このプログラムでは実際3バイトにしなくちゃいけないんだけども、そこは面倒だしいいや。