最優長度與實際序列是不同輸出
對 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 更便宜。新增操作改變了最優化問題,不反駁插入/刪除定理。