编辑距离算法

即MED(Minimum Edit Distance)算法，由俄罗斯的 Vladimir Levenshtein 在1965年提出，故又称Levenshtein距离。

所谓编辑距离，指的是从一个单词转换为另一个单词所需要编辑的次数，而单次编辑只有三种操作：

插入删除替换

递归实现

现有两个字符串 a 1 a 2 a 3 a 4 a_1a_2a_3a_4 a1​a2​a3​a4​和 b 1 b 2 b 3 b 4 b_1b_2b_3b_4 b1​b2​b3​b4​，如果从 a 1 a 2 a 3 a_1a_2a_3 a1​a2​a3​到 b 1 b 2 b 3 b_1b_2b_3 b1​b2​b3​需要操作N次，那么如果 a 4 = b 4 a_4=b_4 a4​=b4​，则 a 1 a 2 a 3 a 4 → b 1 b 2 b 3 b 4 a_1a_2a_3a_4\to b_1b_2b_3b_4 a1​a2​a3​a4​→b1​b2​b3​b4​也只需要N次。否则的话需要将 a 4 a_4 a4​变成 b 4 b_4 b4​，可能需要N+1次。

当然，这里其实并没有考虑到错位的情况，即 a 1 a 2 a 3 a 4 a_1a_2a_3a_4 a1​a2​a3​a4​可能和 b 1 b 2 b 3 b_1b_2b_3 b1​b2​b3​有着更近的距离（此即删除）；或者 a 1 a 2 a 3 a_1a_2a_3 a1​a2​a3​可能和 b 1 b 2 b 3 b 4 b_1b_2b_3b_4 b1​b2​b3​b4​距离更近（此即插入）。

所以根据这个原理，我们可以写出MED算法的递归程序。

def MED(str1,str2):len1 = len(str1)len2 = len(str2)if len1 == 0: return len2#如果str1为空，则返回str2的长度if len2 == 0: return len1if str1==str2: return 0d = 0 if str1[-1]==str2[-1] else 1return min(MED(str1,str2[:len2-1])+1,MED(str1[:len1-1],str2)+1,MED(str1[:len1-1],str2[:len2-1])+d)

测试一下

>>> str1 = "python">>> str2 = "numpy">>> MED(str1,str2)6

说明二者毫无相似之处，尽管都有py，但最佳匹配方案显然不是把python的thon去掉，然后把numpy的num去掉；而是把python的n去掉后，逐字符变为numpy。

相比之下

>>> MED("numpy","scipy")3

动态规划实现

所谓动态规划，就是把递归的所有情况都列举出来，例如对比numpy和scipy，其递归的尽头必然是n和s的对比，或者更进一步，是n和""，s和""以及""和""之间的对比。接下来，n和s对比的结果返回给n和sc、nu和s以及nu和sc。

这样就可以得到一个对比矩阵

M = [ n u m p y s 1 2 c 2 2 i p y ] M=\begin{bmatrix} &n&u&m&p&y\\ s&1&2\\ c&2&2\\i&\\p\\y \end{bmatrix} M=⎣⎢⎢⎢⎢⎢⎢⎡​scipy​n12​u22mpy⎦⎥⎥⎥⎥⎥⎥⎤​

反复进行这种对比，矩阵最右下角的值即为二者的Levenshtein距离。

def dpMED(str1,str2):L1 = len(str1)+1L2 = len(str2)+1mat = [[i+j for j in range(L2)] for i in range(L1)]for i in range(1,L1):for j in range(1,L2):d = 0 if(str1[i-1]==str2[j-1]) else 1mat[i][j] = min(mat[i-1][j]+1, mat[i][j-1]+1, mat[i-1][j-1]+d)return mat[-1][-1]