レーベンシュタイン距離のアルゴリズムを理解する
二つの文字列の類似度を測れるので
メールアドレスの入力チェック等でも使われてるレーベンシュタイン距離。
rubyではgemもあるし、サンプルコードもweb上に色々あるけど
触る機会があったので、せっかくだしアルゴリズムを理解した上で
自分で焼き直してみた。
考え方
レーベンシュタイン距離は、
文字列の類似度を「二つの文字列が最短で何回の編集で同じになるか」
で表したもの。
編集とは[挿入、削除、(置換)]を指す。
一度の編集では1つの文字しか編集できない。
アルゴリズム
wikipediaのアルゴリズム説明にはこう書いてある。
レーベンシュタイン距離を計算するためには、
一般的に動的計画法によるアルゴリズムが用いられている。
長さ n と長さ m の文字列間の距離を求めるには
(n + 1)×(m + 1) の二次元行列が使われ、
計算時間はO(mn)と非常に効率がよい。
このアルゴリズムの要諦は、
1文字削った文字列の末尾にどのような文字を追加すれば一致するか見ることで、
1文字削った文字列との距離から1文字加えた文字列との距離を求めることができる
長さ 0 の文字列と長さ x の文字列の距離は x である
の2点から帰納的に求めることができるという点である。
動的計画法とか用語が分からないと戸惑ってしまうけど、図にしてみると割と簡単。
文字列A = abc
文字列B = ad
上記2つの文字列のレーベンシュタイン距離を求めてみる。
まず、2つの文字列を縦軸と横軸に一文字ずつ並べた表を作る。
| - a b c
-----------------
- |
a |
d |
各軸の最初のハイフンは空文字の意味。
後の説明のために、縦軸横軸それぞれに追加してある。
ここに、Bの文字列(Y軸)をAの文字列(X軸)にするための編集距離を追加する。
文字同士を比較して、編集が必要(追加/削除)な場合は1を加算、
一致している場合は加算しない。
一致している場合は右斜め下、追加が必要な場合は右、削除が必要な場合は下に、
という風に進んで行く。
| - a b c
-----------------
- | 0
a | 0 1 2
d | 3
もしくは
| - a b c
-----------------
- | 0
a | 0
d | 1 2 3
空文字、aは一致しているので0、2文字目以降は不一致なので
dを削除、bとcを追加(又は逆の順序で)しているので
それぞれ一つ前の値に1を加算して進み、
最終的に右下の位置までいくと一致することになる。
つまり、この図の右下にたどり着く為におこなった
編集の回数(斜め以外の移動回数)が編集距離(レーベンシュタイン距離)となる。
これを最も単純に求める方法は、
左上のセルから順に、全てのセルの値をインクリメントしてセットしていけばよい。
まずは左上セルは開始位置なので0をセット、
そのまま1行目の右方向セルに1ずつ加算した値をセットする。
これは、Y軸の空文字とa/ab/abcとの編集距離をそれぞれ登録しているという事になる。
上記のwikipediaのアルゴリズムの説明にあった
長さ 0 の文字列と長さ x の文字列の距離は x である
の部分になる。
| - a b c
-----------------
- | 0 1 2 3
次に、同様の考え方で1列目の2行目以降のセルに1ずつ加算した値をセットする。
これは、X軸の空文字とa/ab/abcとの編集距離をそれぞれ登録しているという事になる。
| - a b c
-----------------
- | 0 1 2 3
a | 1
d | 2
ここからは各行毎に左端から右端に向かって一つずつセルに値をセットして行く。
(1,1)のセルに設定する値を考える。
比較文字はX、Y共に[a]で一致しているので編集距離は加算されない。
つまり、左斜め上(0,0)のセル値と同じ値、0をセットすればよい。
| - a b c
-----------------
- | 0 1 2 3
a | 1 0
d | 2
次に右に一つ進んで(2,1)のセル値を設定する。
Xが[b]、Yが[a]なので編集が発生する。
この時、人間ならここまでの最短ルートを記憶しているので
左の0に加算をすると言う判断がすぐに出来るが、
プログラム的にはルートの記憶は考慮していないので一つ前の値となる
(0,1)と(1,0)の値を比較して、小さい方
(今回の場合は左隣の0)を選択して、そこに1を加算する。
| - a b c
-----------------
- | 0 1 2 3
a | 1 0 1
d | 2
このロジックで全て数値を埋めて行くと、
# 完成図
| - a b c
-----------------
- | 0 1 2 3
a | 1 0 1 2
d | 2 1 2 3
上記のマトリクスが完成し、右下の値が最短の編集距離となる。
という訳で、この考え方に基づいて書いたレーベンシュタイン距離を求める、
よくあるコードが以下のような形になる。(コードはruby)
# coding: utf-8
def levenshtein_distance(a ,b)
# 二つとも長さゼロの場合は差異無しとして扱う
return 0 if a.length == 0 && b.length == 0
# 片方が長さゼロの場合はもう一方の長さを返却
return b.length if a.length == 0
return a.length if b.length == 0
# 値をセットする為の2次元配列を生成
matrix = Array.new
0.upto(a.length){ matrix << Array.new}
0.upto(a.length){ |i| matrix[i][0] = i}
0.upto(b.length){ |j| matrix[0][j] = j}
# 各文字を比較して、編集距離を各セルに設定する
1.upto(a.length) do |i|
1.upto(b.length) do |j|
m = matrix[i-1][j] + 1
n = matrix[i][j-1] + 1
if a[i-1] == b[j-1]
l = matrix[i-1][j-1]
matrix[i][j] = l
else
matrix[i][j] = [m, n].min
end
end
end
# 右下のセルの値が最短編集距離
return matrix[a.length][b.length]
end
str1 = 'select'
str2 = 'inspect'
puts levenshtein_distance(str1, str2)
ちなみに、編集の定義に置換も考慮する場合は上記のコード中の
セルに値をセットしている処理部分を以下のようにすれば良い
# 各文字を比較して、編集距離を各セルに設定する
1.upto(a.length) do |i|
1.upto(b.length) do |j|
# 置換の加算値を1とする場合(編集の定義=追加/削除/置換)
x = (a[i-1] == b[j-1]) ? 0 : 1
m = matrix[i-1][j] + 1
n = matrix[i][j-1] + 1
l = matrix[i-1][j-1] + x
matrix[i][j] = [m, n, l].min
end
end