最短编辑距离（Edit Distance）

66 阅读 0 评论 44 点赞

我是靠谱客的博主欣喜毛衣，最近开发中收集的这篇文章主要介绍最短编辑距离（Edit Distance），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1.问题描述

有两个字符串S1, S2；编辑距离指将S1转化为S2（或S2转化为S1）所需要的操作次数；这里的操作次数指插入一个字符、删除一个字符或者替换一个字符（有时替换字符不当作是一次操作，会被当成先删除，再插入两次操作）；

最短编辑距离：指将字符串S1转化为S2的所需的最小操作次数

2.状态转移方程

$d[i][j]left{begin{matrix} j ,& i=0\ i ,& j=0\ minleft{begin{matrix} d[i][j-1]+1\ d[i-1][j]+1\ d[i-1][j-1]+left{begin{matrix} 0, &a_{i}=b_{j}\ 1, &a_{i} neq b_{j} end{matrix}right. end{matrix}right. ,& i neq 0 & j neq 0 end{matrix}right.$

3.推导过程

对于一个串S1来说，将其转化为S2：

1.ad->and：插入 ny

2.abcd->acd：删取 b

3.sum->sun：将 m 替换为 n

对于长的串，甚至是句子A，B可以将其拆分开，接下来用（A，B）表示 A，B的编辑距离：

1.（ad, and）=>（d, nd）=>（sd, nd）+ 1；这里加一指由 d 到 sd 已经插入过一次

2.（abcd, acd）=>（ab, a）

3.（sum, sun）=>（m, n）

这里的 => 表示问题的转化关系

则最短编辑距离是一个阶段性问题，而且每一步都基于其初始状态和第一步做出的决定，

即可以使用动态规划来解决

使用一个例子来说明："fiction" 和 "ignore" 的最短编辑距离

str_a = "ignore"；str_b = "fiction"

利用矩阵来推导，distance[i][j] 表示由 str_a[0:i - 1] 到 str_b[0:j - 1] 的最短编辑距离：

例：distance[3][2] 指由 "ign" 到 "fi" 的最短编辑距离（接下来使用 d[i][j] 表示 distance[i][j]）

1.初始化矩阵

对于任意的字符串到一个空串的最短编辑距离都是该字符串的长度，依此来初始化矩阵

distance		str_b
distance		""(空串)	"f"	"i"	"c"	"t"	"i"	"o"	"n"
str_a	""(空串)	0	1	2	3	4	5	6	7
	"i"	1
	"g"	2
	"n"	3
	"o"	4
	"r"	5
	"e"	6

2.填充矩阵

对于任意两个字符串( $a_{1}a_{2}...a_{m}$ , $b_{1}b_{2}...b_{n}$ )的最短编辑距离都有三种基于其子串的推导：

<1>（ $a_{1}a_{2}...a_{m}$ , $b_{1}b_{2}...b_{n}$ ）=（ $a_{1}a_{2}...a_{m-1}$ , $b_{1}b_{2}...b_{n}$ ）+ 1；

先由子串到目标串再插入

<2>（ $a_{1}a_{2}...a_{m}$ , $b_{1}b_{2}...b_{n}$ ）=（ $a_{1}a_{2}...a_{m}$ , $b_{1}b_{2}...b_{n-1}$ ）+ 1；

将目标串删除一个字符（相当于匹配目标串子串后再插入目标串的尾部字符）

<3>（ $a_{1}a_{2}...a_{m}$ , $b_{1}b_{2}...b_{n}$ ）=（ $a_{1}a_{2}...a_{m-1}$ , $b_{1}b_{2}...b_{n-1}$ ）+ 0/1 ；当 $a_{m}=b_{n}$ 时为 0，当 $a_{m} neq b_{n}$ 为 1；