转：https://www.jianshu.com/p/a617d20162cf

概述

编辑距离（Minimum Edit Distance，MED），由俄罗斯科学家 Vladimir Levenshtein 在1965年提出，也因此而得名 Levenshtein Distance。

在信息论、语言学和计算机科学领域，Levenshtein Distance 是用来度量两个序列相似程度的指标。通俗地来讲，编辑距离指的是在两个单词<w1,w2><w_1, w_2><w1​,w2​>之间，由其中一个单词w1w_1w1​转换为另一个单词w2w_2w2​所需要的最少单字符编辑操作次数。

在这里定义的单字符编辑操作有且仅有三种：

• 插入（Insertion）
• 删除（Deletion）
• 替换（Substitution）

形式化定义

假设有俩个字符串str1和str2，如果两个字符串首位的字符有相等的情况的话，比如首字符相等，那么这两个字符串的编辑距离就等于"str1[1:]和str2[1:]"的编辑距离；如果首位不存在相等的情况，那么这个位置必然对最终编辑距离的产生影响，即编辑距离等于"str1[1:]和str2"或者"str2[1:]和str1"中编辑距离的最小者加1。这就形成了一个递推关系，公式如下

leva,b(i,j)={max{i,j},ifmin{i,j}=0min{leva,b(i−1,j)+1leva,b(i,j−1)+1leva,b(i−1,j−1)+I(ai≠bi)otherwise.lev_{a,b}(i,j)= \begin{cases} max\{i,j\},\quad if \quad min\{i,j\}=0 \\ min \begin{cases} lev_{a,b}(i-1,j) + 1 \\ lev_{a,b}(i,j-1) + 1 \\ lev_{a,b}(i-1,j-1)+I_{(a_i \neq b_i)} \end{cases} \quad otherwise. \end{cases}leva,b​(i,j)=⎩⎨⎧​max{i,j},ifmin{i,j}=0min⎩⎨⎧​leva,b​(i−1,j)+1leva,b​(i,j−1)+1leva,b​(i−1,j−1)+I(ai​=bi​)​​otherwise.​

a,b表示字符串，i,j是长度

leva,b(i−1,j)+1lev_{a,b}(i-1,j) + 1leva,b​(i−1,j)+1表示删除aia_iai​

leva,b(i,j−1)+1lev_{a,b}(i,j-1) + 1leva,b​(i,j−1)+1表示删除bjb_jbj​

leva,b(i−1,j−1)+I(ai≠bi)lev_{a,b}(i-1,j-1)+I_{(a_i \neq b_i)}leva,b​(i−1,j−1)+I(ai​=bi​)​表示替换bjb_jbj​

I(ai≠bi)I_{(a_i \neq b_i)}I(ai​=bi​)​为一个指示函数。相等时等于0，不相等时等于1.

两个字符串删除和插入是等价的，即a串（dogs)的删除和b串（dog)插入是等价的，替换也是等价的（bat, cat)。

问题能够分解成子问题的形式。想到：自顶向下的递归和自底向上的动态规划

动态规划方法通常需要初始化一个矩阵来记录各个子问题。

以 xxc和 xyz 为例，建立一个矩阵，通过矩阵记录计算好的距离：

初始化矩阵的第一行和第一列:

推导第二行

直到最后完成

动态规划算法实现

defLevenshtein_Distance(x1,x2):#初始化矩阵， 第一行和第一列是正确值matrix=[[i+jforiinrange(len(x2)+1)]forjinrange(len(x1)+1)]#从第二行第二列开始更新矩阵foriinrange(1,len(x1)+1):forjinrange(1,len(x2)+1):ifx1[i-1]==x2[j-1]:t=0else:t=1matrix[i][j]=min(matrix[i-1][j]+t,matrix[i][j-1]+t,matrix[i-1][j-1]+t)returnmatrix[len(x1)][len(x2)]