从精确匹配到编辑
精确字符串匹配问的是模式在哪里原封不动地出现。另一个问题是把一个字符串变成另一个需要多少工作。先为每个字符串固定一个有限符号序列;处理文字时,算法执行前须约定符号表示,因为字节、Unicode 码点和显示字符未必相同。
定义 6.2.1
(编辑距离)
设 与 是有限符号序列。编辑序列以有限多次操作把 变成 ,每次操作插入、删除或替换一个符号,成本各为一;保留符号不变的成本为零。编辑距离 是这种编辑序列的最小总成本。空编辑序列的成本为零;此模型不把相邻符号对调视为一次操作。
对齐与递推式
定义 6.2.2
(对齐及其成本)
和 的对齐把两者的符号排成两行,并保留每行的原有顺序。一列可以配对两个符号,或把一个符号与空位配对;一列不能有两个空位。相同符号配对成本为零,不同符号配对及单空位列各成本一。对齐的成本是各列成本之和。
例如 和 的一种对齐为
成本为二:把 替换成 ,再插入 。
为什么最小对齐成本应该等于编辑距离?下面的结果说明确实如此,其证明也显示了两种描述如何互相转换。
定理 6.2.3
(对齐成本等于编辑距离)
对任意有限序列 与 , 与 的最小对齐成本等于编辑距离 。
证明
(从对齐到操作序列,再从操作序列回到对齐)
对齐可给出同成本的操作序列:从左至右扫描,保留或替换成对符号,删去与空位配对的上行符号,插入与空位配对的下行符号。因此最小对齐成本至少是 。
反过来,沿任意编辑序列追踪符号身份:替换保留身份,删除终止身份,插入则建立新身份。最后仍存在的原符号保持原有顺序,因为允许的操作均不交换符号。把每个这样的原符号与其最终后裔配对;每个被删原符号及每个最终插入符号则与空位配对。在相邻存活配对之间、首对之前及末对之后(若没有存活配对则处理整个序列),按原有顺序列出被删原符号,按最终顺序列出插入符号;把两列依次放置仍保留各行顺序。
每对不同的存活符号至少需要一次替换,每个被删原符号至少需要一次删除,每个最终插入符号至少需要一次插入。这些所需操作互不相同,故对齐成本不大于该操作序列成本。此论证也允许多做一些随后被抵消的操作;它们不能使操作序列比对齐更便宜。两个最小值因而相等。
定义 6.2.4
(对齐成本的前缀表)
记 、。对 、,令 为 前 个符号与 前 个符号的最小对齐成本。当 ,若 令 ,否则令 。
定理 6.2.5
(编辑距离的前缀递推式)
沿用上述记号,有 、,而当 时
因此 。
证明
(移去与附加最后一列)
边界:若其中一个前缀为空,另一个前缀的每个符号都必须与空位配对,每列成本为一。故 、。
设 。上界:对三个候选值中的每一个,取较小前缀的一个最优对齐,并附加相应的末列,即 对空位、空位对 ,或 对 。每个结果都是较长前缀的一个对齐,成本等于该候选值,所以 不大于三者的最小值。
下界:取两个前缀的一个最优对齐。因为不允许两个空位,其末列恰为三种形式之一。移去末列后,余下是相应较短前缀的一个对齐,成本至少为对应表格项,而被移去的一列成本分别为 、 或 。所以 至少等于该形式对应的候选值,因而至少等于最小值。对 做归纳,把同一论证用于较小的表格项,边界值提供起点。最后由上一个定理得 。
证明透视
为何只看最后一列就足够
关键一步是只看最优对齐的最后一列。末列恰有三种形式,因为含两个空位的列是被禁止的;这是用到对齐定义的地方。移去这一列后余下的是较短前缀的对齐,而成本对各列可加,所以没有损失信息;正是这种可加性让前缀成本表可以取代对所有对齐的搜索。
论证以 归纳完成,因为每个候选值都指向下标和更小的表格项。上界用的是最优子对齐,下界用的是整体最优对齐;两个方向缺一不可。若成本依赖相邻的列,例如较长空位的起始成本较低,移去一列便不再留下独立的子问题,这个递推式也就不成立。
同一张表还有第二种等价的描述,即最短路径的计算。
概念视角组合
对齐就是格点上的路径
把各项 放在格点上。由 到 的向下一步,是把 与空位配对的一列;向右一步是空位对 ;对角一步把 与 配对,成本为 。 与 的对齐恰好对应从 到 的单调路径,对齐成本就是路径长度。于是递推式就是这个无环格点图上常见的最短路径方程, 是 到 的最短距离。
表格与见证
例题 6.2.6
(CAT 与 CUTS 的表格)
对 、,先填空前缀边界,再逐行由左至右填表:
| 前缀 / 前缀 | 空 | C | CU | CUT | CUTS |
|---|---|---|---|---|---|
| 空 | 0 | 1 | 2 | 3 | 4 |
| C | 1 | 0 | 1 | 2 | 3 |
| CA | 2 | 1 | 1 | 2 | 3 |
| CAT | 3 | 2 | 2 | 1 | 2 |
例如, 对 的表格项是 ,其中对角候选值加上 ,因为 。 对 的表格项是 ,因为 使对角一步免费。右下角的值证明两次编辑已是最优;前面给出的对齐提供相符的见证。
一般而言,要重构最优解,从 开始,每步选择任一达到递推式最小值的前驱并记录对齐列。对角步记录匹配或替换,向上步记录删除,向左步记录插入。在 时继续向左,在 时继续向上,直至 ,然后把所记列的顺序反转。并列可能产生不同的最优对齐;若实现需要确定输出,必须指定并列处理规则。反向读取后若不再反转,列的顺序便会错误。
定理 6.2.7
(回溯给出最优对齐)
从 出发,每步移到一个达到递推式最小值的前驱(当 或 时沿边界移动),并记录各列。把所记录的列反转,便得到 与 的一个成本为 的对齐,因此它是最优的。
证明
(每一步剥去最优前缀对齐的一列)
断言:从格点 回溯到 所记录的各列,反转后构成前 个与前 个符号的一个对齐,成本为 。对 归纳。在 处对齐为空,成本为 。在边界 上只能向上走,每列删除一个符号,成本为 ; 的情形对称。
否则所选前驱 满足 ,其中 是这一步所记录那一列的成本。由归纳假设,从 回溯所得各列反转后构成成本为 的对齐;附加所记录的一列,便得到较长前缀的对齐,成本为 。在 处这就是 与 的一个最优对齐。
例题 6.2.8
(倒着读 CAT 与 CUTS 的表格)
从值为 的 开始。对角前驱给出 ,向上的前驱给出 ,向左的前驱给出 ,所以记录插入 。在 ,对角前驱给出 ,达到该值,所以记录匹配 。在 ,对角给出 ,另外两个给出 ,所以记录替换 。在 ,对角给出 ,所以记录匹配 ,到达 。
把所记录的列反转,得到 、、、,就是前面给出的对齐。这里每一步都没有并列,所以这是唯一的最优对齐。
例题 6.2.9
(并列与边界情形:AB 对 BA)
对 、,表格为
| 前缀 / 前缀 | 空 | B | BA |
|---|---|---|---|
| 空 | 0 | 1 | 2 |
| A | 1 | 1 | 1 |
| AB | 2 | 1 | 2 |
在角落 ,三个候选值都等于二:向上给出 ,向左给出 ,对角给出 。每种选择都通向一个最优对齐:两次替换 、;或各列 、、;或各列 、、。它们的成本都是二。特别地,对调 在此模型中成本为二,而表格显示不存在只用一次操作的序列,因为 。
下面的交互图逐格填表,列出每格的三个候选值及达到最小值的前驱,并按所选并列规则回溯读出最优对齐。
成本、内存与模型选择
共有 个表格项,每项用常数时间计算,故完整表格的时间和空间成本均为 。若只需要距离,递推式只需保留上一行和当前行,工作空间可降至 ;保留完整表格则支持上述简单回溯。用更少内存恢复对齐需要额外工作,不能丢弃所有旧行后仍按原方法回溯。
改变操作成本会改变递推式,也可能改变其数学性质。特别是上述模型不包含一次相邻对调: 到 的距离在此模型为二,虽然另设对调操作时可花一。动态规划返回最小编辑成本,并非判断两个句子语义是否相同。
反例模式
只有插入与删除会得到另一种距离
一个看似合理的说法是 ,其中 LCS 是最长公共子序列的长度。对 、,最长公共子序列是 ,长度为二,因为 不在 中出现。公式给出 ,但表格给出 ,见证是把 替换成 再插入 。该公式是只允许插入与删除的模型中的距离,在那个模型里替换必须用一次删除加一次插入来模拟,成本为二。允许单位成本的替换时,必须使用上面的递推式。
常见错误
常见错误
(把空前缀边界初始化为零)
设 等于说把空字符串变成长度为 的字符串不需要成本。对 、,被破坏的表格给出 ,可是 ,真实距离是一(插入 )。边界 记录的是 的 个符号都必须被插入。
常见错误
(对角步比较了错误的符号)
处的对角候选值使用 ,它比较的是 与 ,即两个前缀的最后一个符号。若实现从零开始编号,在按前缀长度编号的表格中却比较 与 ,就差了一位。对 与 的 ,它会比较 与 ,得到 ,而正确值是 。
练习
快速检查
(计算 到 的距离,并给出一个最优操作序列。)
先比较两个字符串的长度。
解答 · 答案
距离是一。删除最后的符号 的操作序列,以成本一把 变成 。因为两个字符串不同,不存在成本为零的序列,所以一是最优的。
快速检查
(解释为何空前缀边界必须是 。若初始化为零会出什么问题?)
想一想 的空前缀能与什么配对。
解答 · 答案
空前缀没有符号可与 的前 个符号配对,所以它们每个都与空位配对,每列成本为一;故 。若初始化为零,表格就声称在空字符串中插入符号不需成本。对 、,它会给出 ,但两个字符串不同,真实距离是一。
快速检查
(假设两个转移候选值在 并列最小。对这两种末列选择,是否各有一个相应前缀的最优对齐?解释为何不在任何由 出发的最优回溯上的表格项,即使有并列,也未必给出完整字符串的两个最优对齐。)
第二部分可试 与 中 对 的表格项。
解答 · 答案
是。若某个候选值达到最小值,则在较小前缀的最优对齐后附加相应末列,便得到成本为 的对齐,因而是最优的,并且以该列结尾。所以两种结尾都存在。
表格项上的并列并不表示该项属于完整字符串的最优对齐。在 与 的表格中, 的值为二,既可由上方()也可由对角()达到。两者都给出 对 的最优对齐。但要把任一个补成 ,仍须插入 与 ,总成本至少为 ,大于 。这个表格项不在任何由 出发的最优回溯上。