文章目录
- 1. 编辑距离的定义
- 2. 基于动态规划的求解算法
- 2.1. 递推公式
- 2.2. python代码实现
- 3. 应用
https://www.jianshu.com/p/a617d20162cf 1. 编辑距离的定义
编辑距离（Minimum Edit Distance，MED），由俄罗斯科学家 Vladimir Levenshtein 在1965年提出，也因此而得名 Levenshtein Distance。编辑距离一般用于度量两个序列相似程度的指标，具体来说，它计算的是一个序列A最少可以经过多少次 *** 作变成另一个序列。这里的 *** 作包括以下三种：
- 插入（Insert）
- 删除（Deletion）
- 替换（Substitution）
比如字符串australia和austrian，后者可以由前者进行三次 *** 作得到（2次删除，分别是a和l；一次插入，n）；字符串ABCDE和AFGE进行3次 *** 作得到。
2. 基于动态规划的求解算法 2.1. 递推公式对于两个字符串
a
,
b
a,b
a,b，记
f
(
i
,
j
)
f(i,j)
f(i,j)为
a
a
a中前
i
i
i个字符
a
[
0
:
i
]
a[0:i]
a[0:i]与
b
b
b中前
j
j
j个字符
b
[
0
:
j
]
b[0:j]
b[0:j]的编辑距离，则有：
f
(
i
,
j
)
=
{
m
a
x
(
i
,
j
)
,
i
f
m
i
n
(
i
,
j
)
=
0
m
i
n
{
f
(
i
−
1
,
j
)
+
1
f
(
i
,
j
−
1
)
+
1
f
(
i
−
1
,
j
−
1
)
+
1
(
a
i
≠
b
j
)
i
f
m
i
n
(
i
,
j
)
≠
0
f(i,j)=left{ begin{aligned} &max(i,j),&if min(i,j)=0 \ &min { left{ begin{aligned} &f(i-1,j)+1\ &f(i,j-1)+1\ &f(i-1,j-1)+1_{(a_ineq b_j)} end{aligned} right. } &if min(i,j)neq 0 end{aligned} right.
f(i,j)=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧max(i,j),min⎩⎪⎨⎪⎧f(i−1,j)+1f(i,j−1)+1f(i−1,j−1)+1(ai=bj)if min(i,j)=0if min(i,j)=0
解释：
- m a x ( i , j ) max(i,j) max(i,j)很好理解，当 i = 0 i=0 i=0时， a [ 0 : i ] a[0:i] a[0:i]变为 b [ 0 : j ] b[0:j] b[0:j]只需要插入 j j j个字符；当 = 0 =0 =0时， a [ 0 : i ] a[0:i] a[0:i]变为 b [ 0 : j ] b[0:j] b[0:j]只需要删除 i i i个字符.
- f ( i − 1 , j ) + 1 f(i-1,j)+1 f(i−1,j)+1表示 a [ 0 : i ] a[0:i] a[0:i]变为 b [ 0 : j ] b[0:j] b[0:j]的一种方式是，先将 a [ 0 : i − 1 ] a[0:i-1] a[0:i−1]转变为 b [ 0 : j ] b[0:j] b[0:j]，然后删除 a [ i − 1 ] a[i-1] a[i−1].
- f ( i , j − 1 ) + 1 f(i,j-1)+1 f(i,j−1)+1表示 a [ 0 : i ] a[0:i] a[0:i]变为 b [ 0 : j ] b[0:j] b[0:j]的一种方式是，先将 a [ 0 : i ] a[0:i] a[0:i]转变为 b [ 0 : j − 1 ] b[0:j-1] b[0:j−1]，然后插入 b [ j − 1 ] b[j-1] b[j−1].
- f ( i − 1 , j − 1 ) + 1 ( a i ≠ b j ) f(i-1,j-1)+1_{(a_ineq b_j)} f(i−1,j−1)+1(ai=bj)表示 a [ 0 : i ] a[0:i] a[0:i]变为 b [ 0 : j ] b[0:j] b[0:j]的一种方式是，先将 a [ 0 : i − 1 ] a[0:i-1] a[0:i−1]转变为 b [ 0 : j − 1 ] b[0:j-1] b[0:j−1]，然后判断 a [ i − 1 ] a[i-1] a[i−1]和 b [ j − 1 ] b[j-1] b[j−1]是否相等，若相等，则无需 *** 作，否则需要将 a [ i − 1 ] a[i-1] a[i−1]替换为 b [ j − 1 ] b[j-1] b[j−1].
上面的第一条是作为初始化，后三条是递推公式的所有情况，所以后三条应该选择 *** 作次数最小的那条。
如果将上述地推过程的中间结果存储下来，则会得到如下图所示的矩阵
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
matrix=[[i+j for j in range(len(word2)+1)] for i in range(len(word1)+1)]
for i in range(1,len(word1)+1):
for j in range(1,len(word2)+1):
if word1[i-1]==word2[j-1]:
matrix[i][j]=matrix[i-1][j-1]
else:
matrix[i][j]=matrix[i-1][j-1]+1
matrix[i][j]=matrix[i-1][j]+1 if matrix[i-1][j]+1
3. 应用
常见的应用是计算ASR模型的错字率（WER, Word Error Rate），以及nlp里面计算两个文本的相似度
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）