stephen's blog

[object Object] object(s)
 

最小编辑距离问题(Edit Distance)

前言

最近在研究react-diff算法的时候,遇到了两个Virtual DOM列表的Diff,其实就是典型的最小编辑距离(Edit Distance)问题,于是抱着强烈的好奇心去研究了一番并做个总结。

定义

什么是编辑距离?简单来说就是两个字符串之间,一个转成另一个的最少编辑操作次数,也就是说编辑距离是衡量两个字符串相似性的度量方法,距离越小相似度越大,而其中允许编辑的操作有:插入(insert),删除(delete)以及替换(substitution)。

这里可以看具体问题的描述(摘自leetcode):

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character

思路

具体思路如下图:

假设字符串X的长度为N,字符串Y的长度为M,D(i,j)表示字符串X[1...i]转换为Y[1...j]的编辑距离:

注意: 其中X[i]和Y[j]表示字符串X和Y的最后一位

初始化:

D(i,0) = i,表示Y字符串为空,X[1…i]全部删除,所以编辑距离为i
D(0,j) = j,表示X字符串为空,新插入Y[1…j],所以编辑距离为j

递归关系:

例子中 >> 定义为字符串转换

最后求的这三项的最小值就是编辑距离。

递归算法

我们按照上面的思路用代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const editDistance = (
word1,
word2,
i,
j
) => {
const len1 = word1.length
const len2 = word2.length
const d = []
if(len1 === 0) {
return len2
}else if(len2 === 0) {
return len1
}else if(word1[i-1] === word2[j-1]){
return editDistance(word1,word2,i-1,j-1)
}else{
return Math.min(editDistance(word1,word2,i-1,j) + 1,
editDistance(word1,word2,i,j-1) + 1,
editDistance(word1,word2,i-1,j-1) + 2
)
}
}

显然这样写的代码,性能是一个很大的问题,时间复杂度是随指数增长的,所以解决该问题的办法是使用动态规划求解。

动态规划算法

我们可以用动态规划的方法来优化时间复杂度
以word1为‘sot’,word2为‘stop’为例,我们首先创建一个矩阵:

计算 i=1,j=1:

得到:

计算i=1,j=2:

得到:

最终得到

于是可以得到最短编辑距离为d[m][n] = 3,现在时间复杂度控制在了O(mn)。

具体算法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const editDistance = (
word1,
word2
) => {
const len1 = word1.length
const len2 = word2.length
let d = []
let i,j
for(i = 0; i <= len1; i++){
d[i] = []
d[i][0] = i
}
for(j = 0; j <= len2; j++){
d[0][j] = j
}
for(i = 1; i<= len1; i++){
for(j = 1; j <= len2; j++){
if(word1[i-1] == word2[j-1]){
d[i][j] = d[i-1][j-1]
}else{
d[i][j] = Math.min(d[i-1][j]+1,d[i][j-1]+1,d[i-1][j-1]+2)
}
}
}
return d[len1][len2]
}

参考