algorithm - レーベンシュタインの質問

Question

レーベンシュタイン距離アルゴリズムでは、この行は何をしますか?:

    d[i][j] = Minimum (d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + cost);

これらすべての値の最小値を取得しますが、なぜコストが最後に追加され、各配列インデクサー (最初の 2 つのパラメーター) の最後に + 1 があるのはなぜですか?

Answer 1

式は次のとおりです。

m(a,b) = if a==b then 0 else 1

「min」のある行は再帰式そのもので、それ以外は再帰が導く非再帰的なケースです。

あなたの行は結果を配列に「キャッシュ」しています。次のように見てみてください。

 d(i, j) = Minimum (d(i-1, j)+1, d(i, j-1)+1, d(i-1, j-1) + cost);

costでありm(a,b)、場合はゼロa==b、それ以外の場合は 1

Answer 2

記事から：

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

アルゴリズムの目的は、1 つの文字列 (またはリスト) を別の文字列に変換するための最も安価なパスを見つけることです。特定の操作の「コスト」は、参照した行で考慮されます。あなたの場合、「削除」は1のコスト、「挿入」も1、可変コストでの「置換」と見なされます。

Answer 3

さらに読むと、次のことがわかります。挿入、削除、および置換に異なるペナルティ コストを与えることができます。また、どの文字が挿入、削除、または置換されたかに応じて、ペナルティ コストを与えることもできます。

文字の削除が文字の置換よりも大きな違いを生むと仮定する場合、式の削除部分に 0 より大きいコスト値を含めます。