2.9 最小编辑距离

我们经常需要比较两个词或字符串有多相似。后续章节会看到，这种需求最常见于自动语音识别或机器翻译等任务；在这些任务中，我们希望知道一个词序列与某个参考词序列有多相似。

编辑距离（edit distance）提供了一种量化字符串相似性直觉的方法。更严格地说，两个字符串之间的最小编辑距离（minimum edit distance），是把一个字符串转换成另一个字符串所需的最少编辑操作数；编辑操作包括插入、删除和替换等。本节以单个词介绍编辑距离，但该算法同样适用于完整字符串。

例如，intention 与 execution 之间的距离是 5：删除一个 i，把 n 替换成 e，把 t 替换成 x，插入 c，再把 n 替换成 u。查看图 2.17 所示的字符串距离核心可视化——两个字符串之间的对齐（alignment）——会更容易理解这一点。给定两个序列，对齐就是两个序列的各个子串之间建立的对应关系。因此，我们说 I 与空字符串对齐，N 与 E 对齐，依此类推。对齐字符串下方还有另一种表示：一系列符号构成操作列表，说明如何把上方字符串转换成下方字符串；其中 d 表示删除，s 表示替换，i 表示插入。

I N T E * N T I O N * E X E C U T I O N

^{d s s i s}

图 2.17 以对齐形式表示两个字符串之间的最小编辑距离。最后一行给出把上方字符串转换成下方字符串的操作列表：d 表示删除，s 表示替换，i 表示插入。

还可以为每种操作指定特定的代价或权重。两个序列之间的 Levenshtein 距离（Levenshtein distance）采用最简单的加权方式，三种操作的代价都为 1（Levenshtein, 1966）；把一个字母替换成它本身，例如把 t 替换成 t，代价为 0。intention 与 execution 之间的 Levenshtein 距离是 5。Levenshtein 还提出了该指标的另一个版本：每次插入或删除的代价为 1，但不允许替换。（这等价于允许替换、但把每次替换的代价设为 2，因为任何替换都可以表示成一次插入和一次删除。）在这个版本下，intention 与 execution 之间的 Levenshtein 距离是 8。

2.9.1 最小编辑距离算法¶

如何找到最小编辑距离？可以把它看作一项搜索任务：搜索从一个字符串到另一个字符串的最短路径，即一个编辑序列。

图 2.18 把求编辑距离视为一个搜索问题。

所有可能编辑构成的空间极其庞大，无法进行朴素搜索。不过，许多不同编辑路径最终会到达同一个状态（字符串）。因此，与其重新计算所有这些路径，不如在每次看到某个状态时，只记住到达它的最短路径。我们可以使用动态规划（dynamic programming）做到这一点。动态规划是一类最早由 Bellman（1957）提出的算法，它们采用表格驱动的方法，通过组合各个子问题的解来解决问题。自然语言处理中一些最常用的算法会使用动态规划，例如 Viterbi 算法（第 18 章）和用于句法分析的 CKY 算法（第 19 章）。

动态规划问题背后的直觉是：妥善组合不同子问题的解，就能解决一个较大的问题。考虑图 2.19 所示、表示 intention 与 execution 之间最小编辑距离的最短转换词路径。

图 2.19 从 intention 到 execution 的路径。

设想最优路径（无论它具体是什么）中的某个字符串，例如 exention。动态规划的直觉是：如果 exention 位于最优操作列表中，那么该最优序列也必然包含从 intention 到 exention 的最优路径。为什么？如果从 intention 到 exention 存在一条更短的路径，我们就可以用它替换原路径，从而得到一条更短的总体路径；这样，原来的最优序列就不再最优，产生矛盾。

最小编辑距离算法由 Wagner and Fischer（1974）命名，但许多人曾独立发现该算法（参见第 18 章历史说明）。

首先定义两个字符串之间的最小编辑距离。给定长度为 $n$ 的源字符串 $X$ 和长度为 $m$ 的目标字符串 $Y$，定义 $D[i,j]$ 为 $X[1..i]$ 与 $Y[1..j]$ 之间的编辑距离，也就是 $X$ 的前 $i$ 个字符与 $Y$ 的前 $j$ 个字符之间的编辑距离。因此，$X$ 与 $Y$ 之间的编辑距离是 $D[n,m]$。

我们使用动态规划，自底向上组合子问题的解来计算 $D[n,m]$。在基本情形中，如果源子串长度为 $i$，目标字符串为空，那么从 $i$ 个字符变成 0 个字符需要执行 $i$ 次删除。如果目标子串长度为 $j$，而源字符串为空，那么从 0 个字符变成 $j$ 个字符需要执行 $j$ 次插入。算出较小 $i,j$ 对应的 $D[i,j]$ 后，就可以依据先前算出的较小值计算更大的 $D[i,j]$。$D[i,j]$ 的取值是到达矩阵中该位置的三条可能路径之最小值：

前文提到 Levenshtein 距离的两个版本：一个版本中的替换代价为 1，另一个版本中的替换代价为 2，也就是等价于一次插入加一次删除。这里采用第二个版本：插入与删除的代价均为 1（$\operatorname{ins-cost}(\cdot)=\operatorname{del-cost}(\cdot)=1$），替换的代价为 2；把相同字母彼此替换的代价例外地为 0。在这个 Levenshtein 距离版本下，$D[i,j]$ 的计算变为：

图 2.21 总结了该算法；图 2.20 则展示使用式 2.20 中 Levenshtein 距离版本，把该算法应用于 intention 和 execution 时的结果。

图 2.20 使用图 2.21 的算法计算 intention 与 execution 之间的最小编辑距离；这里采用的 Levenshtein 距离把插入或删除的代价设为 1，把替换的代价设为 2。

图 2.21 最小编辑距离算法，它是动态规划算法的一例。各项代价既可以固定（例如对任意 x，ins-cost(x) = 1），也可以因字母而异，以模拟某些字母比其他字母更容易被插入这一事实。我们假设把一个字母替换成它本身没有代价，即 sub-cost(x,x) = 0。

对齐 已知最小编辑距离，可以帮助拼写纠错等算法找到可能的纠正结果。不过，编辑距离算法还有另一项重要用途：只需稍作修改，它就可以给出两个字符串之间代价最小的对齐。对齐两个字符串在语音与语言处理中随处可见。在语音识别中，最小编辑距离对齐用于计算词错误率（第 16 章）；在机器翻译中，对齐也发挥作用，因为平行语料库（同时包含两种语言文本的语料库）中的句子需要彼此匹配。

要扩展编辑距离算法以产生对齐，可以先把对齐可视化为编辑距离矩阵中的一条路径。图 2.22 使用粗体单元格展示这条路径。每个粗体单元格表示两个字符串中的一对字母彼此对齐。如果两个粗体单元格位于同一行，从源字符串到目标字符串的过程中就发生了一次插入；同一列中的两个粗体单元格则表示一次删除。

图 2.22 还展示了计算这条对齐路径的直觉。计算分为两步。第一步，扩充最小编辑距离算法，在每个单元格中存储回溯指针（backpointer）。一个单元格的回溯指针指向进入当前单元格时所来自的前一个单元格（或多个单元格）。图 2.22 示意了这些回溯指针。某些单元格包含多个回溯指针，因为取得最小扩展代价的路径可能来自多个先前单元格。第二步，执行回溯（backtrace）。回溯从最后一个单元格（最后一行与最后一列的交点）开始，沿指针反向穿过动态规划矩阵。从最后一个单元格到初始单元格的每一条完整路径，都是一种最小距离对齐。练习 2.10 要求你修改最小编辑距离算法，使其存储这些指针并执行回溯，从而输出一个对齐。

图 2.22 向每个单元格填入数值时，使用最多三个箭头标记我们来自三个相邻单元格中的哪一个。填满表格后，从右下角的 8 开始沿箭头反向回溯，便可计算一个对齐（最小编辑路径）。粗体单元格序列表示两个字符串之间一种可能的最小代价对齐；这里仍采用插入或删除代价为 1、替换代价为 2 的 Levenshtein 距离。图示设计参考 Gusfield（1997）。

尽管示例采用简单的 Levenshtein 距离，图 2.21 中的算法允许为各种操作设置任意权重。例如，在拼写纠错中，键盘上彼此相邻的字母之间更容易发生替换。Viterbi 算法是最小编辑距离的一种概率扩展。它不计算两个字符串之间的“最小编辑距离”，而是计算一个字符串与另一个字符串之间的“最大概率对齐”。第 18 章将进一步讨论这一内容。