博客

最近由于工作需要，接触了

编辑距离（Levenshtein Distance）算法。

赶脚很有意思。最初百度了一些文章，但讲的都不是很好，读起来感觉似懂非懂。最后还是用google找到了一些资料才慢慢理解。当我完全理解的时就想把自己探索时遇到的“坑”总结起来，为后人“乘凉”。于是就有了这篇博文。

下面先来看一下他的定义：


编辑距离

就是用来计算从原串（s）转换到目标串(t)所需要的最少的插入、删除和替换

的数目，在NLP中应用比较广泛，如一些评测方法中就用到了（wer,mWer等），同时也常用来计算你对原文本所作的改动数。编辑距离的算法是首先由俄国科学家Levenshtein提出的，故又叫Levenshtein Distance。

Levenshtein Distance算法可以看作动态规划。它的思路就是从两个字符串的左边开始比较,记录已经比较过的子串相似度(实际上叫做距离),然后进一步得到下一个 字符位置时的相似度。比如：字符串intention变成execution需要进行下面的操作

如上图所示，d（deletion）代表删除操作，s（substitution）代表替换操作，i（insertion）代表插入操作。这里每种操作的cost为1，那么它的ED（Edit Distance）=5。

代码实现：

挖坑&填坑：

1、为什么要初始化第一行和第一列的值？

答：上面代码初始化后矩阵的结构如下：

		i	n	t	e	n	t	i	o	n
	0	1	2	3	4	5	6	7	8	9
e	1
x	2
e	3
c	4
u	5
t	6
i	7
o	8
n	9

从上面可以看出，第一行的值表示s2的距离，第一列的值表示s1的距离

2、matrix[i – 1, j] 、matrix[i, j – 1]、matrix[i – 1, j – 1] 分别表示啥？它们为啥都加1，而这个1又表示啥？

答：

根据编辑距离的概念可知，所需要最少的的插入、删除和替换的数目就是编辑距离。我们要找出每个字符中最小的操作，那么怎么找出“最小的操作”呢？只能挨个试了，所以出现了对每个字符进行删除、插入和替换的操作，然后进行对比从而找出最小的编辑距离

matrix[i – 1, j] 表示删除操作

matrix[i, j – 1]表示插入操作

matrix[i – 1, j – 1]表示替换操作

“1”表示距离值，因为ED算法是动态规划问题，后面的值由前面的结果得出，所以加1

3、为什么 matrix[i – 1, j]就表示删除操作，matrix[i, j – 1]就表示插入操作，matrix[i – 1, j – 1]就表示替换操作呢？

答：

举个例子：

matrix[3,3]位置，现在i=3，对应的字符串为exe；j=3，对应的字符串为int

matrix[i-1,j]=matrix[2,3]，2对应的比较字符为ex，请注意关键点来了，i 和 i-1对比，也就是exe 和 ex 对比，是不是少了一个字符？那么我们就可以认为对字符exe进行了删除的操作得到ex。讲到这是不是有些感觉呢？ok，我们接着进行。

matrix[i,j-1]=matrix[3,2],2对应的比较字符in。同样我们用in和int相比，in少一个字符，那么我们可以认为in需要进行插入操作从而得到int。

matrix[i-1.j-1]=matrix[2,2]，它表示替换操作，因为替换=删除+插入。看到这里你一定会恍然大悟原来是这样。这次比较的字符是ex和in，相当于我们对exe进行了删除操作得到ex，对in进行插入操作的到int

最后输出结果：

		i	n	t	e	n	t	i	o	n
	0	1	2	3	4	5	6	7	8	9
e	1	1	2	3	3	4	5	6	7	8
x	2	2	2	3	4	4	5	6	7	8
e	3	3	3	3	3	4	5	6	7	8
c	4	4	4	4	4	4	5	6	7	8
u	5	5	5	5	5	5	5	6	7	8
t	6	6	6	5	6	6	5	6	7	8
i	7	6	7	6	6	7	6	5	6	7
o	8	7	7	7	7	7	7	6	5	6
n	9	8	7	8	8	7	8	7	6	5

结束

以上是我个人的理解，如果有什么不对的地方还请大家指出