Levenstein距離アルゴリズムの実装におけるアクションマトリックスの埋め込み

Question

現在のsetpsの値だけでなく、取られたアクション（挿入、置換、削除またはマッチ）でmartixを生成するために、既存のjavascript levenstein距離計算ソースコードを改良しようとしています。 ）

は、私が "アクション" マトリックスに間違った結果を得る：

アルゴリズムでは、我々はjsのを見ている（いない、ウィキペディアから）：

d[i, j] := minimum 
        (
         d[i-1, j] + 1, // a deletion 
         d[i, j-1] + 1, // an insertion 
         d[i-1, j-1] + 1 // a substitution 
        ) 

だから私のJSコードで、私は次のようにします。

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

// a deletion 
if(d[i][j] == d[i - 1][j] + 1) { 
    actions[i][j] = 'D'; 
} 

// a insertion 
if(d[i][j] == d[i][j - 1] + 1) { 
    actions[i][j] = 'I'; 
} 

// a substitution 
if(d[i][j] == d[i - 1][j - 1] + cost) { 
    actions[i][j] = 'R'; 
} 

d行列（2次元配列）の値のためであり、それがのは、正しい値で読み込まれます。 しかし、対応するactions行列が、論理的にどのようなアルゴリズムで表示されないのか？

「I」、「R」、「D」の割り当てに関して、私は間違って何をしていますか？それとも、それは正解で、ちょうど私には論理的ではないように思えます。なぜなら、私が前例のないシナリオで考えたので、挿入は第2ステップで行われるからです。

ところで、Levensteinアルゴリズムの場合、このような「アクション」マトリックスを生成するのは実際には賢明ですか？

Answer 1

通常、任意のLevensthein行列に対して一連の「アクション」を生成する方法はたくさんあります。あなたの例では、結果のコストマトリックスを常にminimunに戻すことができ、かなりのパスを見つけることができます。ここで

は、いくつかの例は以下のとおりです。

(0,0)(0,1)(1,2)(1,3)(2,4)(3,5) 

(0,0)(1,1)(1,2)(1,3)(2,4)(3,5) 

(0,0)(0,1)(0,2)(1,3)(2,4)(3,5) 

だから私は同じ距離行列の少なくとも三つの異なる解釈を見つけることができます。つまり、方向を優先させる方法がない限り（挿入より削除などの置換が優先されます）、マトリックスが非常にあいまいになります。

アクションマトリクスを埋めるために提案したアルゴリズムを使用してください：あなたの場合、削除と比較して置換を好む（最後にチェックされ、以前の選択を上書きするため）。それはあなたのマトリックスのRがどこから来たかです。さんがここで何が起こるか見てみましょう：

我々は置換を好む提案された解決策は、SによってAとXによってN、AによってMを置き換える何か前AとNを挿入することです。これが4のコスト（2つの挿入と2つの "実際の"置換）を持つことがわかります。これは正確に行列が決定したものです（これはトレースしたパスの最後のパスです）。

は今再びあなたの行動の行列をチェックし、我々は最終コーナーから遡るならば、私たちが見つけることは、次のとおりです。場所(3,5)、(2,4)と(1,3)でR、RとR。これは、MAX〜NASの最終的な置換に相当する。しかし、ここで欠けているものは、私が上にトレースした先導ANの挿入です。マトリックスを見ると、最初の行には数字があり、列にはアクションが含まれていないことがわかります。これらはそれぞれ削除と置換でなければなりません。その場合、をANNASに変換するために4のコストを持つ最終シーケンスSSRRRを生成することができます。

ただし、最終的なコストマトリックスですべての情報を利用できるため、実際にはマトリックスのアクションを計算する必要はないことに注意してください。最後のコーナーから最初のコストマトリックスを常にトレースバックすることができ、ある単語を別の単語に変換できるすべてのパスを再構築できます。しかし、アクションマトリックスのアクションを修正すると、すべての可能性のうち1つのパスしか残っていません。

これは、パスが非常にあいまいであるのに対し、これはコストが高く、一意的に定義されていなければなりません。ここで

EDIT

は曖昧さを含んでいるパスのフルアクション行列、次のとおりです。

* D  D  D 
I R R/D D 
I R/I R/I R 
I R/I R/I R/I 
I R/I R R/I/D 
I R/I I  R