algorithm - 仅跟踪替换和插入的编辑距离算法的变体

Question

有谁知道只计算替换和插入的编辑距离算法。所以基本上，这将是没有删除的 Levenshtein 距离算法。

Answer 1

假设您的 Levenshtein 距离算法如下：

For each i= 1...M
    For each j = 1...N
        //min(deletion, insertion, match/substitution)
        D(i,j) = min(D(i-1,j) + 1, D(i,j-1) + 1, D(i-1,j-1) + (X(i)=Y(j) : 0 ? 2))

应该删除计算删除的部分。留给您：

For each i= 1...M
    For each j = 1...N
        //min(insertion, match/substitution)
        D(i,j) = min(D(i,j-1) + 1, D(i-1,j-1) + (X(i)=Y(j) : 0 ? 2))

注意：此特定算法以 2 分代替替换，其他两个操作（删除、插入）为 1 分。有许多不同的变化。

好的 PowerPoint 资源在这里。

Answer 2

您可以使用与计算正常 Levenshtein 距离几乎相同的动态规划解决方案，但没有对应于删除的转换。