动机
两个字符串之所以不同,可能是因为某个字符被插入、删除或替换。仅统计不匹配的位置是不够的:在开头附近插入一个字符会使其后所有位置发生移位,但可能只需要一次编辑。编辑距离所问的是:把一个字符串变成另一个字符串,所需允许操作的最少次数是多少。凡是需要基于这些操作作精确比较的场合,它都很有用,但其数值取决于我们所选择的代价模型。
动态规划作用于成对的前缀。其核心思想是对一个对齐的最后一列进行分类,从而把整体的最优变换与较小的前缀问题联系起来。这张表既是计算距离的工具,也是可以据以还原最优变换的记录。
定义
定义 2.10.1
(编辑操作与对齐)
设 与 是同一字母表上的有限字符串。允许的操作为:插入一个字符、删除一个字符,或把一个字符替换为另一个不同的字符;每次操作代价为一。所有中间字符串均被允许。记 为把 变换为 的最小代价。空前缀的长度为零。
一个对齐(alignment)把两个字符串的字符按原有顺序放入若干列中,允许任一行出现空位(gap),但同一列的两行不得同时为空位。两个相同字符所在的列代价为零,两个不同字符所在的列代价为一,含一个空位的列代价为一。对齐的代价是各列代价之和。
定理
定理 2.10.2
(编辑序列与对齐)
对任意两个有限字符串,单位代价的插入、删除与替换的最少次数,等于这两个字符串的对齐的最小代价。
定理 2.10.3
(前缀递推式)
边界值为 与 。对 ,
其中方括号在两个字符不同时取一,否则取零。按行、列递增的顺序填表,可在字符比较为常数时间的前提下,以 的时间与空间计算出 。
证明
证明:为什么对齐能刻画编辑
证明
(编辑序列与对齐相对应)
由一个对齐可得到代价相同的编辑序列。从左到右扫描它的各列。若某列两行字符相同,则保持该字符不变。若两行字符不同,则把上行字符替换为下行字符;若其下行为空位,则删除上行字符;若其上行为空位,则插入下行字符。列的顺序保证了这些操作可以从左到右依次施行,同时保持尚未处理的后缀不变。因此最小编辑代价不超过最小对齐代价。
反方向:考察任意一个编辑序列,并把当前字符串中的每个字符追溯回它原来的字符(如果有的话)。被插入的字符没有原始祖先;替换保留字符的祖先关系,删除则移除该字符。这些操作从不改变仍存活的祖先之间的顺序。在最终字符串中,把每个存活的原始祖先与其最终后代对齐。把被删除的原始字符与空位对齐,把最终字符串中被插入的字符也与空位对齐。这些未配对的字符,按其在原字符串与最终字符串中的顺序,放置在相邻的已配对祖先之间。
每个与不同的最终后代对齐的原始字符,至少被替换过一次。每个被删除的原始字符必然被删除过,而最终字符串中没有原始祖先的每个字符必然被插入过。这些是互不相同的操作计费;先被插入、随后又被删除的中间字符,以及重复的替换,只会增加该序列的代价。所以所得对齐的代价不超过该编辑序列的代价。取最小值即证得相等。这一祖先论证允许任意的中间编辑;它并不预先假定最优序列具有某个便于处理的最后一步操作。
证明:前缀递推式
证明
(由最后一列得到前缀递推式)
若目标为空,则源字符串的每个字符都必须被删除;若源为空,则目标的每个字符都必须被插入。这就证明了边界值。现在考虑两个非空前缀的一个最小代价对齐。它的最后一列恰为三种类型之一: 在空位之上,空位在 之上,或 在 之上。去掉这一列,剩下的是相应较小前缀的一个对齐。其代价等于该列的代价加上不小于这些前缀最优值的量。由此得到所示最小值的一个下界。
反过来,把三种可能的最后一列分别接到相应较小前缀的最优对齐之后。所得对齐是合法的,并且达到相应候选值的代价。因此最小的候选值是可以达到的,从而证得相等。由对齐定理,它也是最少的编辑次数。
每个表项只依赖于其上方的表项、左方的表项以及左上对角的表项。从已初始化的第一行与第一列出发逐行填表,三者都已就绪。共有 个表项,在所述模型下每项只需常数工作量,由此得到时间与空间的界。若只需要距离,则只保留上一行以及当前行中已填好的部分,只用 空间;交换两个字符串的角色可得 空间。仅靠这种节省空间的计算,并不保留可供回溯的完整表。
证明透视
对齐的最后一列
这三种情形穷尽且互斥:删除源的最后一个字符、插入目标的最后一个字符,或把两个最后字符对齐。字符相同的情形代价为零;不同的情形则是替换。该证明比较的是完整的对齐,而不是去猜测任意一个编辑脚本中字面上最后发生的是哪一次编辑。
例题详解
例题 2.10.4
(移位的后缀)
通过在 a 与 t 之间插入 r,可把 cat 变为 cart。一个对齐是
其代价为一。两个字符串不同,所以零次编辑不可能做到。它们的距离恰为一,尽管末尾的 t 的位置发生了移动。
例题 2.10.5
(一张完整的小表)
对于源 ab 与目标 ac,前缀距离表为
右下角的表项为一:把两个 a 对齐,并把 b 替换为 c。在该单元格处,对角候选值为 ,而删除与插入的候选值都是二。
例题 2.10.6
(多个最优脚本)
对于 ab 与 ba,两次替换的代价为二。删除第一个 a 并在末尾插入一个 a,代价同样为二。一次操作无法得到目标:一次替换只改变一个位置,而一次插入或删除会改变长度。最优值为二,回溯时遇到并列的情形,可能返回不同的最优对齐。
例题 2.10.7
(空字符串)
从空字符串到 dog 的距离为三:插入它的三个字符。没有任何一次操作能插入多于一个字符,所以少于三次不可能做到。表的第一行对每个目标前缀记录的正是这一推理。
还原编辑序列
从 出发。在每个非边界单元格处,选择一个达到递推式最小值的前驱:向上对应删除,向左对应插入,沿对角线对应匹配或替换。在边界上,则只沿该边界取唯一可能的移动。每一步移动都使 减小,所以该过程至多经 步后在 处停止。
回溯的各步移动按相反顺序描述对齐的各列。把所记录的列表反转,然后像第一个证明那样从左到右扫描其各列以施行操作。并列时可任意选择:与表项相等这一条件保证所记录各列代价之和等于 。若按回溯的相反顺序直接写出操作而不调整下标,可能得到错误的脚本,因此对齐是一种稳定的中间表示。
例如,从 ab 对 ac 一表的右下角表项出发,一次对角移动记录替换 ,下一次对角移动记录匹配 。把所记录的列反转,先得到匹配,再得到替换。由此得到的编辑脚本只改变第二个字符一次。
概念视角结构
把表看成最短路径问题
取顶点为 (、)的网格图。边 与 的代价为一,边 的代价为 。于是 就是从 到 的路径最小代价,而从 到 的每条路径逐步对应一个对齐的各列。最优对齐恰好就是最短路径,回溯则是沿一条最短路径反向走回去。
常见错误
反例模式
汉明(Hamming)距离不等于编辑距离
等长字符串 abc 与 bca 在三个位置上都不相同,但删除第一个 a 并把它插入到末尾,只需两次编辑。逐位置的不匹配计数可能高估编辑距离,因为删除与插入会改变对齐方式。
常见错误
(把单位代价的表用于另一种代价模型)
递推式取决于所允许的操作及其代价。若替换的代价是二而不是一,对角线候选在字符不同时就必须加二。否则 a 到 b 会得到距离一,但此时最便宜的脚本是一次删除加一次插入,代价为二。若转置也算单一操作,则需要另一个递推式及证明。为某一模型算出的表,不应不加说明地被当作另一模型的距离。
常见错误
(把距离当作编辑脚本)
距离本身也不等同于某个具体的编辑脚本。若要输出脚本,必须保留足够的前驱信息,或用另行证明的方法重新计算。滚动行能为数值答案节省内存,却丢弃了上述简单回溯过程所用的完整表。
距离的性质及其局限
单位代价的距离是对称的:把编辑序列反转,将每次插入换成相应的删除,每次删除换成相应的插入,并把每次替换换成其逆替换。这就构造出方向相反、代价相同的序列。对两个方向都应用这一论证,即证得 。
它还满足三角不等式。把从 到 的一个最优编辑序列与从 到 的一个最优编辑序列连接起来,就得到从 到 的一个合法(但不一定最优)的序列,所以 。距离非负,并且当且仅当两个字符串相等时为零。综合这些事实,单位代价的编辑距离是有限字符串上的一个度量。
连接而成的脚本可能含有相互抵消的编辑。例如,把 a 变为 ab 再变回 a,总代价为二,而直接把 a 变为自身的代价为零。因此三角不等式只是一个不等式,并不断言经由某个选定的中间字符串总是最优的。
选择表的方向
在这一对称的模型中,行与列可以互换。若其中一个字符串短得多,在节省空间的计算中就用它作为所存储的那一行。例如,比较一个一千字符的字符串与一个十字符的字符串,时间仍与它们长度之积成正比,但行缓冲区只需十一个表项。算术模型假定表项与下标满足所述的常数时间运算;表示特别长的字符串时,可能需要另作比特代价分析。
节省空间与还原脚本是两个不同的设计目标。完整的表使我们在每一步都容易沿着前驱走,并验证它与所存值相等。滚动行的实现应当只承诺给出距离,除非它同时实现并证明了某种还原方法。这一区分可以避免把针对数值答案的复杂度结论,不加说明地套用到对所选编辑的完整说明上。
总结
对齐的各列是联系任意编辑脚本与前缀递推式的桥梁。三种可能的最后一列分别给出删除、插入以及匹配或替换的候选值。填完的表给出最优值,而前驱的选择则可还原一个最优对齐及编辑序列。
练习
快速检查
(计算从 a 到 b 的编辑距离,并说明理由。)
解答 · 答案
把 a 替换为 b,代价为一。两个字符串不同,所以零次操作不可能做到;距离为一。
快速检查
(计算从 ab 到 a 的编辑距离,并给出一个最优脚本。)
解答 · 答案
删除末尾的 b,代价为一。由于输入与输出的长度不同,至少需要一次操作。
练习 2.10.8
(给出 abc 与 bca 的一个代价为二的对齐。为什么距离不是一?)
基础
解答(3)
- 1
给出代价为二的对齐
把
a与空位对齐,接着b对b、c对c,最后空位对末尾的a。代价为 。依据: 两个相同字符的列代价为零,含空位的列代价各为一。
- 2
排除单次编辑
关键一步
单次编辑是一次替换、插入或删除。替换只改变一个位置,但两个字符串在三个位置都不同;插入或删除会改变长度,但两个字符串的长度都是三。
- 3
得出距离为二
零次编辑会迫使两串相等,而一次编辑不可能,所以距离至少为二。上面的对齐显示距离至多为二。因此距离恰为二,尤其不是一。
快速检查
(对于 aa 与 a,列出两个不同的单次编辑脚本,并说明回溯时并列情形是如何产生的。)
解答 · 答案
删除第一个或第二个 a。两者都得到 a,代价为一。在相关的表单元格处,不同的最小代价前驱路径把目标的 a 与源中不同位置的 a 对齐。重复的字符使这些对齐互不相同,尽管所得到的字符串相同。