目录

一、概念

二、算法过程

三、举例说明

四、Python实现

1. 递归方式

2. 动态规划

3. Jupyter Notebook 步骤分解

一、概念

编辑距离的作用主要是用来比较两个字符串的相似度的，在NLP任务中经常会碰到比较两个字符串的相似度，比如拼写纠错和指代判断。用户很可能在搜索时输入错别字，比如“微信”输成了“为信”，但是搜索引擎返回的结果纠正为“微信”的搜索结果，如下图。另外比如“北京大学校长”和“北大校长”，“北京故宫博物院”和“北京故宫”都是指的同一个人或事物。

基本的定义如下所示：

编辑距离，又称Levenshtein距离（莱文斯坦距离也叫做Edit Distance），是指两个字串之间，由一个转成另一个所需的最少编辑操作次数，如果它们的距离越大，说明它们越是不同。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。

这个概念是由俄罗斯科学家Vladimir Levenshtein在1965年提出来的，所以也叫 Levenshtein 距离。它可以用来做DNA分析，拼字检测，抄袭识别等等。总是比较相似的，或多或少我们可以考虑编辑距离。

在概念中，我们可以看出一些重点那就是，编辑操作只有三种。插入，删除，替换这三种操作，我们有两个字符串，将其中一个字符串经过上面的这三种操作之后，得到两个完全相同的字符串付出的代价是什么就是我们要讨论和计算的。

例如：

我们有两个字符串： kitten 和 sitting，现在我们要将kitten转换成sitting，我们可以做如下的一些操作：

k i t t e n --> s i t t e n 将K替换成s

sitten --> sittin 将 e 替换成i

sittin --> sitting 添加g

如果str1=“ivan”，str2=“ivan”，那么经过计算后等于 0。没有经过转换。相似度=1-0/Math.Max(str1.length,str2.length)=1如果str1=“ivan1”，str2=“ivan2”，那么经过计算后等于1。str1的"1"转换"2"，转换了一个字符，所以距离是1，相似度=1-1/Math.Max(str1.length,str2.length)=0.8

二、算法过程

那么如何找到最小编辑距离呢？可以看作是一种操作路径的搜索，从一个字符串转变为另一个字符串的最短搜索路径。

从一个字符串转到另一个字符串的可能路径是非常多的，所有不同的操作路径，最终都会到达一种状态。采用动态规划的方法，每一种状态都记录下来最短的路径，然后从最终状态进行回溯。动态规划把一个大的问题转换成很多的子问题来处理。

最小编辑距离同时被多个人独立发现，由Wagner和Fischer在1974年命名。让我们先定义两个字符串间的最小编辑距离。有两个字符串X和Y，X长度为n，Y长度为m。D[i, j] 为X[1..i]到Y[1.. j]的最小编辑距离。X[1..i]表示X的前i个字符，Y[1.. j]表示Y的前j个字符，D[n,m]为X和Y的最小编辑距离。

采用动态规划方法计算D[n,m], D[i,j]从小到大采用图3-3计算，del-cost表示删除操作的代价值，ins-cost表示插入操作的代价值，sub-cost表示替换操作的代价值，source表示原字符串，target表示转换的目标字符串。如果定义插入和删除的代价值为1，替换的代价值为2。计算方法如下式：

明确代价值的最小编辑距离计算

最小编辑距离算法总结如下图：

三、举例说明

计算相似度公式：1-它们的距离/两个字符串长度的最大值。

其实这个算法并不难实现

我们用字符串“ivan1”和“ivan2”举例来看看矩阵中值的状况：

1、第一行和第一列的值从0开始增长

首先我们先创建一个矩阵，或者说是我们的二维数列，假设有两个字符串，我们的字符串的长度分别是m和n，那么，我们矩阵的维度就应该是(m+1)*(n+1)。注意，我们先给数列的第一行第一列赋值，从0开始递增赋值。我们就得到了图一的这个样子，之后我们计算第一列，第二列，依次类推，算完整个矩阵。我们的计算规则就是：

d[i,j]=min(d[i-1,j]+1 、d[i,j-1]+1、d[i-1,j-1]+temp) 这三个当中的最小值。其中：str1[i] == str2[j]，用temp记录它，为0，否则temp记为1，我们用d[i-1,j]+1表示增加操作，d[i,j-1]+1 表示我们的删除操作d[i-1,j-1]+temp表示我们的替换操作。

2、举证元素的产生 Matrix[i - 1, j] + 1 ; Matrix[i, j - 1] + 1 ; Matrix[i - 1, j - 1] + t 三者当中的最小值

3.依次类推直到矩阵全部生成

这个就得到了我们的整个完整的矩阵。

四、Python实现

1. 递归方式

def Levenshtein_Distance(str1, str2):"""计算字符串 str1 和 str2 的编辑距离:param str1:param str2:return:"""matrix = [[ i + j for j in range(len(str2) + 1)] for i in range(len(str1) + 1)]for i in range(1, len(str1)+1):for j in range(1, len(str2)+1):if(str1[i-1] == str2[j-1]):d = 0else:d = 1matrix[i][j] = min(matrix[i-1][j]+1, matrix[i][j-1]+1, matrix[i-1][j-1]+d)return matrix[len(str1)][len(str2)]Levenshtein_Distance("Shanghai","Beijing")

2. 动态规划

递归是从后向前分解，那与之相对的就是从前向后计算，逐渐推导出最终结果，此法被称之为动态规划。动态规划很适用于具有重叠计算性质的问题，但这个过程中会存储大量的中间计算的结果，一个好的动态规划算法会尽量减少空间复杂度。

def Levenshtein_Distance_Recursive(str1, str2):if len(str1) == 0:return len(str2)elif len(str2) == 0:return len(str1)elif str1 == str2:return 0if str1[len(str1)-1] == str2[len(str2)-1]:d = 0else:d = 1return min(Levenshtein_Distance_Recursive(str1, str2[:-1]) + 1,Levenshtein_Distance_Recursive(str1[:-1], str2) + 1,Levenshtein_Distance_Recursive(str1[:-1], str2[:-1]) + d)Levenshtein_Distance_Recursive("Shanghai","Beijing")

3. Jupyter Notebook 步骤分解

初始化的矩阵

def minEditDist(sm,sn):m,n = len(sm)+1,len(sn)+1# create a matrix (m*n)matrix = [[0]*n for i in range(m)]matrix[0][0]=0for i in range(1,m):matrix[i][0] = matrix[i-1][0] + 1for j in range(1,n):matrix[0][j] = matrix[0][j-1]+1for i in range(m):print(matrix[i])mindist=minEditDist("Shanghai","Beijing")

最终矩阵

def minEditDist(sm,sn):m,n = len(sm)+1,len(sn)+1# create a matrix (m*n)matrix = [[0]*n for i in range(m)]matrix[0][0]=0for i in range(1,m):matrix[i][0] = matrix[i-1][0] + 1for j in range(1,n):matrix[0][j] = matrix[0][j-1]+1cost = 0for i in range(1,m):for j in range(1,n):if sm[i-1]==sn[j-1]:cost = 0else:cost = 1matrix[i][j]=min(matrix[i-1][j]+1,matrix[i][j-1]+1,matrix[i-1][j-1]+cost)for i in range(m):print(matrix[i])return matrix[m-1][n-1]mindist=minEditDist("Shanghai","Beijing")

最终结果

def minEditDist(sm,sn):m,n = len(sm)+1,len(sn)+1# create a matrix (m*n)matrix = [[0]*n for i in range(m)]matrix[0][0]=0for i in range(1,m):matrix[i][0] = matrix[i-1][0] + 1for j in range(1,n):matrix[0][j] = matrix[0][j-1]+1cost = 0for i in range(1,m):for j in range(1,n):if sm[i-1]==sn[j-1]:cost = 0else:cost = 1matrix[i][j]=min(matrix[i-1][j]+1,matrix[i][j-1]+1,matrix[i-1][j-1]+cost)return matrix[m-1][n-1]mindist=minEditDist("Shanghai","Beijing")mindist

输出结果：8

所以可以得到“Shanghai”，和“Beijin”的编辑距离为8