Min Edit Distance

Posted on | In

用例

问：最少操作多少次可以把字符串T变为S？
例：S=“ABCF”，T=“DBFG”
则可以

  1. 把D替换为A
  2. 删掉G
  3. 插入C

最短编辑距离概念

给定两个字符串S和T，对于T，我们允许如下三个操作

  • 在任意位置添加任一字符
  • 删除存在的任一字符
  • 修改任一字符

将字符串T转换成成字符串S所使用的操作次数就是编辑距离，其中，最少的操作次数就是最短编辑距离（Min Edit Distance）

算法逻辑详解

向S和T中分别插入字符-，使得两个字符串相同字符尽量对齐，且两个字符串最终长度相同

setting

  1. 如果S，T对应位置都是相同的普通字符，则不扣分，如位置2、4
  2. 如果S，T对应位置都是普通字符但不相同，则扣1分（对应修改操作），如位置1
  3. 如果S的位置为-，但是T位置是不同字符，则扣1分（对应删除操作），如位置5
  4. 如果S的位置为普通字符，但是T位置为-，则扣1分（对应增加操作），如位置3

设f(i, j)表示字符串S的前i位和T的前j位对齐后的最少扣分，则最后一位的对齐情况为

  1. 当S[i] == T[j] 时，前i-1和j-1位已经完成对齐，此时最小扣分为f(i-1, j-1)
  2. 当S[i] != T[j]时，此时最少扣分为f(i-1, j-1)+1
  3. 当S前i位和T的前j-1位已经对齐，此时最少扣分为f(i, j-1)+1
  4. 当S前i-1位和T的前j位对齐，此时最少扣分为f(i-1, j)+1

定义一个函数same(i, j)，如果S[i] == T[j]则为0表示不扣分，否则为1也就是扣分，此时f的递推表达式如下

f(i, j) = min{ f(i-1, j-1)+same(i-1, j-1), f(i-1, j)+1, f(i, j-1)+1}

初始值：f(0, j) = j, f(i, 0) = i

动态规划算法

定义一个矩阵dp[m][n], 其中m=len(string1)+1，n=len(string2)+1，+1是为了避免长度为0；dp[i][j]为string1的前i个字符构成的字符串，与string2的前j个字符构成的字符串的编辑距离。

插入操作：在string1的前i个字符后插入一个新的字符，使得插入的字符等于新加入的string2[j]，插入操作对于string1来说，i没有前进，但是对于string2来说，j前进了一位，也就是说，dp[i][j] = dp[i]dp[j-1]+1

删除操作：在string1的第i个字符后删除一个字符，使得删除后的字符串string1[:i-1]与word[:j]相同，那么删除操作对于原string2来说，j没有前进，但是i前进了一位，也就是说，dp[i][j] = dp[i-1][j]+(0/1)

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 初始化过程
for j=0 to n do
	f[j] =  j
endfor

# 连续处理
for i=1 to m do
	last = f[0]
	f[0] = i
	for j=1 to n do
		temp = f[i, j]
		f[i, j] = min(last+same(i, 1), remp+1, temp+1, f[j-1]+1)
		last = temp
	endfor
endfor

算法代码

0%