如何修改 Levenshteins 编辑距离以计算“相邻字母交换”作为 1 编辑

Question

我正在使用 Levenshteins 编辑距离算法，我想扩展它来计算换位 - 即交换相邻字母的数量——作为 1 次编辑。未修改的算法计算从另一个字符串到达​​某个字符串所需的插入、删除或替换次数。例如，从“KITTEN”到“SITTING”的编辑距离是3。维基百科的解释如下：

1. kitten→sitten（将'k'替换为's'）
2. sitten→sittin（将'e'替换为'i'） )
3. 坐 → 坐（在末尾插入“g”）。

按照相同的方法，从“CHIAR”到“CHAIR”的编辑距离为2：

1. CHIAR → CHAR (delete 'I')
2. CHAR → CHAIR (insert 'I')

我想将其计为“1次编辑”，因为我只交换两个相邻的字母。我该怎么做呢？

Answer 1

您还需要维基百科的算法中的另一种情况：

if s[i] = t[j] then 
  d[i, j] := d[i-1, j-1]
else if i > 0 and j > 0 and s[i] = t[j - 1] and s[i - 1] = t[j] then
  d[i, j] := minimum
             (
               d[i-2, j-2] + 1 // transpose
               d[i-1, j] + 1,  // deletion
               d[i, j-1] + 1,  // insertion
               d[i-1, j-1] + 1 // substitution
             )
else
  d[i, j] := minimum
             (
               d[i-1, j] + 1,  // deletion
               d[i, j-1] + 1,  // insertion
               d[i-1, j-1] + 1 // substitution
             )

Answer 2

您必须修改更新动态规划表的方式。在原始算法中，我们考虑长度最多相差一的两个单词的尾部（或头部）。更新是所有此类可能性中的最低限度。

如果您想修改算法，使两个相邻位置的变化计为 1，则必须根据最多相差 2 的尾部（或头部）计算上述最小值。您可以将其扩展到更大的社区，但复杂性将随着该社区的大小呈指数级增加。

您可以进一步概括并分配取决于删除、插入或替换的字符的成本，但您必须确保分配给配对编辑的成本低于两次单独编辑，否则两次单独编辑将总是赢。

令单词为 w1 和 w2

dist(i,j) = min(
                dist(i-2,j-2) && w1(i-1,i) == w2(j-1,j) else
                dist(i-1,j-1) && w1(i) == w2(j) else
                dist(i,j-1)   + cost(w2(j)),
                dist(i-1,j)   + cost(w1(i)),
                dist(i-1,j-1) + cost(w1(i), w2(j)),
                dist(i, j-2)  + cost(w2(j-1,j)),
                dist(i-2, j)  + cost(w1(i-1,i)),
                dist(i-2,j-2) + cost(w1(i-1,i), w2(j-1,j))
                ) 

我所说的 && 的意思是，只有满足条件时才应考虑这些行。

Answer 3

其他答案是实现最佳字符串对齐算法，而不是 Damerau Levenshtein我想这就是你所描述的。

我有一个 OSA 的 Java 实现，并进行了一些优化：
https://gist.github.com/steveash/5426191