从Damerau-Levenshtein提取操作

Question

Damerau-Levenshtein距离告诉您两个单词之间添加、删除、替换和转换的数量(后者是DL与Levenshtein距离的区别)。

algo是维基百科，相对简单。然而，我想要的不仅仅是距离，我想要的是实际操作。

例如，采用AABBCC的函数，将其与ABZ进行比较，并返回：

• 在索引0 -> ABBCC处删除A
• 删除索引2 -> ABCC处的B
• 删除索引4 -> ABC处的C
• 将索引5处的C替换Z -> ABZ

(暂时忽略指数如何受到清除的影响)

似乎你可以用DL计算产生的矩阵做些什么。本站产生上面的输出。下面的文本说，您应该从矩阵的右下角走，遵循每个单元格中的每个最低成本操作(跟随粗体单元格)：

• 如果删除的成本最低，请增加一个单元格。
• 插入，左转一个单元格
• 否则，替换，转置或平等上升和左

​

​

如果有平分的话，它似乎优先考虑平等或替换，所以在我提供的示例中，当右下角单元格为4时，它会选择替换。

但是，一旦到达左上角单元格，等式是得分最低的操作，为0。但它选择了删除，得分为2。

这似乎是正确的答案，因为如果你严格地选择最低的分数，你会在字符串开始时得到太多的分数。

但是，选择手术的真正步骤是什么，如果不是最低分的话？是否有其他方法从DL矩阵中选择操作，如果有，您有引用吗？

Answer 1

我错过了模糊字符串关于如何重建操作的解释的一个重要部分：

但是，当你想要看到最简单的路径时，它是由从右下角向左上角倒转确定的，它遵循每个单元格中最小变化的方向。(如果在左上角单元格之前到达顶部或左侧边缘，则将覆盖其余单元格中的更改类型，分别使用插入或删除.)

...which解释了为什么忽略单元格1,1中的相等操作，而使用删除！