动机
两个字符串即使其符号并不相邻,也可能共享一个有序的模式。只要符号的相对顺序重要而允许有间隔,寻找最长的这种模式就有实际用途。直接搜索所有子序列,会多次重复求解相同的前缀问题。动态规划为每一对前缀记录最优答案,再利用这些答案构造一个最优子序列。
子序列不同于子串:允许删除符号,但不要求保留下来的符号在原字符串中保持连续。保留下来的符号的顺序则必须保持不变。本文计算的是长度以及一个见证;求出所有见证则是另一个输出问题。
定义
定义 2.1.1
(子序列与前缀表)
设 与 为有限字符串。若字符串 可以通过从 中删除零个或多个位置、且不改变其余位置的顺序而得到,则称 是 的子序列。允许出现重复符号,但同一个被选取的位置不能使用两次。公共子序列是同时为两个字符串的子序列的字符串。空字符串总是公共子序列,即使其中一个输入为空亦然。
对于 与 ,将 定义为前缀 与 的公共子序列的最大长度。空前缀给出 。状态同时记录两个前缀的长度,是因为去掉其中一个字符串的最后一个字符,只改变两个约束中的一个。
定理
定理 2.1.2
(前缀递推式)
对于 ,
表中的值 是最长公共子序列的长度。
定理 2.1.3
(计算与重构)
按照上方、左方与左上方对角前驱项均已知的顺序填表,需要 的时间与空间(当两个长度均为正时即为 )。从 出发:若最后一个符号相同,则沿对角线移动并记录该符号;否则移向表值较大的前驱,若相等则任意选取。将记录下来的符号反转,即得一个最长公共子序列。
证明思路或证明
证明
(前缀递推式与重构)
若 ,将 附加到两个较短前缀的任意一个最优公共子序列之后,便得到长度为 的公共子序列。反过来,取较长前缀的任意一个最优公共子序列。若它使用了其中任何一个最后位置,则其最后一个符号为 ;另一个字符串中与之匹配的出现可以移到该字符串的最后位置,而在它之前留下的是两个较短前缀的一个公共子序列。若它两个最后位置都没有使用,则附加 将产生更长的公共子序列,与最优性矛盾。因此存在一个使用两个最后位置的最优表示,去掉其最后一个符号,便得到较短前缀的一个公共子序列。这两个不等式证明了符号相同的情形。
若 ,则没有任何公共子序列能把两个最后位置作为一对匹配位置同时使用。因此每个公共子序列至少避开其中一个最后位置:若它在各自匹配的位置上同时使用了两者,则其相对顺序会迫使两个字符串中最后被选取的符号相等。于是它属于两个较小前缀子问题中至少一个。反过来,任一较小前缀对的公共子序列,也是原来两个前缀的公共子序列。取最大值即证明了符号不同的情形。
对 作归纳,边界值与递推式可正确计算表中的每一项。在重构过程中,符号相同情形下的对角移动从一个最优见证中去掉一个符号,而符号不同情形下的移动则保持最优长度不变。每一步移动都使至少一个下标减小,因此过程会在边界处终止。符号是从右向左被发现的,必须反转。反转之后,它们所记录的位置是递增的,因此构成一个长度等于所宣称最优值的公共子序列。
证明透视
一个有效的见证与一个上界
附加一个匹配的符号只提供了一个候选解,其本身并不能证明最优性。逆向论证必须说明:存在一个使用两个最后位置的最优表示,因此它的前缀不可能超过较短前缀的最优值。
符号不同的情形以另一种方式收尾。使用 最后位置的公共子序列必以 结尾,使用 最后位置的公共子序列必以 结尾。两者同时使用就会迫使 ,所以假设 将其排除,每个公共子序列都已属于两个较小问题之一。
例题详解
例题 2.1.4
(允许有间隔)
对于 与 ,字符串 是公共子序列:从第一个输入中删除 ,而第二个输入不删除任何符号。任何公共子序列的长度都不可能超过第二个输入的长度,所以最优长度为二。同一个见证并不是 的子串。
例题 2.1.5
(平局产生不同的见证)
对于 与 , 与 都是长度为一的公共子序列。长度为二的公共子序列必须同时等于两个输入字符串,而这不可能。在最后这对不相同的符号处,两个前驱项相等;任一选择都能重构出一个最优解,但所选的见证可能不同。
例题 2.1.6
(重复符号使用的是位置)
对于 与 , 与 都是长度为二的公共子序列。两个完整字符串并不相同,所以不存在长度为三的公共子序列。 的一个有效见证使用 的前两个位置以及 的第一和第三个位置;它没有重复使用同一个出现。
常见错误
反例模式
共同子串是另一个问题
对于 与 ,最长公共子序列的长度为二,但不存在长度为二的公共子串。把子序列递推式换成子串递推式,会在不知不觉中改变问题。
常见错误
(把长度表当作答案)
长度表本身并不会显示见证。若题目要求给出一个子序列,就必须沿表追踪并记录各步选择。若题目要求给出所有最长子序列,则任意打破平局并不足够。表中不同的路径也可能拼出同一个子序列,在符号重复时尤其如此。
填表与读表
将第零行与第零列初始化为零。然后依次处理行 ,并在每一行内依次处理列 。需要用到上方、左方以及左上方对角的项时,它们都已可用。这一顺序是依赖图的一个有效拓扑序;先列后行的顺序同样可行。表中的格子代表的是前缀长度,而不单是字符下标,所以尽管不存在字符 ,第零行仍是真正的边界。
例题 2.1.7
(一个小表及其追踪)
取 与 。包括空前缀在内,表的各行为
在最后一格,两个符号都是 ,所以记录 并沿对角线移动到对应 与 的格子。在那里符号 相同,所以记录 并沿对角线移动到边界。将记录下来的序列 反转,得到 ,这是一个长度为二的公共子序列。该表证明了不存在更长的公共子序列。
填好的表也是一种诊断工具。每一项都介于零与较短前缀的长度之间。当任一前缀被延长时,值不会减小,因为之前所有的公共子序列仍然可用。若某个实现在增加一个字符之后产生了更小的值,就违反了这种单调性。这些检查能够暴露错误,但不能代替对递推式的证明:一个错误的表也可能同时满足这两个界和单调性。
为什么符号相同的情形是安全的
常见错误
(以为每个最优解都使用两个最后位置)
有时人们过于草率地为符号相同时的递推式辩护,说每个最优解都必然已经使用了两个最后位置。当符号重复时,以位置序列形式给出的最优解不一定如此。例如,对于 与 , 的第一个 可以用于一个最优匹配,而最后一个 则未被使用。证明所需要的是较弱的结论:存在一个使用两个最后位置的最优表示。把已匹配的最后一个出现移到较后的相同出现上,可以保持此前所有的顺序关系。
字符串与其位置见证之间的这种区别在重构时很重要。不同的匹配位置集合可以产生同一个符号序列。若目标是得到一个公共子序列,任何有效的匹配位置都足够。若目标是统计不同字符串的数目,对路径数求和一般是错误的,因为多条路径可能拼出同一个字符串。若目标是统计位置匹配的数目,那是另一个需要明确说明的计数问题。
符号不同情形的证明同样使用位置,而不仅仅是字符是否出现。一个符号可以在两个字符串中多次出现,但在一个字符串中最后被选取的位置,必须与另一个字符串中最后被选取的位置相匹配。若某个公共子序列同时使用两个最后位置,则这两个位置代表的是同一个最后被选取的符号。由于最后的符号不同,这不可能发生。因此至少有一个最后位置未被使用,可以将其去掉而不失去该见证。
概念视角组合
最长公共子序列即插入删除距离
只用插入和删除把 变成 。 中从未被删去的符号构成 与 的一个公共子序列;反过来,每个公共子序列 都给出这样的一个步骤:删去 的其余 个符号,再插入 的其余 个符号。因此最少的操作次数是 。对 和 ,这是 。
空间与输出的选择
完整的表为每一对前缀使用一个格子。若只需要最优长度,则每一行只依赖于上一行及其自身前一个格子,所以两行就足够。当行对应 的前缀时,这将存储量降为 个格子;交换两个字符串,可以让较短的维度成为被存储的行。边界行必须正确初始化,并且必须保留当前行的左侧值。时间界仍与格子数成正比。
仅用两行的计算本身并不会保存简单的向后追踪所需的全部前驱选择。因此,若不说明如何恢复缺失的信息,就不能同时承诺做到这种精确追踪与两行存储。可以保留完整的表、重新计算部分内容,或者使用另行证明过的分治重构。第一种方案就是这里所证明的算法。见证的输出也需要存储空间:一个最长公共子序列最多可含 个符号。
所述的时间统计的是表的运算次数,并假设符号相等性可以在常数时间内检验。若输入符号本身是庞大的结构,则必须计入它们的比较成本。该方法适用于任何具有明确相等性检验的有限序列;字母表不必很小。它也通过已初始化的边界直接处理空输入,在不进入重构循环的情况下给出空见证。
一个策略检验
反例模式
匹配最早出现的位置并不最优
有一种诱人的贪心规则:只要可能,就把第一个字符串的每个符号匹配到它在第二个字符串中最早的可能出现。对于 与 ,把开头的 匹配到 的最后位置,会使 与 都没有余地,所以该规则只得到长度一。跳过 则可得到长度为二的 。局部的匹配可能耗用一个位置,从而阻碍更好的后续模式;动态规划比较的是较小前缀对上的各种选择,而不假设第一个可用的匹配是安全的。
这个反例针对的是所述的贪心规则,而不是每一种使用最早出现位置数据结构的算法。数据结构可以加速一个正确的算法,但并不决定其目标。若要一般性地论证某个贪心规则,就需要证明对每个输入,其选择都可以成为某个最优解的一部分。一个反例即可推翻这一全称断言,而递推式的证明则确立了对每一对有限输入的正确性。
总结
前缀对给出一个有限的状态空间。最后的符号相同时,两个前缀都缩短;最后的符号不同时,最优解必须避开至少其中一个。由此得到的表计算出最优长度,而向后追踪可以恢复一个见证。
练习
快速检查
(求 与 的一个最长公共子序列,并论证其长度。)
解答 · 答案
与 都是长度为二的公共子序列。长度为三要求两个完整字符串相等,所以二是最优的。
快速检查
(若 为空而 的长度为五,边界值是什么?)
解答 · 答案
对 ,每一项 都是零:空输入的唯一子序列是空字符串。
快速检查
(对于 与 ,为什么答案不是二?)
解答 · 答案
第二个输入只有一个位置,所以它的任何子序列的长度至多为一。符号 是长度为一的公共子序列。
快速检查
(对于 与 ,给出最优长度及一个见证。)
解答 · 答案
这两个字符串没有公共符号。最大长度为零,空字符串是一个见证。