在Levenstein距離算法實現中填充動作矩陣

Question

我正在嘗試改進現有的javascript levenstein距離計算源代碼，以便不僅使用當前setps的值生成martix，而且還使用所採取的操作（插入，替換，刪除或匹配）

我得到錯誤的結果在 「動作」 矩陣：

在算法中我們看到，（不是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矩陣（二維數組）是價值觀，它得到的填充用正確的值。 但爲什麼相應的actions矩陣顯示不是邏輯算法會做什麼？

我在分配'I'，'R'，'D'方面做錯了什麼？或者它是正確的，對我來說似乎並不合邏輯，因爲我在前面的情景中認爲插入會在第二步中發生。

順便說一句，在Levenstein算法的情況下生成這樣的「動作」矩陣實際上是否合理？

Answer 1

通常有很多方法可以爲任何給定的Levensthein矩陣生成一組「行爲」。在你的例子中，你可以追溯到最低限度的結果成本矩陣，你會發現不少路徑。

下面是一些例子：

(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都來自哪裏。讓我們來看看這裏發生了什麼：

當我們喜歡換人提出的解決方法是插入A和N任何事情之前然後通過N，A通過S取代M通過A和X。如果你檢查你可以看到這將有四個成本（兩個插入和兩個「真實」替換），這正是矩陣確定的（這是我追蹤的路徑中的最後一條路徑）。

現在再次檢查你的行動矩陣，我們發現，如果我們從最後一個彎道追溯：在地方(3,5)，(2,4)和(1,3)R，R和R。這對應於MAX到NAS的最終替代。然而，這裏缺少的是插入前面描述的前導AN。看矩陣，可以看到第一行和第一列有數字，而不是行爲。但是，這些分別應該是刪除和替換，在這種情況下，您可以生成最終序列SSRRR，將MAX轉換爲ANNAS的成本爲4。

但是，您應該意識到，並非真的有必要像您一樣計算矩陣中的操作，因爲所有信息都將在最終成本矩陣中可用。您始終可以追溯從最後一個角落到最後一個角落的最終成本矩陣，並且您將能夠重建可以將一個單詞轉換爲另一個單詞的所有路徑。但是，一旦你已經在行動矩陣中修正了行動，那麼在所有可能性中只剩下一條路徑。

這必須做很多與成本良好和唯一定義，而路徑可能高度模糊。

編輯

這裏是該路徑的全面行動矩陣，其中包括歧義：

* 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