編集距離

今月号のWeb+DB Pressを読んでいたら文字列間の差異の程度を表す編集距離の求め方が載っていた。

ちょっと面白かったので再帰呼び出しでもっと綺麗に書いてみようかなと思ったら、ごちゃごちゃしそうだったので挫折。単なる Perl -> Ruby の移植になってしまった。

module LDist
  def get_ld another
    splitter = respond_to?(:split) ?  lambda {|e| e.split(//)} : lambda {|e| e}
    a1, a2 = [self, another].map {|elms| splitter.call(elms)}

    matrix = Array.new(a1.size + 1) {|i| Array.new(a2.size + 1)}
    0.upto(a1.size) {|i| matrix[i][0] = i}
    0.upto(a2.size) {|i| matrix[0][i] = i}

    1.upto(a1.size) do |i1|
      1.upto(a2.size) do |i2|
        diff = (a1[i1 - 1] == a2[i2 - 1] ? 0 : 1)
        matrix[i1][i2] = [
          matrix[i1 - 1][i2] + 1,
          matrix[i1][i2 - 1] + 1,
          matrix[i1 - 1][i2 - 1] + diff
        ].min
      end
    end
    matrix[a1.size][a2.size]
  end
end

str = "abcd"
str.extend LDist
puts str.get_ld "abdc"
puts str.get_ld "ab"
puts str.get_ld "abcc"
puts '----------------------'

arr = [1, 3, 5, 7]
arr.extend LDist
puts arr.get_ld [2, 3, 5, 7]
puts arr.get_ld [7, 5, 3, 1]
puts '----------------------'

$KCODE = 'u'
mstr = "あいうえお"
mstr.extend LDist
puts mstr.get_ld "あいうえ"
puts mstr.get_ld "かきうえこ"
puts mstr.get_ld "さしすせそ"
puts mstr.get_ld "あえいうえおあお"

一応、配列にも対応。

komamitsu@potato:~/lab/ruby$ ruby ldist.rb 
2
2
1
----------------------
1
4
----------------------
1
3
5
3