最优长度与实际序列是不同输出
对 ABC 与 AC,若允许跳过符号,AC 在两者都出现;它在 ABC 不必占相邻位置。目标是最长公共子序列,不是最长公共连续子串。这个区别决定递推有哪些合法选择。
优化内存时还有另一区别:一行数值能算最优长度,却没有保留完整表格的回溯数据。我们先证明表格法,再推导刻意重算指定行的重建方法。
前缀让状态定义精确
定义 8.1.1
(子序列与前缀 LCS 长度)
设 、 是有限符号序列,且符号相等有明确判定。子序列在严格递增索引选符号,位置不必连续。公共子序列的一个对齐,把两输入依次递增位置的相同符号配对。
定义为前缀 与 的最长公共子序列长度。空前缀长度为 0,所以 。
假设符号相等比较与每格操作成本为常数。表格索引是前缀长度,不是空前缀中并不存在的“最后符号索引”。
定理 8.1.2
(前缀递推)
对 ,
证明
(每个候选都受界定,且上界可以达到)
若 ,在两个较短前缀的最优对齐后加此符号,得到长度 。反向看任意公共子序列对齐:若使用任一末端索引 i 或 j,包含它的配对必是最后一对;删除此对,便落在两个较短前缀,所以原长度至多是上述值。若两末端索引都没用,本已落在较短前缀,也受同一上界。故等号成立。
若 ,对齐不能同时使用两末端索引:两者不能互配,分开配也违反递增顺序,因为使用 i 的对与使用 j 的对都必须是最后一对。因此至少有一个末端索引没用,候选必落在其中一个前缀子问题,长度至多为两者最大值。反之,每个前缀最优解仍是完整前缀的公共子序列,能达到该最大值。
证明透视
为什么只需看末端索引
证明的两个方向强度不同。下界 只需要:在较短前缀的任何对齐后面加上一对相配的符号,索引仍然递增;等式 正是在这里用上。上界才是实质的一半:它需要观察到使用任一末端索引的配对必是最后一对,因为其他配对在两边的索引都较小;删去该对,就留下严格较短前缀的对齐。
关键一步是按末端符号有没有被使用来分类,而不是按哪个对齐最优来分类。在 的情形,同一步骤说明两者不能同时被使用:含 的配对与含 的配对都必须是最后一对,因此是同一对,也就是把 与 配对,而两者并不相等。
每种情形都化为严格较短的前缀 、 或 ,因此从空前缀出发,对 归纳就能收尾。如果要求子序列连续,删去最后一对并不保持同一类对象,状态与递推式就要改变。
按 i、j 递增填格,依赖项就已可用;归纳证明每格都等于其定义的最优值。最后长度为 ,表格时间与存储为 ,非空输入下即 。
从格子回溯到序列
TRACE_LCS(X, Y, L):
i = length(X)
j = length(Y)
reversed_output = empty buffer
while i > 0 and j > 0:
if X[i-1] == Y[j-1]:
append X[i-1] to reversed_output
i = i - 1
j = j - 1
else if L[i-1,j] >= L[i,j-1]:
i = i - 1
else:
j = j - 1
return reverse(reversed_output)
程序的序列索引从零开始,L 仍用前缀长度。序列是倒着收集的,因此最后须反转。
定理 8.1.3
(回溯返回最优公共子序列)
给定完整表格 ,TRACE_LCS 返回长度为 的公共子序列,且至多进行 次迭代。
证明
(保持长度的回溯不变量)
设 为目前已收集的符号数。每次迭代开始时,。起初 ,等式成立。如果 ,递推式给出 ,算法收集一个符号并沿对角移动。否则 ,而 >= 测试移到达到最大值的前驱,所以 与 的值都不变。循环在 或 时停止,此时 ,故 。收集到的符号来自在两个输入中都递减的索引对,所以反转后是公共子序列。每次迭代都减少 或 。
每步减 i 或 j,所以已有表格后回溯为 。>= 在平手时往上走,只选一个最优解,不枚举全部最优序列,也不枚举同一序列的全部对齐。
概念视角几何
把表格看成格子上的最长路径
画出前缀对 的格子。从 或 走到 的一步权重为 ;从 到 的斜步只在 时才允许,权重为 。这样 就是从 到 的路径的最大总权重,每一个斜步就是一对配对。回溯是倒着还原一条最优路径。每条通往 的路径都会在某个列 穿过任何固定的第 行,这正是后面使用的 分割。
例题 8.1.4
(ABAB 与 BABA 不只一个最优答案)
行是 ABAB 前缀,列是 BABA 前缀:
| X 前缀 | 空 | B | BA | BAB | BABA |
|---|---|---|---|---|---|
| 空 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 1 | 1 | 1 |
| AB | 0 | 1 | 1 | 2 | 2 |
| ABA | 0 | 1 | 2 | 2 | 3 |
| ABAB | 0 | 1 | 2 | 3 | 3 |
最优长度为 3,所示平手往上的回溯返回 ABA;若最后平手改往左,可返回 BAB。两者在两字符串都有递增配对位置;长度证明没有保证唯一。
滚动行必须保留旧对角值
若只求长度,前一行与当前行已足够;从左至右更新时,甚至只需一个数组:
LCS_ROW(X, Y):
m = length(Y)
dp = array of m + 1 zeros
for each symbol x in X:
diagonal = 0
for j from 1 through m:
old = dp[j]
if x == Y[j-1]:
dp[j] = diagonal + 1
else:
dp[j] = max(dp[j], dp[j-1])
diagonal = old
return dp
定理 8.1.5
(滚动行不变量)
在 LCS_ROW 中,处理 X 的第 个符号时,每次对 的迭代开始,都有 dp[j] 、dp[j-1] 及 diagonal 。该行结束时,对每个 都有 dp[j] 。
证明
(对行与列归纳)
处理第一行之前,dp 为 。每行开始时 diagonal 为 ,而 dp[0] 从不改变。设三项事实在第 轮成立。覆写前先保存 old dp[j] ,更新就恰好算出递推式:相配时得到 diagonal ,否则取 dp[j] 与 dp[j-1] 的最大值。因此新的 dp[j] 是 ,而 diagonal = old 提供 ,正是第 轮所需的对角值。同时 dp[j+1] 仍是 ,新的 dp[j] 是 ,三项事实因而恢复。
行存储为 ,非空时间仍为 ;必要时交换输入,可让 m 是较小长度。但最后一行并不包含完整表格的前驱选择。
反例模式
新写入的对角值可能重用同一符号
取 X=A、Y=AA,正确末行为 [0,1,1]。若更新格子后用 diagonal = dp[j],而非保存的 old,第一配对会把 diagonal 1 带到第二配对,结果成 [0,1,2]。
这把唯一 X 符号用了两次,违反严格递增索引。保留旧对角值是正确性要求,不是小小存储偏好。
在边界切开一个最优对齐
把 X 分为长度 的左半 与右半 。对每个 Y 边界 ,设
区间索引从零开始且不含右端。F 用一次正向行计算;B 可用反转 、反转 Y 的行 G,令 。两序列同时反转,会把公共子序列也反转,长度不变。
定理 8.1.6
(分割边界保留最优长度)
对此固定 X 分割,
证明
(切开完整对齐,再连接两个局部对齐)
任一对齐中,使用 的配对都在使用 的配对之前,且 Y 索引也递增。因此可在两组 Y 索引之间选边界 j;若一组为空,可选相应端点。左组长度至多 F[j],右组至多 B[j],所以整体最优不超过所示最大值。
反之,任一 j 的最优左、右对齐可连接,因为两 X 区间与两 Y 区间有序且不相交,得到长度 F[j]+B[j] 的合法对齐。这给反向界,证明等式。
以分治重建
分割等式给出 Hirschberg 式重建。把子串与反转当成原输入的索引视图,不复制字符串;所有符号追加至同一输出缓冲区:
APPEND_LCS(X, Y, output):
n = length(X)
m = length(Y)
if n == 0 or m == 0:
return
if n == 1:
if X[0] occurs in Y:
append X[0] to output
return
h = n // 2
F = LCS_ROW(X[0:h], Y)
G = LCS_ROW(reverse(X[h:n]), reverse(Y))
j = smallest index maximizing F[j] + G[m-j]
release F and G
APPEND_LCS(X[0:h], Y[0:j], output)
APPEND_LCS(X[h:n], Y[j:m], output)
空输入与单符号直接解决;否则选最大边界,重建两个小问题。由分割定理及归纳,连接是最优的;先追加左答再追加右答,保留顺序。选最小 j 的平手规则是确定的,但未必与完整表格平手往上的答案相同。
例题 8.1.7
(在 X 的中点分割 ABAB 与 BABA)
对 ABAB、BABA,把 X 分成 AB、AB:
| 边界 j | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| F[j] | 0 | 1 | 1 | 2 | 2 |
| B[j] | 2 | 2 | 1 | 1 | 0 |
| 和 | 2 | 3 | 2 | 3 | 2 |
第一个最大边界为 j=1。左边由 AB、B 得 B;右边由 AB、ABA 得 AB;连接为 BAB,与早前回溯不同,但同样最优。
例题 8.1.8
(空输入与单符号的第一序列)
对 AB、 为空,LCS_ROW 的 ,所以 dp 是 [0],长度为 ;APPEND_LCS 在第一个测试就返回,不追加任何符号。对 C、 ACC,使用单符号分支。LCS_ROW 得到 [0,0,1,1]: 中两个 C 都与 唯一的 C 相配,但第二次相配用的是已保存的对角值 ,不是新值,所以长度为 。APPEND_LCS 只追加一个 C,不是两个。若 D,同一输入得 [0,0,0,0],不追加任何符号。
分开计算重算、递归与输出成本
定理 8.1.9
(分治重建的成本)
对 的非空输入,APPEND_LCS 的时间为 ,辅助空间为 ,另加长度 的输出所需 。
证明
(几何面积界与存活行)
长度 、 的非基础子问题,两次行计算合计 ;扫描 b+1 个分割分数花 ,所以总界仍为 。子问题第一长度至多 ,第二长度之和为 b,所以子问题长度乘积的总面积至多 。跨递归层求几何和,非空输入工作为 。单符号叶子扫描 Y 视图,时间等于其面积;空子问题与调用开销是 ,m 正时也包含于 。初始空输入则立即返回。
两个分数行用 内存;递归前释放,才不会让父层行继续占用调用栈中的存活数据。第一输入每次减半,控制帧用 空间。起初令 后,非空输入的此实现辅助空间为 ,另有答案长度 所需 输出存储。这把线性行存储与调用栈分开计算。复制子串、保留父行或反复连接不可变输出字符串,都须另作成本分析。
插入/删除距离是同一最优值的另一面
定理 8.1.10
(插入与删除距离)
如果只允许单符号插入与删除,把 变成 的最少操作数为
证明
(保留一个最长公共子序列)
保留一个长度 的最长公共子序列,删其余 符号,再插入缺少的 符号,便达上界。反之,一个编辑过程中存留的原符号,在两序列依序出现,故其数 k 至多 。至少删 n-k 个原符号,插入 m-k 个最终符号,需要至少 次操作;即使过程浪费额外编辑,此下界也成立,故等式得证。
单位成本替换是另一种操作。A、B 的 LCS 为 0,插入/删除距离为 2,但一次替换只花 1。公式必须配合其指定编辑模型。
对一般输入,没有已知指数低于二的算法,而这个问题与一个困难性猜想有关。
自然的下一个问题
可以避开二次规模的表格吗?
对一般输入,没有已知指数低于二的算法,而这个问题与一个困难性猜想有关。
本节每个方法所需时间都与 成正比。对长度同为 的一般输入,没有已知的算法能在 时间内运行( 固定)。一个被广泛研究的困难性猜想若成立,就会排除这样的算法,但该猜想超出本课程范围。因此表格方法是标准答案,而不是已证明的最优。
常见错误
常见错误
(混淆子序列与子串)
对 ABC 与 AC,最长公共子序列是 AC,长度 ,但最长公共连续子串长度只有 (A 或 C)。上面的递推式针对子序列;子串版本在不相配时须重置为 ,而不是取最大值。
常见错误
(不相配时只跟随一个前驱)
时, 与 都是候选。对 BA、 B,在 末符号不同。如果只用 ,得到 ,但 更大,真正的值是 。
常见错误
(指望由最后一行得到序列)
LCS_ROW 对 ABAB 与 BABA 的最后一行是 [0,1,2,3,3]。它给出最优长度 ,却同时符合 ABA 与 BAB,也没有记录前驱选择。重建需要完整表格,或分治重算。
附解答练习
快速检查
(保留行的旧数据)
对 X=A、Y=AA 运行滚动行,列出每次内循环的 old、diagonal、更新值。把新格带作下一对角值,破坏哪项不变量?
解答 · 答案
起初 dp=[0,0,0],diagonal=0。j=1 时 old=0,格改为 1,再令 diagonal=old=0;j=2 时 old 也为 0,格改为 1,diagonal 仍为 0。末行为 [0,1,1]。若带新第一格,diagonal 会成 1,再产生 2,超过单符号输入长度。对角值必须属于前一行。
快速检查
(平手不代表 LCS 唯一)
按平手往上规则,回溯例题 ABAB、BABA 表格并列配对位置。最后平手的另一选择如何产生另一个最优序列?
解答 · 答案
从 (4,4) 往上到 (3,4),再配 (3,4)、(2,3)、(1,2),倒向收集 A、B、A,答案为 ABA。最后平手若往左,到 (4,3) 后用 (4,3)、(3,2)、(2,1),反转得到 BAB。两者长度都为 3;表格证明最优长度,平手策略选一个见证。
快速检查
(找到分治边界)
X=ABC、Y=ACB,把 X 分为 A、BC。求 j=0、1、2、3 的 F[j]、B[j] 及和。最小 j 策略选哪里,可产生什么最优序列?
解答 · 答案
F=[0,1,1,1],B=[1,1,1,0],和=[1,2,2,1]。选 j=1,左问题为 A 对 A,右问题为 BC 对 CB。左边贡献 A,右边递归最小 j 规则可给 C,所以得到 AC。j=2 则可得 AB。两个长度二答案都达最大值;两个长度三输入的顺序不同,没有长度三公共子序列。
快速检查
(说清楚允许哪种编辑)
用 LCS 求 ABC 到 AC 的插入/删除距离,并给出达到上界的过程。为何同一公式不给 A 到 B 的单位替换距离?
解答 · 答案
LCS AC 长度为 2,距离 ,删 B 即达到。A、B 的 LCS 为 0,删 A 再插 B 花 2;若可花 1 替换,直接把 A 改 B 更便宜。新增操作改变了优化问题,不反驳插入/删除定理。