algorithm - 为什么斯坦福NLP类(class)中edit Distance算法的定义加2而不是1

Question

我正在通过以下幻灯片学习斯坦福 NLP 类(class):https://web.stanford.edu/class/cs124/lec/med.pdf .本幻灯片中edit Distance算法的定义如下:

初始化

D(i,0) = i
D(0,j) = j

递归关系:

 For each  i = 1…M
    For each  j = 1…N


       D(i,j)= min  {D(i-1,j) + 1, D(i,j-1) + 1, 
                     D(i-1,j-1) +   2(if X(i) ≠ Y(j) )  
                                    0(if X(i) = Y(j))}

如果 X(i) ≠ Y(j)，为什么 D(i-1,j-1) + 2 不是 (+1)。我发现维基百科中编辑距离算法的定义是“+1”:https://en.wikipedia.org/wiki/Levenshtein_distance .请你们解释一下这两个定义的区别。我是 NLP 的新手。谢谢!

Answer 1

When editing one string, what is the minimal number of changes you need to do in order to get another string?

这是对编辑距离的一般而非具体定义。要获得准确的定义，您需要定义“变化”是什么。

• 如果“更改”包括“用另一个字母替换一个字母”，则您的定义中有 +1
• 如果“更改”不包括“用另一个字母替换一个字母”，则您的定义中有 +2

示例:将 feh 变成 fah 需要多少改动？

• 一个变化 - 只需将 e 替换为 a
• 两项更改 - 删除 e；然后在同一个地方添加a

这两个答案都很有用，并导致对编辑距离的两个略有不同的定义。