LZ78方式符号化をRubyで実装

してみたはいいけど、激しく遅い。なんでかなーと思って調べているとWEB+DB PRESS Vol.54にid:naoyaさんのPerlでの実装が載ってた。位置どこどこに何があったかを記録しておくような辞書を容易しておくようだ。そりゃ遅くなるな。。。なお、辞書はTrieでやるとよいようだ。

超が付くほど遅いけど、とりあえずのっけておく。

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

def coding_word(array, i) # 後ろから見てi番目の符号語を返すメソッド
  result = ""
  while(true)
    item = array.reverse[i]
    b = item[0]; x = item[1]
    result = x + result
    return result if b == 0
    i = i + b
  end
end

def encode(target_string)
  result = []
  tmp = [] # ブロックにまだ入っていない記号

  prev_index = 0 # いくつ戻ったらあったか
  target_string.each_char{|c|
    if result.length == 0
      result.push [0, c]
      next
    end

    tmp.push c
    flag = true # 初出現かどうかのフラグ
    i = 0

    while(i < result.length)
      word = coding_word(result, i)
      i = i + 1
      prev_index = 0 if !flag
      if tmp.join("") == word
        flag = false
        prev_index = i
        break
      end
    end

    if flag # ブロック全部なめたけど、なかった
      result.push [prev_index, c]
      tmp.clear
    end
  }
  if !tmp.empty?
    result.push [prev_index, tmp[-1]]
  end
  return result
end

def decode(array)
  result = ""
  (0...array.length).each{|i|
    result += coding_word(array, array.length - 1 - i)
  }
  return result
end

puts "Encode..."
target_string = "ABC"
pp encode(target_string)

target_string = "ABCBE"
pp encode(target_string)

target_string = "ABCBC"
pp encode(target_string)

target_string = "ABCBCBCDBCDE"
pp encode(target_string)

puts "=" * 50

puts "Decode..."
aaa = [[0, "A"],
       [0, "B"],
       [0, "C"],
       [2, "C"],
       [1, "D"],
       [1, "E"]]

puts decode(aaa)

target_string = "ABCBCBCDBCDE" * 3000

file = File.open("hoge_without_lz.bin", "w")
file.write Marshal.dump(target_string)
file.close

puts "finished dumping witout lz..."

file = File.open("hoge_with_lz.bin", "w")
file.write Marshal.dump(encode(target_string))
file.close