问题
一次编辑会让单词改变一个字母:插入一个字母、删除一个字母,或把一个字母替换成另一个。两个单词之间的编辑距离,就是把一个变成另一个所需的最少编辑次数。cat 和 cut 相差 1,cat 和 cast 相差 1,cat 和 act 相差 2。它也叫莱文斯坦距离,以苏联数学家弗拉基米尔·莱文斯坦命名,他在 1965 年研究了这一距离。
表格
设 d[i][j] 为一个单词的前 i 个字母与另一个单词的前 j 个字母之间的编辑距离。把一个单词变成空,每个字母需要删除一次,所以 d[i][0] = i;从空开始构造一个单词,每个字母需要插入一次,所以 d[0][j] = j。如果第 i 个字母等于第 j 个字母,则 d[i][j] = d[i − 1][j − 1]。否则 d[i][j] = 1 + d[i − 1][j − 1](替换)、d[i − 1][j](删除)和 d[i][j − 1](插入)中的最小值。
一个例子
对于 kitten 和 sitting,表格有 7 行 8 列。右下角的单元格是 3,从它回溯得到:把 k 替换为 s,保留 i、t 和 t,把 e 替换为 i,保留 n,再插入 g。Kitten、sitten、sittin、sitting:三次编辑,而表格证明不存在更短的编辑列表。
回溯编辑操作
从右下角的单元格开始,问它的值来自哪个相邻单元格。如果两个字母相同,且该单元格等于左上方的相邻单元格,说明字母被保留:沿对角线移动。如果它比左上方的单元格大一,就是替换;比上方的单元格大一,就是删除;比左方的单元格大一,就是插入。可能有几条路径并列,每一条都给出一份最短的编辑列表。
历史与应用
莱文斯坦在 1965 年研究纠错码时提出了这一距离。表格方法由多人发表,其中最著名的是罗伯特·瓦格纳(Robert Wagner)和迈克尔·费舍尔(Michael Fischer)在 1974 年发表的工作,因此它常被称为 Wagner–Fischer 算法。如今,编辑距离被用来给拼写建议排序、在数据库中匹配带错别字的名字、比较 DNA 和蛋白质序列,以及给语音识别打分。
动手试试
打开应用,按“单步”。正在比较的两个字母会在表头中高亮;字母相同时复制左上方的蓝色单元格,字母不同时读取三个蓝色相邻单元格,并在最小值上加一。最后,橙色路径从角落往回延伸,编辑操作显示在表格下方。
常见问题
编辑距离是一种度量吗?
是的。它永远不为负,只有两个单词相同时才为 0,两个方向的结果相同,而且绕经第三个单词永远不会让它变短:d(a, c) ≤ d(a, b) + d(b, c)。这使它很适合用来搜索相近的匹配。
什么是 Damerau–Levenshtein 距离?
多了一种编辑操作的编辑距离:交换两个相邻字母。弗雷德里克·达默劳(Frederick Damerau)在 1964 年发现,插入、删除、替换和交换加起来覆盖了 80% 以上的拼写错误。允许交换时,recieve 和 receive 相差 1 而不是 2。
编辑距离能比 O(m·n) 算得更快吗?
快不了多少。2015 年,Arturs Backurs 和 Piotr Indyk 证明:如果存在对某个 ε > 0 只需 O(n^(2 − ε)) 时间的方法,就会推翻强指数时间假设,而大多数研究者相信这一假设成立。不过,对于很接近的单词,只需计算表格对角线附近的一条窄带。
编辑距离在 DNA 比对中怎样使用?
生物学家使用同样的表格,只是用得分代替次数:匹配得分,替换和空位则按字母扣分。用于整条序列的是 1970 年的 Needleman–Wunsch 算法,用于寻找最佳匹配片段的是 1981 年的 Smith–Waterman 算法。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
试试编辑距离