編集距離

Ruby Study

編集距離、一般には「Levenstein Distance」と言うらしいです。二つの文字列について、片方を「削除、挿入」をそれぞれ何回することによってもう片方と同じものにできるか、という数字です。よく、二つの文字列の類似度を測る基準として用いられます。

この編集距離を求める方法には、ベタな方法、O(ND)法、O(NP)法というものが代表的なアルゴリズムらしいです。ベタな方法はそのまま。O(ND)法は「n回の編集で一致できるか？」という観点で無駄を省いたもの。O(NP)法は「p回損をすると一致できるか」という観点でO(ND)法を改良したもの。ということらしい。

参考


そこで、dtl開発者の方のソースを参考に、Rubyに落とし込んでみた。Moduleにしているので、Requireして「EditDistance.onp(arg1,arg2)」で編集距離が帰ってきます。arg1,arg2はArrayを渡します。またその要素は「==」演算子が使え無ければなりません。なお往々にして「複数の文の中から最小の編集距離を求めたい」ということがあるので、枝刈りできるように制限引数limitをつけています。これを指定した場合、編集距離がその数以上になった場合、計算を打ち切ります。

module EditDistance

  @@N = 0
  @@M = 0
  @@ary1 = nil
  @@ary2 = nil

  def onp(ary1, ary2, limit = nil)
    if ary1.size > ary2.size then 
      @@ary1, @@ary2 = ary2, ary1 
    else
      @@ary1, @@ary2 = ary1, ary2
    end

    @@M = @@ary1.size
    @@N = @@ary2.size
    offset = @@M + 1
    delta  = @@N - @@M
    size   = @@M + @@N + 3

    limit = @@M*2 + delta if limit == nil

    fp = Array.new(size)
    fp.fill(-1)

    p = -1
    k = 0

    until fp[delta + offset] >= @@N do
      p += 1
      return limit if 2*p+delta >= limit #limit以上で打ち切り

      k = -p
      while k < delta do
        fp[k + offset] = fp[k - 1 + offset] + 1 > fp[k + 1 + offset] ? 
        snake(k, fp[k - 1 + offset] + 1) : 
        snake(k, fp[k + 1 + offset])

        k += 1
      end
      
      k = delta + p
      while k > delta do
        fp[k + offset] = fp[k - 1 + offset] + 1 > fp[k + 1 + offset] ? 
        snake(k, fp[k - 1 + offset] + 1) : 
        snake(k, fp[k + 1 + offset])

        k -= 1
      end
      
      fp[delta + offset] = fp[delta - 1 + offset] + 1 > fp[delta + 1 + offset] ? 
      snake(delta, fp[delta - 1 + offset] + 1) : 
      snake(delta, fp[delta + 1 + offset])
    end
        
    return delta + 2 * p
  end
  module_function :onp

  def snake (k, y)
    x = y - k
    while x < @@M && y < @@N && @@ary1[x] == @@ary2[y] do
      x += 1
      y += 1
    end

    return y
  end
  module_function :snake

end


上記を「edit_distance.rb」として保存し、メインスクリプトがあるファイルのあるフォルダに置いた場合、サンプルはこんな感じになります。

require "edit_distance.rb"
str1 = "abc"
str2 = "ac"

p EditDistance.onp(str1.unpack("C*"), str2.unpack("C*"))
#===> 2