動機
兩個字串即使其符號並不相鄰,也可能共享一個有序的模式。只要符號的相對次序重要而容許有間隔,尋找最長的這種模式就有實際用途。直接搜尋所有子序列,會多次重複求解相同的前綴問題。動態規劃為每一對前綴記錄最優答案,再利用這些答案構造一個最優子序列。
子序列不同於子字串:容許刪除符號,但不要求保留下來的符號在原字串中保持連續。保留下來的符號的次序則必須保持不變。本文計算的是長度以及一個見證;求出所有見證則是另一個輸出問題。
定義
定義 2.1.1
(子序列與前綴表)
設 與 為有限字串。若字串 可以透過從 中刪除零個或多個位置、且不改變其餘位置的次序而得到,則稱 是 的子序列。容許出現重複符號,但同一個被選取的位置不能使用兩次。公共子序列是同時為兩個字串的子序列的字串。空字串總是公共子序列,即使其中一個輸入為空亦然。
對於 與 ,將 定義為前綴 與 的公共子序列的最大長度。空前綴給出 。狀態同時記錄兩個前綴的長度,是因為去掉其中一個字串的最後一個字元,只改變兩個約束中的一個。
定理
定理 2.1.2
(前綴遞推式)
對於 ,
表中的值 是最長公共子序列的長度。
定理 2.1.3
(計算與重構)
按照上方、左方與左上方對角前驅項均已知的次序填表,需要 的時間與空間(當兩個長度均為正時即為 )。從 出發:若最後一個符號相同,則沿對角線移動並記錄該符號;否則移向表值較大的前驅,若相等則任意選取。將記錄下來的符號反轉,即得一個最長公共子序列。
證明思路或證明
證明
(前綴遞推式與重構)
若 ,將 附加到兩個較短前綴的任意一個最優公共子序列之後,便得到長度為 的公共子序列。反過來,取較長前綴的任意一個最優公共子序列。若它使用了其中任何一個最後位置,則其最後一個符號為 ;另一個字串中與之匹配的出現可以移到該字串的最後位置,而在它之前留下的是兩個較短前綴的一個公共子序列。若它兩個最後位置都沒有使用,則附加 將產生更長的公共子序列,與最優性矛盾。因此存在一個使用兩個最後位置的最優表示,去掉其最後一個符號,便得到較短前綴的一個公共子序列。這兩個不等式證明了符號相同的情形。
若 ,則沒有任何公共子序列能把兩個最後位置作為一對匹配位置同時使用。因此每個公共子序列至少避開其中一個最後位置:若它在各自匹配的位置上同時使用了兩者,則其相對次序會迫使兩個字串中最後被選取的符號相等。於是它屬於兩個較小前綴子問題中至少一個。反過來,任一較小前綴對的公共子序列,也是原來兩個前綴的公共子序列。取最大值即證明了符號不同的情形。
對 作歸納,邊界值與遞推式可正確計算表中的每一項。在重構過程中,符號相同情形下的對角移動從一個最優見證中去掉一個符號,而符號不同情形下的移動則保持最優長度不變。每一步移動都使至少一個下標減小,因此過程會在邊界處終止。符號是從右向左被發現的,必須反轉。反轉之後,它們所記錄的位置是遞增的,因此構成一個長度等於所宣稱最優值的公共子序列。
證明透視
一個有效的見證與一個上界
附加一個匹配的符號只提供了一個候選解,其本身並不能證明最優性。逆向論證必須說明:存在一個使用兩個最後位置的最優表示,因此它的前綴不可能超過較短前綴的最優值。
符號不同的情形以另一種方式收尾。使用 最後位置的公共子序列必以 結尾,使用 最後位置的公共子序列必以 結尾。兩者同時使用就會迫使 ,所以假設 將其排除,每個公共子序列都已屬於兩個較小問題之一。
例題詳解
例題 2.1.4
(容許有間隔)
對於 與 ,字串 是公共子序列:從第一個輸入中刪除 ,而第二個輸入不刪除任何符號。任何公共子序列的長度都不可能超過第二個輸入的長度,所以最優長度為二。同一個見證並不是 的子字串。
例題 2.1.5
(平手產生不同的見證)
對於 與 , 與 都是長度為一的公共子序列。長度為二的公共子序列必須同時等於兩個輸入字串,而這不可能。在最後這對不相同的符號處,兩個前驅項相等;任一選擇都能重構出一個最優解,但所選的見證可能不同。
例題 2.1.6
(重複符號使用的是位置)
對於 與 , 與 都是長度為二的公共子序列。兩個完整字串並不相同,所以不存在長度為三的公共子序列。 的一個有效見證使用 的前兩個位置以及 的第一和第三個位置;它沒有重複使用同一個出現。
常見錯誤
反例模式
共同子字串是另一個問題
對於 與 ,最長公共子序列的長度為二,但不存在長度為二的公共子字串。把子序列遞推式換成子字串遞推式,會在不知不覺中改變問題。
常見錯誤
(把長度表當作答案)
長度表本身並不會顯示見證。若題目要求給出一個子序列,就必須沿表追蹤並記錄各步選擇。若題目要求給出所有最長子序列,則任意打破平手並不足夠。表中不同的路徑也可能拼出同一個子序列,在符號重複時尤其如此。
填表與讀表
將第零行與第零列初始化為零。然後依次處理行 ,並在每一行內依次處理列 。需要用到上方、左方以及左上方對角的項時,它們都已可用。這一次序是依賴圖的一個有效拓撲序;先列後行的次序同樣可行。表中的格子代表的是前綴長度,而不單是字元下標,所以儘管不存在字元 ,第零行仍是真正的邊界。
例題 2.1.7
(一個小表及其追蹤)
取 與 。包括空前綴在內,表的各行為
在最後一格,兩個符號都是 ,所以記錄 並沿對角線移動到對應 與 的格子。在那裏符號 相同,所以記錄 並沿對角線移動到邊界。將記錄下來的序列 反轉,得到 ,這是一個長度為二的公共子序列。該表證明了不存在更長的公共子序列。
填好的表也是一種診斷工具。每一項都介乎零與較短前綴的長度之間。當任一前綴被延長時,值不會減小,因為之前所有的公共子序列仍然可用。若某個實作在增加一個字元之後產生了更小的值,就違反了這種單調性。這些檢查能夠暴露錯誤,但不能代替對遞推式的證明:一個錯誤的表也可能同時滿足這兩個界和單調性。
為甚麼符號相同的情形是安全的
常見錯誤
(以為每個最優解都使用兩個最後位置)
有時人們過於草率地為符號相同時的遞推式辯護,說每個最優解都必然已經使用了兩個最後位置。當符號重複時,以位置序列形式給出的最優解不一定如此。例如,對於 與 , 的第一個 可以用於一個最優匹配,而最後一個 則未被使用。證明所需要的是較弱的結論:存在一個使用兩個最後位置的最優表示。把已匹配的最後一個出現移到較後的相同出現上,可以保持此前所有的次序關係。
字串與其位置見證之間的這種區別在重構時很重要。不同的匹配位置集合可以產生同一個符號序列。若目標是得到一個公共子序列,任何有效的匹配位置都足夠。若目標是統計不同字串的數目,對路徑數求和一般是錯誤的,因為多條路徑可能拼出同一個字串。若目標是統計位置匹配的數目,那是另一個需要明確說明的計數問題。
符號不同情形的證明同樣使用位置,而不僅僅是字元是否出現。一個符號可以在兩個字串中多次出現,但在一個字串中最後被選取的位置,必須與另一個字串中最後被選取的位置相匹配。若某個公共子序列同時使用兩個最後位置,則這兩個位置代表的是同一個最後被選取的符號。由於最後的符號不同,這不可能發生。因此至少有一個最後位置未被使用,可以將其去掉而不失去該見證。
概念視角組合
最長公共子序列即插入刪除距離
只用插入和刪除把 變成 。 中從未被刪去的符號構成 與 的一個公共子序列;反過來,每個公共子序列 都給出這樣的一個步驟:刪去 的其餘 個符號,再插入 的其餘 個符號。因此最少的操作次數是 。對 和 ,這是 。
空間與輸出的選擇
完整的表為每一對前綴使用一個格子。若只需要最優長度,則每一行只依賴於上一行及其自身前一個格子,所以兩行就足夠。當行對應 的前綴時,這將儲存量降為 個格子;交換兩個字串,可以讓較短的維度成為被儲存的行。邊界行必須正確初始化,並且必須保留當前行的左側值。時間界仍與格子數成正比。
僅用兩行的計算本身並不會保存簡單的向後追蹤所需的全部前驅選擇。因此,若不說明如何恢復缺失的資訊,就不能同時承諾做到這種精確追蹤與兩行儲存。可以保留完整的表、重新計算部分內容,或者使用另行證明過的分治重構。第一種方案就是這裏所證明的算法。見證的輸出也需要儲存空間:一個最長公共子序列最多可含 個符號。
所述的時間統計的是表的運算次數,並假設符號相等性可以在常數時間內檢驗。若輸入符號本身是龐大的結構,則必須計入它們的比較成本。該方法適用於任何具有明確相等性檢驗的有限序列;字母表不必很小。它也透過已初始化的邊界直接處理空輸入,在不進入重構迴圈的情況下給出空見證。
一個策略檢驗
反例模式
匹配最早出現的位置並不最優
有一種誘人的貪心規則:只要可能,就把第一個字串的每個符號匹配到它在第二個字串中最早的可能出現。對於 與 ,把開頭的 匹配到 的最後位置,會使 與 都沒有餘地,所以該規則只得到長度一。跳過 則可得到長度為二的 。局部的匹配可能耗用一個位置,從而阻礙更好的後續模式;動態規劃比較的是較小前綴對上的各種選擇,而不假設第一個可用的匹配是安全的。
這個反例針對的是所述的貪心規則,而不是每一種使用最早出現位置數據結構的算法。數據結構可以加速一個正確的算法,但並不決定其目標。若要一般性地論證某個貪心規則,就需要證明對每個輸入,其選擇都可以成為某個最優解的一部分。一個反例即可推翻這一全稱斷言,而遞推式的證明則確立了對每一對有限輸入的正確性。
總結
前綴對給出一個有限的狀態空間。最後的符號相同時,兩個前綴都縮短;最後的符號不同時,最優解必須避開至少其中一個。由此得到的表計算出最優長度,而向後追蹤可以恢復一個見證。
練習
快速檢查
(求 與 的一個最長公共子序列,並論證其長度。)
解答 · 答案
與 都是長度為二的公共子序列。長度為三要求兩個完整字串相等,所以二是最優的。
快速檢查
(若 為空而 的長度為五,邊界值是甚麼?)
解答 · 答案
對 ,每一項 都是零:空輸入的唯一子序列是空字串。
快速檢查
(對於 與 ,為甚麼答案不是二?)
解答 · 答案
第二個輸入只有一個位置,所以它的任何子序列的長度至多為一。符號 是長度為一的公共子序列。
快速檢查
(對於 與 ,給出最優長度及一個見證。)
解答 · 答案
這兩個字串沒有公共符號。最大長度為零,空字串是一個見證。