Levenshtein distanceに関する質問

Question

1）なぜこれらの行に1を追加するのですか？

d[i-1, j] + 1, // deletion 
    d[i, j-1] + 1, // insertion 

if s[i] = t[j] then cost := 0 

     else cost := 1 

は下位ワード長/削除を考慮すべきである、または私は何かが足りないのですライン？

2）コメントは、削除と挿入を示します。より低い値が削除された文字を表すため、両方の単語（削除された文字の長さを表す整数j/i）で削除された文字をチェックしていると思うのは間違いありません。

使用されるコードはここにある

は（それは擬似コードであると私は、言語固有の問題を持っていないので、このスレッドは、任意の言語のカテゴリではありません）：

http://www.iterasi.net/openviewer.aspx?sqrlitid=z0cloj7xhk-ce0f72v4cjq

Answer 1

1）これらの行は、距離を計算します挿入の場合は削除の場合、置換の場合は「コスト」を使用するもの...

削除計算と挿入は、距離計算で有効に1とカウントされます。

私たちは、新たな距離は、これらの3つの仮説の間最小距離です...両方の文字が等しい場合、文字が故に「= 0コスト」異なっている場合にのみ、置換があった

を信じることができますあなたは常に1を追加するとは限りません...

2） "FooBar"と "FoBaWhatever"の間の距離を計算すると、2番目の文字列が最初の文字列より長い場合でもいくつかの文字が削除されます...

もちろん、2番目の文字列が2番目の文字列よりも短い場合（FooBar - > F oBa）私はいくつかの削除を見つけるでしょうが、それらがどこにあるかを事前に知ることはできません...

Answer 2

あなたはhttp://www.merriampark.com/ld.htmをお読みですか？

文字列を別の文字列に変換するために必要な変換のコスト（挿入と削除の回数）を計算しています。

この "コスト"は、2つの文字列の間の距離を表します。

エクスチェンジはどうですか？これはDamerau–Levenshteinアルゴリズムで、これは異なっています。取引所を含めても物事はあまり改善されません。

本質は、2つの単語の間に行列を作成し、各単語の各文字から他の単語の各文字への「距離」を計算することです。その行列の右下隅は、すべての文字を考慮した合計距離です。

は質問1）

「上」細胞は、変更履歴を反映し、その行の文字（通常は）これとは異なるので、この細胞は、それに削除相対的です。

セル "left"は変更の履歴を反映しており、その列の文字は（通常）これとは異なります。したがって、このセルは相対的な挿入文字です。

これは通常、間違っている唯一の時間は3文字シーケンスの単語です。英語ではまれです。

行 - 列の比較は、「履歴プラス1つの変更」と変化の実際のコストの最小値が適用コストは0または1

のコストを有します。

質問2）

変数iとjは何の長さではありません。彼らは比較マトリックスの位置です。 「挿入」と「削除」は、ある単語を別の単語に変換するために必要なアクションです。挿入/削除アクションの数は、単語間の距離です。