動機
兩個字串之所以不同,可能是因為某個字元被插入、刪除或替換。僅統計不匹配的位置是不夠的:在開頭附近插入一個字元會使其後所有位置發生移位,但可能只需要一次編輯。編輯距離所問的是:把一個字串變成另一個字串,所需容許操作的最少次數是多少。凡是需要基於這些操作作精確比較的場合,它都很有用,但其數值取決於我們所選擇的代價模型。
動態規劃作用於成對的前綴。其核心思想是對一個對齊的最後一列進行分類,從而把整體的最優變換與較小的前綴問題聯繫起來。這張表既是計算距離的工具,也是可以據以還原最優變換的記錄。
定義
定義 2.10.1
(編輯操作與對齊)
設 與 是同一字母表上的有限字串。容許的操作為:插入一個字元、刪除一個字元,或把一個字元替換為另一個不同的字元;每次操作代價為一。所有中間字串均被容許。記 為把 變換為 的最小代價。空前綴的長度為零。
一個對齊(alignment)把兩個字串的字元按原有次序放入若干列中,容許任一行出現空位(gap),但同一列的兩行不得同時為空位。兩個相同字元所在的列代價為零,兩個不同字元所在的列代價為一,含一個空位的列代價為一。對齊的代價是各列代價之和。
定理
定理 2.10.2
(編輯序列與對齊)
對任意兩個有限字串,單位代價的插入、刪除與替換的最少次數,等於這兩個字串的對齊的最小代價。
定理 2.10.3
(前綴遞推式)
邊界值為 與 。對 ,
其中方括號在兩個字元不同時取一,否則取零。按行、列遞增的次序填表,可在字元比較為常數時間的前提下,以 的時間與空間計算出 。
證明
證明:為甚麼對齊能刻劃編輯
證明
(編輯序列與對齊相對應)
由一個對齊可得到代價相同的編輯序列。從左到右掃描它的各列。若某列兩行字元相同,則保持該字元不變。若兩行字元不同,則把上行字元替換為下行字元;若其下行為空位,則刪除上行字元;若其上行為空位,則插入下行字元。列的次序保證了這些操作可以從左到右依次施行,同時保持尚未處理的後綴不變。因此最小編輯代價不超過最小對齊代價。
反方向:考察任意一個編輯序列,並把當前字串中的每個字元追溯回它原來的字元(如果有的話)。被插入的字元沒有原始祖先;替換保留字元的祖先關係,刪除則移除該字元。這些操作從不改變仍存活的祖先之間的次序。在最終字串中,把每個存活的原始祖先與其最終後代對齊。把被刪除的原始字元與空位對齊,把最終字串中被插入的字元也與空位對齊。這些未配對的字元,按其在原字串與最終字串中的次序,放置在相鄰的已配對祖先之間。
每個與不同的最終後代對齊的原始字元,至少被替換過一次。每個被刪除的原始字元必然被刪除過,而最終字串中沒有原始祖先的每個字元必然被插入過。這些是互不相同的操作計費;先被插入、隨後又被刪除的中間字元,以及重複的替換,只會增加該序列的代價。所以所得對齊的代價不超過該編輯序列的代價。取最小值即證得相等。這一祖先論證容許任意的中間編輯;它並不預先假定最優序列具有某個便於處理的最後一步操作。
證明:前綴遞推式
證明
(由最後一列得到前綴遞推式)
若目標為空,則源字串的每個字元都必須被刪除;若源為空,則目標的每個字元都必須被插入。這就證明了邊界值。現在考慮兩個非空前綴的一個最小代價對齊。它的最後一列恰為三種類型之一: 在空位之上,空位在 之上,或 在 之上。去掉這一列,剩下的是相應較小前綴的一個對齊。其代價等於該列的代價加上不小於這些前綴最優值的量。由此得到所示最小值的一個下界。
反過來,把三種可能的最後一列分別接到相應較小前綴的最優對齊之後。所得對齊是合法的,並且達到相應候選值的代價。因此最小的候選值是可以達到的,從而證得相等。由對齊定理,它也是最少的編輯次數。
每個表項只依賴於其上方的表項、左方的表項以及左上對角的表項。從已初始化的第一行與第一列出發逐行填表,三者都已就緒。共有 個表項,在所述模型下每項只需常數工作量,由此得到時間與空間的界。若只需要距離,則只保留上一行以及當前行中已填好的部分,只用 空間;交換兩個字串的角色可得 空間。僅靠這種節省空間的計算,並不保留可供回溯的完整表。
證明透視
對齊的最後一列
這三種情形窮盡且互斥:刪除源的最後一個字元、插入目標的最後一個字元,或把兩個最後字元對齊。字元相同的情形代價為零;不同的情形則是替換。該證明比較的是完整的對齊,而不是去猜測任意一個編輯腳本中字面上最後發生的是哪一次編輯。
例題詳解
例題 2.10.4
(移位的後綴)
透過在 a 與 t 之間插入 r,可把 cat 變為 cart。一個對齊是
其代價為一。兩個字串不同,所以零次編輯不可能做到。它們的距離恰為一,儘管末尾的 t 的位置發生了移動。
例題 2.10.5
(一張完整的小表)
對於源 ab 與目標 ac,前綴距離表為
右下角的表項為一:把兩個 a 對齊,並把 b 替換為 c。在該儲存格處,對角候選值為 ,而刪除與插入的候選值都是二。
例題 2.10.6
(多個最優腳本)
對於 ab 與 ba,兩次替換的代價為二。刪除第一個 a 並在末尾插入一個 a,代價同樣為二。一次操作無法得到目標:一次替換只改變一個位置,而一次插入或刪除會改變長度。最優值為二,回溯時遇到並列的情形,可能返回不同的最優對齊。
例題 2.10.7
(空字串)
從空字串到 dog 的距離為三:插入它的三個字元。沒有任何一次操作能插入多於一個字元,所以少於三次不可能做到。表的第一行對每個目標前綴記錄的正是這一推理。
還原編輯序列
從 出發。在每個非邊界儲存格處,選擇一個達到遞推式最小值的前驅:向上對應刪除,向左對應插入,沿對角線對應匹配或替換。在邊界上,則只沿該邊界取唯一可能的移動。每一步移動都使 減小,所以該過程至多經 步後在 處停止。
回溯的各步移動按相反次序描述對齊的各列。把所記錄的列表反轉,然後像第一個證明那樣從左到右掃描其各列以施行操作。並列時可任意選擇:與表項相等這一條件保證所記錄各列代價之和等於 。若按回溯的相反次序直接寫出操作而不調整下標,可能得到錯誤的腳本,因此對齊是一種穩定的中間表示。
例如,從 ab 對 ac 一表的右下角表項出發,一次對角移動記錄替換 ,下一次對角移動記錄匹配 。把所記錄的列反轉,先得到匹配,再得到替換。由此得到的編輯腳本只改變第二個字元一次。
概念視角結構
把表看成最短路徑問題
取頂點為 (、)的網格圖。邊 與 的代價為一,邊 的代價為 。於是 就是從 到 的路徑最小代價,而從 到 的每條路徑逐步對應一個對齊的各列。最優對齊恰好就是最短路徑,回溯則是沿一條最短路徑反向走回去。
常見錯誤
反例模式
漢明(Hamming)距離不等於編輯距離
等長字串 abc 與 bca 在三個位置上都不相同,但刪除第一個 a 並把它插入到末尾,只需兩次編輯。逐位置的不匹配計數可能高估編輯距離,因為刪除與插入會改變對齊方式。
常見錯誤
(把單位代價的表用於另一種代價模型)
遞推式取決於所容許的操作及其代價。若替換的代價是二而不是一,對角線候選在字元不同時就必須加二。否則 a 到 b 會得到距離一,但此時最便宜的腳本是一次刪除加一次插入,代價為二。若轉置也算單一操作,則需要另一個遞推式及證明。為某一模型算出的表,不應不加說明地被當作另一模型的距離。
常見錯誤
(把距離當作編輯腳本)
距離本身也不等同於某個具體的編輯腳本。若要輸出腳本,必須保留足夠的前驅資訊,或用另行證明的方法重新計算。滾動行能為數值答案節省記憶體,卻丟棄了上述簡單回溯過程所用的完整表。
距離的性質及其局限
單位代價的距離是對稱的:把編輯序列反轉,將每次插入換成相應的刪除,每次刪除換成相應的插入,並把每次替換換成其逆替換。這就構造出方向相反、代價相同的序列。對兩個方向都應用這一論證,即證得 。
它還滿足三角不等式。把從 到 的一個最優編輯序列與從 到 的一個最優編輯序列連接起來,就得到從 到 的一個合法(但不一定最優)的序列,所以 。距離非負,並且當且僅當兩個字串相等時為零。綜合這些事實,單位代價的編輯距離是有限字串上的一個度量。
連接而成的腳本可能含有互相抵消的編輯。例如,把 a 變為 ab 再變回 a,總代價為二,而直接把 a 變為自身的代價為零。因此三角不等式只是一個不等式,並不斷言經由某個選定的中間字串總是最優的。
選擇表的方向
在這一對稱的模型中,行與列可以互換。若其中一個字串短得多,在節省空間的計算中就用它作為所儲存的那一行。例如,比較一個一千字元的字串與一個十字元的字串,時間仍與它們長度之積成正比,但行緩衝區只需十一個表項。算術模型假定表項與下標滿足所述的常數時間運算;表示特別長的字串時,可能需要另作位元代價分析。
節省空間與還原腳本是兩個不同的設計目標。完整的表使我們在每一步都容易沿著前驅走,並驗證它與所存值相等。滾動行的實作應當只承諾給出距離,除非它同時實作並證明了某種還原方法。這一區分可以避免把針對數值答案的複雜度結論,不加說明地套用到對所選編輯的完整說明上。
總結
對齊的各列是聯繫任意編輯腳本與前綴遞推式的橋樑。三種可能的最後一列分別給出刪除、插入以及匹配或替換的候選值。填完的表給出最優值,而前驅的選擇則可還原一個最優對齊及編輯序列。
練習
快速檢查
(計算從 a 到 b 的編輯距離,並說明理由。)
解答 · 答案
把 a 替換為 b,代價為一。兩個字串不同,所以零次操作不可能做到;距離為一。
快速檢查
(計算從 ab 到 a 的編輯距離,並給出一個最優腳本。)
解答 · 答案
刪除末尾的 b,代價為一。由於輸入與輸出的長度不同,至少需要一次操作。
練習 2.10.8
(給出 abc 與 bca 的一個代價為二的對齊。為甚麼距離不是一?)
基礎
解答(3)
- 1
給出代價為二的對齊
把
a與空位對齊,接著b對b、c對c,最後空位對末尾的a。代價為 。依據: 兩個相同字元的列代價為零,含空位的列代價各為一。
- 2
排除單次編輯
關鍵一步
單次編輯是一次替換、插入或刪除。替換只改變一個位置,但兩個字串在三個位置都不同;插入或刪除會改變長度,但兩個字串的長度都是三。
- 3
得出距離為二
零次編輯會迫使兩串相等,而一次編輯不可能,所以距離至少為二。上面的對齊顯示距離至多為二。因此距離恰為二,尤其不是一。
快速檢查
(對於 aa 與 a,列出兩個不同的單次編輯腳本,並說明回溯時並列情形是如何產生的。)
解答 · 答案
刪除第一個或第二個 a。兩者都得到 a,代價為一。在相關的表儲存格處,不同的最小代價前驅路徑把目標的 a 與源中不同位置的 a 對齊。重複的字元使這些對齊互不相同,儘管所得到的字串相同。