LZ78方式符号化をRubyで実装、を改良

Trieちゃんと使ったので、それなりの速度になりました。100MBくらいのテキストが40MBくらいまで縮んだかと思えば、2.8MBのテキストが2.6MBにしかならなかったりと圧縮したいテキストの性質によって圧縮率が全然違う感じでした。WEB+DB PRESS Vol.54によると、LZ78方式符号化はXMLのような文章では強いらしい。

#!/opt/local/bin/ruby1.9
# -*- coding: utf-8 -*-
require 'pp'

module Trie
  class Node
    attr_accessor :sym, :code
    def initialize(code)
      @code = code # 番号
      @sym = Hash.new
    end
    def insert_child(sym, code)
      @sym[sym] = Trie::Node.new(code)
    end
    def search_child(sym)
      return @sym[sym]
    end
  end
end

def encode_lz78(str)
  result = []
  root = Trie::Node.new(0)
  n = 0
  p = root # 今見ているノード

  str.each_char{|c|
    q = p.search_child(c)
    if !q.nil? # 子が見つからない => 次を辿る
      p = q
    else # 末端まで行ったけど、見つからない => 登録しつつ符号化
      result.push [p.code, c]
      n = n + 1
      # puts "insert n:#{n} into #{p.code}"
      p.insert_child(c, n)
      # puts "Before: #{p.code}"
      p = root
    end
  }

  puts "After: #{p.code}"
  if p.code # 子をたどって、leafまで行かなかったとき
    result.push [p.code, '']
  end
  return result
end

def decode_lz78(array)
  result = ""
  n = 0
  d = ['']
  array.each{|item|
    d.push d[item[0]] + item[1]
    n = n + 1
    result += d[n]
  }
  return result
end