ruby でレーベンシュタイン距離（編集距離）の計算

なんとなく暇だったので、ruby でレーベンシュタイン距離（編集距離）を求めるコードを書いてみた。編集距離とは、文字列間の類似度を求める方法のことらしいです。詳しくは、wikipedia:レーベンシュタイン距離を見てください。コードはこんな感じ↓。

# doctest: abc and abc
# >> levenshtein_distance("abc", "abc") 
# => 0
# doctest: kitten and sitting
# >> levenshtein_distance("kitten", "sitting") 
# => 3
# doctest: aaaaa and bbbbb
# >> levenshtein_distance("aaaaa", "bbbbb") 
# => 5
def levenshtein_distance(str1, str2)
  col, row = str1.size + 1, str2.size + 1
  d = row.times.inject([]){|a, i| a << [0] * col }
  col.times {|i| d[0][i] = i }
  row.times {|i| d[i][0] = i }

  str1.size.times do |i1|
    str2.size.times do |i2|
      cost = str1[i1] == str2[i2] ? 0 : 1
      x, y = i1 + 1, i2 + 1
      d[y][x] = [d[y][x-1]+1, d[y-1][x]+1, d[y-1][x-1]+cost].min
    end
  end
  d[str2.size][str1.size]
end

で、、、この手のコードを書いたときに、ちょっとしたテストも書いときたいなあ、と思うんですよね。Python だと、doctest っていうコメントにテストを埋め込める便利なのがあるんですが、ruby にもないものかと思って探したらありました。rubydoctestってやつが。

sudo gem install rubydoctest

こんな感じ↑でインストールすると使えます。rubydoctest の書き方はここらへんにありました。実は冒頭のコードには既に rubydoctest 用のコメントを書いてあるので、test.rb って名前で保存して、こんな感じ↓でテスト。

/Users/kenkitii% rubydoctest test.rb
=== Testing 'test.rb'...
 OK  | abc and abc
 OK  | kitten and sitting
 OK  | aaaaa and bbbbb
3 comparisons, 3 doctests, 0 failures, 0 errors

便利ですね。