Alan Lee

理解编辑距离

2020/05/22 Share

顾名思义,编辑距离(Edit distance)是一种距离,用于衡量两个字符串之间的远近程度,方式是一个字符串至少需要多少次基础变换才能变成另一个字符串,可应用在拼写检查、判断 DNA 相似度等场景中。根据可操作的基础变换不同,可分为以下几种:

  • 莱文斯坦距离(Levenshtein distance):最常见的编辑距离,基础变换包括插入、删除和替换。但是需要注意一点的是,当每种变换发生时,产生的距离(或者称为代价)并不一定是 1,例如斯坦福大学关于最小编辑距离的课件中,一次替换产生的距离就可能是 2。
  • 最长公共子序列(LCS)距离:基础变换包括插入和删除。
  • Jaro 距离:基础变换只包括转置,即交换两个字符的位置,AB -> BA。
  • 汉明距离:基础变换只包括替换,所以只能应用于两个字符串长度相等的情况。

本文只讨论最常见的第一种形式,莱文斯坦距离。

解法

解法有两种:暴力法和动态规划法。

暴力法

暴力法思想很直接,采用递归思想,直接取所需插入、删除和替换操作的最小值。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def brute_force(s1, s2):
m = len(s1)
n = len(s2)
if m == 0:
return n
if n == 0:
return m
if s1[m - 1] == s2[n - 1]:
c = 0
else:
c = 1 # 一次替换产生的距离,也可以定义成 2
return min(
brute_force(s1, s2[: n - 1]) + 1, # 插入
brute_force(s1[: m - 1], s2) + 1, # 删除
brute_force(s1[: m - 1], s2[: n - 1]) + c, # 替换
)

缺点就是耗时很大,这是由于存在大量的重复计算。有多大量?我举一个例子,brute_force('geek', 'gesek'),下图是函数调用次数排行榜:

可以看到,排第一的 brute_force('', 'g') 被调用了 192 次,brute_force() 总计被调用了 1021 次,这还仅仅是对两个长度分别为 4、5 的字符串进行的比较,其耗时程度可见一斑。

动态规划法

动态规划法是对暴力法的改进,把所有的重复计算都干掉,空间换时间,将计算过的值存储到一个矩阵中,后面用的时候就直接取。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def levenshtein_distance_dp(s1, s2):
m = len(s1) + 1
n = len(s2) + 1
dp_table = np.zeros((m, n))
# 初始化
for i in range(m):
dp_table[i, 0] = i
for i in range(n):
dp_table[0, i] = i

for i in range(1, m):
for j in range(1, n):
dp_table[i, j] = min(
dp_table[i - 1, j] + 1,
dp_table[i, j - 1] + 1,
dp_table[i - 1, j - 1] + (1 if s1[i - 1] != s2[j - 1] else 0),
)
return int(dp_table[m - 2, n - 2])

初始化为什么是那样呢?想象一下,假设我们想计算 geek 和 gesek 之间的距离,即从 geek 到 gesek 至少需要多少步,记着这一点。和其他动态规划问题一样,首先会有一个 DP 表:

“” g e e k
“”
g
e
s
e
k

从第一个单元开始,先看第一列,"" -> "" 所需步骤为 0(因为相等),所以第一个填 0。

“” g e e k
“” 0
g
e
s
e
k

第二行第一列,"" -> g,需要插入一个字符 g,因此所需步骤为 1:

“” g e e k
“” 0
g 1
e
s
e
k

第三行第一列,"" -> ge,需要插入两个字符 ge,因此需要两个步骤:

“” g e e k
“” 0
g 1
e 2
s
e
k

以此类推,得到第一列:

“” g e e k
“” 0
g 1
e 2
s 3
e 4
k 5

对于第一行,同样的道理,只不过是删除操作,例如 ge -> "" 需要删除两个字符,即两步删除操作。

“” g e e k
“” 0 1 2 3 4
g 1
e 2
s 3
e 4
k 5

这就完成了初始化过程。从过程中我们可以看出,其实对于一个单元格 $T[i,j]$ 来说,其左上角 $T[i-1, j-1]$ 是最小替换步数,正上方 $T[i-1, j]$ 是最小删除步数,左边 $T[i, j-1]$ 是最小插入步数,然后我们只需根据条件取最小即可,表格剩余部分就是这么推出来的。

至于这个改进有多猛?我做了个实验:假设 s1 和 s2 长度相等,依次测试长度为 1-15 时的不同方法耗时(单位为秒)。结果看下图:

可以看到暴力法是指数级增长,当字符串长度为 15 时,暴力法耗时已经达到 30000 秒,约为 8.3 小时,动态规划法仅耗时万分之六秒。而当长度翻倍变为 30 时,暴力法预计至少需要 1.27 亿年才能算万,具体秒数可以点开图右上角灰色的 $e^x$ 来查看暴力法耗时的模拟曲线。该曲线并不是 $y=e^x$ 的曲线,具体公式如下:

还有

一些没说到的:

  • 有时候只求出编辑距离可能还不够,还需要回溯,对两个字符串进行对齐。
  • Weighted Edit Distance,即加权编辑距离,这其实是在初始化和后续计算时加入了一些权重作为先验,一步操作产生的距离不再是 1 或者 2。
  • 其他变种……

这些等有时间再说吧。

Reference

END

CATALOG
  1. 1. 解法
    1. 1.1. 暴力法
    2. 1.2. 动态规划法
  2. 2. 还有
  3. 3. Reference
  4. 4. END