编辑距离

编辑距离介绍

利用编辑距离可以判断两个字符串的相似程度，即从一个字符串到另一个字符串所需要的编辑次数，包括插入字符，删除字符及替换字符这三种操作。 最小编辑距离即从一个字符串到另一个字符串所需要的最小编辑次数。

图2-1所示将两个字符串进行排列比对，上面的字符串INTENTION进行一系列操作可以变为下面的字符串EXECUTION,  d代表删除字符操作，s代表替换字符操作，i代表插入字符操作。

最小编辑距离算法

那么如何找到最小编辑距离呢？ 可以看作是一种操作路径的搜索，从一个字符串转变为另一个字符串的最短搜索路径。 图3-1描述了intention字符串经过三种不同的操作路径，转变为三个不同的字符串。

最小编辑距离算法总结如图3-5，图3-6列出了intention和execution字符串跟根据图3-5计算方法，算法的详细计算结果。

图3-6 intention和execution字符串最小编辑距离计算示例

编辑距离除了被大家所熟知的应用如拼写纠错，编辑距离在另外的方面还有重要作用，如两个字符串比对的最小代价计算。 字符串比对在语音识别和语言处理领域有着广泛的应用，在语音识别领域最小编辑距离比对通常用来计算错词率。 比对在机器翻译领域也扮演了重要的角色，在一个句子中每个词在两种语言中会有不同的词来表示，它们需要相互比对。

为了使编辑距离算法能够处理字符串比对，我们通过编辑距离矩阵标出一个比对路径，图3-7采用粗体蓝色单元格表示出这样一条路径。 每个单元格代表两个字符串中的一对字符的比对结果，如果粗体单元格出现在同一行的相邻位置，那么从原字符串到目标字符串发生了一次插入操作； 粗体单元格出现在同一列的相邻位置，那么从原字符串到目标字符串发生了一次删除操作。

图3-7同时也提供了一种计算比对路径的思路，第一步采用最小编辑距离算法对每个单元格计算并存储一个回溯指针，即到达这个单元格的前一单元格的位置。 图3-7有些单元格有多个回溯指针，代表有多种路径到达该单元格。 第二步开始回溯，从最后一个单元格开始（即最大行和最大列的单元格），跟随回溯指针的方向回溯该矩阵，从最后单元格开始到第一个单元格的每一条完整路径都代表一个最小比对距离。

本文是对编辑距离及最小编辑距离算法及其应用的简单介绍，主要内容参考《 Speech and Language Processing (3rd ed. draft) 》 第二章部分章节进行翻译，大部分图片均来源于该书，疏漏和错误之处，望批评指正。

-end-