一、简介
编辑距离在NLP中是一种比较比较实用，且原理简单的一种算法，一般用于拼写纠错，相似度计算等，特别是在搜索领域，通过计算输入词与候选词的编辑距离，可以一定量的帮助用户进行拼写纠错。
二、原理
本文没有屌炸天的数学公式，读起来不需要那么费劲！
假设你正在百度输入框中想搜索编辑距离，结果手残输成了遍地距离，坐在你身边的女朋友哈哈大笑说你不行，然后她飞快的输入，结果...编辑剧,你扭头就是一个大笑“让你看那么剧”，为了不认怂又自己来，结果，他奶奶个球的又打错了-编辑距离的，哎，带键盘了！故事到此结束，进入正题：
上述中，有了三种情况需要转换为正确的输入：
遍地距离 ->编辑距离：需要替换 遍为编 ，地为辑，共两个替换操作，两词的距离为2
编辑剧 ->编辑距离：需要替换 剧为距 ，再添加一个离，共一个替换操作，一个添加操作，两词的距离为2
编辑距离的 ->编辑距离：需要删除 的，共一个删除操作，两词的距离为1
上文中，为了得到正确的词，一共进行了三种操作，分别是添加、删除、替换，编辑距离正是通过这三种操作进行词的变换，得到正确词的一种手段，一个操作为一个单位的距离，两词要相等需要的做的最少操作即使两词之间的编辑距离。
三、求解分析
为了求解问题，我们找一个复杂的例子来分析一下
- sduyi ->study
从后面开始，一个词一个词分析，为了保证末尾相等：
要么删除sduyi的 i，这样末尾相同，只用比较
和
->editDistance(word1[:-1],word2)
要么替换sduyi的 i 为 y，这样末尾相同，只用比较
和
->editDistance(word1[:-1],word2[:-1])
要么在sduyi添加一个y，这样末尾相同，只用比较
和
->editDistance(word1,word2[:-1])
那么有三种操作，到底选取哪种呢？肯定是选择这三种中距离最小的一种，而且可以发现以上的过程可以用一个递归来求解，字符创的裁剪过程是一样的，不断的调用递归即可，那么递归什么时候停止呢，有以下几种情况：
word1截取完毕，只剩下word2的个别字符word2_left，那么剩余的编辑距离就是len(word2_left)
word2截取完毕，只剩下word1的个别字符word1_left，那么剩余的编辑距离就是len(word1_left)
四、递归求解
def editDistance(word1, word2):
# word1截取完毕
if len(word1) == 0:
return len(word2)
# word2截取完毕
if len(word2) == 0:
return len(word1)
# 如果word1和word2的末尾相等，那么只用比较word1[:len(word1)-1], word2[:len(word2)-1]
if word1[-1] == word2[-1] :
return editDistance(word1[:len(word1)-1], word2[:len(word2)-1])
# 没有满足上述条件的时候，递归求解三种操作的最小编辑距离
return 1 + min(
editDistance(word1, word2[:len(word2)-1]),
editDistance(word1[:len(word1)-1], word2),
editDistance(word1[:len(word1)-1], word2[:len(word2)-1])
)
五、动态规划求解
关于动态规划，https://blog.csdn.net/qq_21120275/article/details/100344151
这篇文章中已经提到过，要先找到三个关键因素
最优子问题就是上述分析中，从末尾开始，的三种操作的最距离（也可以从前面开始）即：
# +1是因为最后一位的删除、插入或者替换产生了一位的操作
min(
editDistance(word1, word2[:len(word2)-1])+1,
editDistance(word1[:len(word1)-1], word2)+1,
editDistance(word1[:len(word1)-1], word2[:len(word2)-1])+1
)
状态转移返程也在上面的代码中体现了,min里面的三种转移过程
至于边界条件就是上述递归中的终止条件，根据以上代码如下：
def edit_distance(word1,word2):
# 构建dp矩阵存储中间过程变量
dp = np.zeros([len(word1)+1,len(word2)+1])
print(dp)
for i in range(len(word1)+1):
for j in range(len(word2)+1):
if i == 0:
dp[i][j] = j
elif j == 0:
dp[i][j] = i
elif word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(
dp[i][j-1]+1,
dp[i-1][j]+1,
dp[i-1][j-1]+1
)
return dp[len(word1)][len(word2)]
六、现成的轮子
关于现成的轮子情参考Levenshtein，安装以后直接调用即可
本文如有什么错误还望大神指正！
