斯坦福NLP +2+1课程编辑距离算法的定义

Question

我正在通过以下幻灯片学习斯坦福大学的NLP课程：https://web.stanford.edu/class/cs124/lec/med.pdf。此幻灯片中编辑距离算法的定义如下：

初始化

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':distance。你们能解释一下这两种定义的区别吗。我是NLP的新人。谢谢!

Answer 1

在编辑一个字符串时，为了获得另一个字符串，您需要做的最小数量的更改是什么？

这是编辑距离的一般定义，而不是具体定义。要得到精确的定义，您需要定义“更改”是什么。

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

示例:要将feh转换为fah，需要进行多少更改？

• 一个改变--只需用e替换a
• 两个更改--删除e；然后将a添加到相同的位置

这两个答案都是有用的，并导致两个稍微不同的定义编辑距离。