解決済みの質問

レーベンシュタイン距離の求め方について教えてください。

レーベンシュタイン距離を求める過程で、「文字の挿入」「文字の削除」「文字の置換」のコストを計算して、いちばん小さい値を採用する手順があります。
それぞれのコストについて、比較する2つの文字数からなるマトリックスを使って求めるのですが、なぜこの方法でそれが求まるのかさっぱりわかりません。。
これが気になって、その先に進めないのです。
初歩的な質問で申し訳ありません。
よろしくお願いします。

違反報告

質問日時：

2008/3/6 21:58:06
解決日時：

2008/3/12 16:31:35
回答数：

1
お礼：

知恵コイン

250枚
閲覧数：

3,523
ソーシャルブックマークへ投稿：

Yahoo!ブックマークへ投稿

はてなブックマークへ投稿

（ソーシャルブックマークとは）

ベストアンサーに選ばれた回答

kts2371148さん

私はこの質問を見るまでレーベンシュタイン距離について知りませんでしたが、
http://ja.wikipedia.org/wiki/%E3%83%AC%E3%83%BC%E3%83%99%E3%83%B3%E...
を参考にしながらやってみます。

apple と play のレーベンシュタイン距離を求めてみます。
このときに、以下のような表を作成します。

............................. "" ........................ "p" ........................... "pl" ............................ "pla" ............................. "play"
"" .................. LD["",""] ............ LD["","p"] .............. LD["","pl"] .............. LD["","pla"] ........... LD["","play"]
"a" ................ LD["a",""] .......... LD["a","p"] ........... LD["a","pl"] ............ LD["a","pla"] ......... LD["a","play"]
"ap" .............. LD["ap",""] ........ LD["ap","p"] ......... LD["ap","pl"] ......... LD["ap","pla"] ........ LD["ap","play"]
"app" .......... LD["app",""] ....... LD["app","p"] ....... LD["app","pl"] ........ LD["app","pla"] ...... LD["app","play"]
"appl" ......... LD["appl",""] ...... LD["appl","p"] ...... LD["appl","pl"] ....... LD["appl","pla"] ..... LD["appl","play"]
"apple" ...... LD["apple",""] .... LD["apple","p"] .... LD["apple","pl"] .... LD["apple","pla"] .... LD["apple","play"]

なお、LD[s1,s2] は、文字列 s1 と s2 のレーベンシュタイン距離です。

まず、"" と長さ n の文字列の間のレーベンシュタイン距離は n です。
これを当てはめると、

....................... "" .................. "p" ...................... "pl" ....................... "pla" .......................... "play"
"" .............. 0 ...................... 1 ............................. 2 ................................. 3 ................................. 4
"a" ............. 1 .......... LD["a","p"] ........... LD["a","pl"] ............ LD["a","pla"] ......... LD["a","play"]
"ap" ........... 2 ........ LD["ap","p"] ......... LD["ap","pl"] ......... LD["ap","pla"] ........ LD["ap","play"]
"app" ......... 3 ....... LD["app","p"] ....... LD["app","pl"] ........ LD["app","pla"] ...... LD["app","play"]
"appl" ....... 4 ...... LD["appl","p"] ...... LD["appl","pl"] ....... LD["appl","pla"] ..... LD["appl","play"]
"apple" ..... 5 .... LD["apple","p"] .... LD["apple","pl"] .... LD["apple","pla"] .... LD["apple","play"]

となります。

ここから、一気に飛んで、LD["apple","play"] 以外の値がすべて求められたとします。
このとき、LD["apple","play"] の値はどうやって求めればいいでしょうか？
次の３通りが考えられます。
.......... "apple" → "e" を削除 → LD["appl","play"] （ "apple" → "appl" → "play" ）
.................... LD["apple","play"] = LD["appl","play"] + 1
.......... "apple" → LD["apple","pla"] → "y" を追加（ "apple" → "play" → "play" ）
.................... LD["apple","play"] = LD["apple","pla"] + 1
.......... LD["appl","pla"] の値を利用し、"apple" の "e" を "play" の "y" に置換する
.................... LD["apple","play"] = LD["appl","pla"] + 1
このうち小さいものを選べばいいわけです。

ただし、３通りのうち最後は、こうならない場合があります。
例えば、LD["apple","plane"] だとすれば、
.......... LD["appl","plan"] の値を利用し、"apple" の "e" を "plane" の "e" に置換する … 置換する必要がない
.................... LD["apple","plane"] = LD["appl","plan"] + 0
となります。

これは、表でいえば、
.......... 上 + 1
.......... 左 + 1
.......... 左上 + 1 （ただし、最後が同じ文字なら左上 + 0 ）
のうちの最小値を選ぶことになります。

あとは、これを左上から順にやれば、求められます。

説明してはみたものの、わかりにくいかもしれません。
参考になれば幸いです。