ノート:レーベンシュタイン距離

外部リンクの http://www15.big.or.jp/~t98907/ld/ にあるソフト「編集距離1.1」ですが、ここの説明と異なる結果を返します。 たとえば、kittenとsittingの編集距離は、擬似コードでは３になるが、ソフトでは５を返します。考え方が若干違うだけで本質は同じようではあるのですが、混乱を招く気がします。

--sna17

上のフリーソフトをダウンロードして生成された行列を確認してみましたが、このソフトはレーベンシュタイン距離の算出にあたって、文字列の置換コストを2と見なす計算を行っているようです。

ソフトの配布サイトから参考資料としてリンクが貼られている、グーグルブックス内のDaniel Jurafsky, James H.Martin のSpeech and Laguage Processing、Minimum Edit Distanceの節[1]に目を通して見たところ、74ページの中ほどに以下の記述がありました。

We can also assign a paticular cost or weight to each of these operations [insertion, deletion, and substitution]. The Levenshtein distance between two sequences is the simplest weighting factor in which each of the three operations has a cost of 1 (Levensterin, 1966). Thus, the Levenstein distance between intention and execution is 5. Levenshtein also proposed an altrernative version of his metric in which each insertion or deletion has a cost of 1 and substitutions are not allowed (equivalent to allowing substitution, but giving each substitution a cost of 2 since any substitution can be represented by one insertion and one deletion). Using this version, the Levenstein distance between intention and execution is 8.

私は情報理論に関してはまったくの門外漢なので、どちらのレーベンシュタイン距離が主流として用いられているのかは分かりませんが、とりあえず応急処置として、置換を禁止する（＝置換のコストを2と見なす）バージョンのレーベンシュタイン距離について本記事に加筆してみました。--Kasuga 2009年8月25日 (火) 10:50 (UTC)返信