概念
编辑距离又称Levenshtein Distance，主要用来衡量两个序列的相似程度。具体指的是：
1
2
3
4
5
6
两个序列之间，由一个序列转换到另一个序列所需要的的次数
主要的操作包含：插入、删除、修改
例子：
abc->ab：将abc删除一个字符即可，编辑距离为1
ab->abc：在ab后加一个字符即可，编辑距离为1
abd->abc：将字符d换为字符c即可，编辑距离为1
公式以及解释
\(\operatorname{lev}_{a, b}(i, j)=\left\{\begin{array}{ll} \max (i, j) & \text { if } \min (i, j)=0 \\ \min \left\{\begin{array}{ll} \operatorname{lev}_{a, b}(i-1, j)+1 & \text { otherwise } \\ \operatorname{lev}_{a, b}(i, j-1)+1 & \\ \left(\operatorname{lev}_{a, b}(i-1, j-1)+1_{\left(a_{i} \neq b_{j}\right)}\right. \end{array}\right. \end{array}\right.\) 第一行表示的是：当第一个序列或者第二个序列为空的时候，那个整个的变换过程就是增加相应长度的字符即可。
第二行到第四行统一处理一般的情况：
1
2
3
4
第二行表示：通过一定的操作将i-1，变为j，然后再将i移除即可
第三行表示：通过一定的操作将i变为j-1，然后再加上j即可
第四行表示：通过一定的操作i-1转换为j-1，后面如果i=1，则结束，如果i不等j则再修改i为j。
2,3,4综合得到操作次数最少的结果。
实现
递归形式：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def edit_distence(str1, str2):
"""递归"""
if len(str1) == 0:
return len(str2)
elif len(str2) == 0:
return len(str1)
elif str1 == str2:
return 0
if str1[len(str1) - 1] == str2[len(str2) - 1]:
d = 0
else:
d = 1
return min(edit_distence(str1, str2[:-1]) + 1,
edit_distence(str1[:-1], str2) + 1,
edit_distence(str1[:-1], str2[:-1]) + d)
动态规划：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def edit_distence(str1, str2):
"""动态规划"""
import numpy as np
matrix = np.zeros((len(str1) + 1, len(str2) + 1), dtype=np.int)
matrix[0] = np.arange(len(str1) + 1)
matrix[:, 0] = np.arange(len(str2) + 1)
# 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 = 0
else:
d = 1
matrix[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 包的使用
1
Levenshtein.distance(str1, str2)
应用
- 错别字纠正
- 也可以作为一种相似度算法
- 拼音检查
