C2. Minimum Edit Distance

许多的NLP应用都会关注字符串的相似性这一问题。例如在拼写纠正中，用户输入了错误的单词，我们想要猜测用户的真实意图是什么。另外一个例子是共同指向（coreference），任务需要判断两个字符串是否指向同一实体。

1. 一些定义

Minimum Edit Distance

编辑距离（Edit distance）帮助我们度量两个字符的相似程度。最小编辑距离（minimum edit distance）定义为两个字符串间将一个词转换成另一个单词的最小编辑操作（如插入、删除、替换）的步数。

Alignment

考虑 intention 和 execution 这两个词的最小编辑距离为5。将这两个字符对齐（alignment）就能容易看出是为什么，如图Figure 2.14所示。给定两个字符串，alignment是两个字符串的子串相互关联的过程。比如$I$I与空串对应，$N$N与$E$E对应，等等。在两个字符串的下方是转换所需的编辑操作。

我们考虑为编辑操作添加相应的操作成本（cost）或权重（weight）。在Levenshtein距离的计算里，插入、删除、替换的代价均为1。一个字符替换为其本身的替换代价为0，比如 $t$t 替换为 $t$t ，如此一来 intention 和 execution 的Levenshtein距离就是5。Levenshtein还提出了一种定义方式，将替换操作的代价定义为2，这相当于将替换操作看作是一次插入和一次删除。这样一来， intention 和 execution 的Levenshtein距离就是8。

2. The Minimum Edit Distance Algorithm

如何求最小编辑距离？我们可以将其视为路径搜索问题。搜索解的空间是非常大的，不能简单的进行搜索。由于许多结果的相似的， 我们每当走到某个字符串的最终状态时，可以将其记录下来。可以用动态规划来实现这一目的。动态规划将原始问题分解成为许多子问题的解的组合。

2.1 动态规划-最小编辑距离

给定两个字符串：源（source）字符串$X$X和目标（target）字符串$Y$Y，$X$X字符串长度为$n$n，$Y$Y长度为$m$m，定义$D[i,j]$D[i,j]为字符串$X[1..i]$X[1..i]与$Y[1..j]$Y[1..j] 的编辑距离。

利用动态规划思想自底向上计算$D[i,j]$D[i,j]。考虑源的子串长度为$i$i，目标子串长度为$0$0，源串执行$i$i次删除操作即可变成目标串，$D[i,0]=i$D[i,0]=i。同理，$D[0,j]$D[0,j]反向执行$j$j次插入操作完成。D[i,j]的计算将根据三类操作的最小值确定。D[i,j]的状态转移方程如下：

$D[i, j]=\min \left\{\begin{array}{l}D[i-1, j]+\operatorname{del-cost}(\operatorname{source}[i]) \\D[i, j-1]+\operatorname{ins-cost}(\operatorname{targ} t[j]) \\D[i-1, j-1]+\operatorname{sub-cost}(\operatorname{source}[i], \operatorname{targ} e t[j])\end{array}\right.$D[i,j]=min⎩⎨⎧​D[i−1,j]+del-cost(source[i])D[i,j−1]+ins-cost(targt[j])D[i−1,j−1]+sub-cost(source[i],target[j])​

算法实现如下（伪代码）：

2.2 最小编辑距离算法应用

最小编辑距离算法有助于查找潜在的拼写错误，而在另一方面它有更重要的作用，经过些许修改，算法能够给出字符串间对齐（alignment）的成本大小。字符串对齐在语音和语言处理中是非常重要的。在语音识别领域最小编辑距离对齐用来计算单词错误率（书28章）。对齐还有一个重要作用是在机器翻译领域，因为这里有两个平行语料库（不同语言）需要完成相互的匹配。