11

我正在玩Levenshteins Edit Distance algorithm，我想扩展它以计算换位 - 即相邻字母的交换 - 作为 1 个编辑。未修改的算法计算从另一个字符串到达​​某个字符串所需的插入、删除或替换。例如，从“KITTEN”到“SITTING”的编辑距离为 3。这是来自 Wikipedia 的解释：

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

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

  1. CHIAR → CHAR（删除“我”）
  2. CHAR → CHAIR（插入“I”）

我想把这算作“1次编辑”，因为我只交换了两个相邻的字母。我该怎么做呢？

4

3 回答 3

19

您还需要 Wikipedia 的算法中的一个案例：

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
             )
于 2010-10-29T20:10:42.917 回答
1

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

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

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

让单词是 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))
                )

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

于 2010-10-29T20:39:34.787 回答
1

其他答案是实现最佳字符串对齐算法，而不是我认为您所描述的Damerau Levenshtein 。

我有一个 OSA 的 java 实现，这里有一些优化： https ://gist.github.com/steveash/5426191

于 2013-04-20T14:50:08.947 回答