Levenshtein|Levenshtein distance（编辑距离） Levenshteindistance（编辑距离）

基本介绍 Levenshtein distance是一种度量两个序列(字符串)差异大小的方法。
该方法定义如下：
两个序列(以单词为例，这里序列也可以表示一个句子)的Levenshtein distance是在使用一个单词修改为另一个单词时，通过编辑单个字符(如插入，删除，修改)所需要的最小次数。
这个概念由俄罗斯数学家Vladimir Levenshtein于1965年提出。目前这个距离常用来评价字符识别任务的好坏。
举个例子将单词“kitten”修改为“sitting”最少需要3次单字符的操作：

kitten -> sitten(将“k”改为“s”)
sitten -> sittin(将“e”改为“i”)
sittin -> sitting(将“g”删除)

原理假设现在两个字符串A和B，其中A的长度为a，B的长度为b，现要计算A与B之间的Levenshtein distance
【Levenshtein|Levenshtein distance（编辑距离）】我们可以考虑使用动态规划的思想解决这个问题
假设和分别为字符串A、B的前个字符组成的子串，现在我们来看看将

修改为

需要的最少编辑次数，即两个子串的Levenshtein distance，下面我们来分别讨论三种操作的操作次数：

插入操作

假设将修改为需要操作数为，那么在后插入一个字符，这样就可以将修改为，这时所需要的操作数为
2.删除操作
假设将修改为需要操作数为，那么删除就可以将修改为，这时所需要的操作数为
3.修改操作
假设将修改为需要操作数为，这时要将修改为分两种情况：
a. ，则将替换成即可完成修改，这时操作数为
b. ，则将不需要进行修改操作，操作数仍为
?
最后可以得到状态转移方程如下
$Levenshtein|Levenshtein distance（编辑距离）$
文章图片

上式中表示表达式取0，否则取1
Python代码如下得到上述转移方程后我们就很容易写出下面程序了
1.按照上述公式编写，没做优化的情况

import numpy as npdef Lev_distance(): A = "fafasa" B = "faftreassa"dp = np.zeros((len(A) + 1, len(B) + 1))for i in xrange(len(A) + 1): dp[i][0] = i for j in xrange(len(B) + 1): dp[0][j] = jfor i in xrange(1, len(A) + 1): for j in xrange(1, len(B) + 1): if A[i - 1] == B[j - 1]: dp[i][j] = dp[i - 1][j - 1] else: dp[i][j] = min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j])) + 1print("Levenshtein distance: {}".format(dp[len(A)][len(B)]))if __name__=="__main__": Lev_distance()

2.使用滚动数组优化上述代码

import numpy as npdef Lev_distance(): A = "fafasa" B = "faftreassa"dp = np.array(np.arange(len(B)+1))for i in xrange(1, len(A)+1): temp1 = dp[0] dp[0] += 1 for j in xrange(1, len(B)+1): temp2 = dp[j] if A[i-1] == B[j-1]: dp[j] = temp1 else: dp[j] = min(temp1, min(dp[j-1], dp[j]))+1 temp1 = temp2print("Levenshtein distance: {}".format(dp[len(B)]))if __name__=="__main__": Lev_distance()

参考 [1] https://en.wikipedia.org/wiki/Levenshtein_distance
[2] http://www.cnblogs.com/BlackStorm/p/5400809.html
欢迎加入OCR交流群：785515057(此群已满)
欢迎加入OCR交流群2：826714963