レーベンシュタイン距離で文字列の類似度を測る
2011 年 11 月 18 日 by 山平過去にネットで見かけてその存在だけは知っていたレーベンシュタイン距離について追ってみます。
編集距離 (Levenshtein Distance) – naoyaのはてなダイアリー
すでにrubyで実装されている方がいらっしゃったので、それを使うことにします。
ruby でレーベンシュタイン距離（編集距離）の計算 – Moderation is a fatal thing. Nothing succeeds like excess.
（私的な）使い勝手向上のために以下2点の修正を加えています。
- Stringクラスを再オープンしてメソッドを定義
- メソッド名をldに変更
では早速動作をチェックしてみます。
“氷山の一角”.ld “天山の一撃”
=> 6
“ヘリコプター”.ld “ヘコリプター”
=> 4
“じゃがいも”.ld “がじゃいも”
=> 5
良さそうな気もしますが、3つとも2文字違いの割に結果（の距離）が長い気がします。
と思ったら、これは恐らくRuby1.9向けの実装ですね。
Ruby 1.8.7 リファレンスマニュアル > ライブラリ一覧 > 組み込みライブラリ > Stringクラス > []
nth 番目のバイトを整数 (文字コード) で返します。
nth が負の場合は文字列の末尾から数えます。
つまり、 self.size + nth 番目のバイトを返します。
Ruby 1.9.2 リファレンスマニュアル > ライブラリ一覧 > 組み込みライブラリ > Stringクラス > []
nth 番目の文字を返します。
nth が負の場合は文字列の末尾から数えます。
つまり、 self.size + nth 番目の文字を返します。
1.8系の文字列は内部的にはただのバイト列、1.9系からは内部的にも文字の列なので、私の環境（1.8.7）では全角文字のバイト数ぶんカウントされているものと思われます。
なので、文字列ではなく正規表現で分割して文字配列で処理させるように変更します。
※uオプションを利用していますので、UTF-8以外は正しく処理しません！
Ruby 1.9.1 リファレンスマニュアル > spec/literal # 正規表現リテラル
では、改めて動作をチェックします。
“氷山の一角”.ld “天山の一撃”
=> 2
“ヘリコプター”.ld “ヘコリプター”
=> 2
“じゃがいも”.ld “がじゃいも”
=> 2
これで予想通りの結果になりました。
以下が今回手を入れたソースです。
class String
def ld(comp)
str1, str2 = self.split(//u), comp.split(//u) # 1.8系対応(*UTF8!)
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
end
当たり前ですが、このアルゴリズムは単語同士の比較には有用でも、単語と文章の比較には使えません。
“七転八倒”.ld “七転び八起き”
=> 3
“七転八倒”.ld “人生は七転び八起きの精神だ”
=> 10
似ているかもしれない2つの単語を抽出するところまでをどうすればよいのか、課題は尽きません。
以上です。
タグ: Ruby
