在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