從精確匹配到編輯
精確字串匹配問的是模式在哪裏原封不動地出現。另一個問題是把一個字串變成另一個需要多少工作。先為每個字串固定一個有限符號序列;處理文字時,算法執行前須約定符號表示,因為位元組、Unicode 碼點和顯示字元未必相同。
定義 6.2.1
(編輯距離)
設 與 是有限符號序列。編輯序列以有限多次操作把 變成 ,每次操作插入、刪除或替換一個符號,成本各為一;保留符號不變的成本為零。編輯距離 是這種編輯序列的最小總成本。空編輯序列的成本為零;此模型不把相鄰符號對調視為一次操作。
對齊與遞推式
定義 6.2.2
(對齊及其成本)
和 的對齊把兩者的符號排成兩行,並保留每行的原有次序。一列可以配對兩個符號,或把一個符號與空位配對;一列不能有兩個空位。相同符號配對成本為零,不同符號配對及單空位列各成本一。對齊的成本是各列成本之和。
例如 和 的一種對齊為
成本為二:把 替換成 ,再插入 。
為何最小對齊成本應該等於編輯距離?下面的結果說明確實如此,其證明也顯示了兩種描述如何互相轉換。
定理 6.2.3
(對齊成本等於編輯距離)
對任意有限序列 與 , 與 的最小對齊成本等於編輯距離 。
證明
(從對齊到操作序列,再從操作序列回到對齊)
對齊可給出同成本的操作序列:從左至右掃描,保留或替換成對符號,刪去與空位配對的上行符號,插入與空位配對的下行符號。因此最小對齊成本至少是 。
反過來,沿任意編輯序列追蹤符號身分:替換保留身分,刪除終止身分,插入則建立新身分。最後仍存在的原符號保持原有次序,因為容許的操作均不交換符號。把每個這樣的原符號與其最終後裔配對;每個被刪原符號及每個最終插入符號則與空位配對。在相鄰存活配對之間、首對之前及末對之後(若沒有存活配對則處理整個序列),按原有次序列出被刪原符號,按最終次序列出插入符號;把兩列依次放置仍保留各行次序。
每對不同的存活符號至少需要一次替換,每個被刪原符號至少需要一次刪除,每個最終插入符號至少需要一次插入。這些所需操作互不相同,故對齊成本不大於該操作序列成本。此論證亦容許多做一些隨後被抵消的操作;它們不能使操作序列比對齊更便宜。兩個最小值因而相等。
定義 6.2.4
(對齊成本的前綴表)
記 、。對 、,令 為 前 個符號與 前 個符號的最小對齊成本。當 ,若 令 ,否則令 。
定理 6.2.5
(編輯距離的前綴遞推式)
沿用上述記號,有 、,而當 時
因此 。
證明
(移去與附加最後一列)
邊界:若其中一個前綴為空,另一個前綴的每個符號都必須與空位配對,每列成本為一。故 、。
設 。上界:對三個候選值中的每一個,取較小前綴的一個最優對齊,並附加相應的末列,即 對空位、空位對 ,或 對 。每個結果都是較長前綴的一個對齊,成本等於該候選值,所以 不大於三者的最小值。
下界:取兩個前綴的一個最優對齊。因為不容許兩個空位,其末列恰為三種形式之一。移去末列後,餘下是相應較短前綴的一個對齊,成本至少為對應表格項,而被移去的一列成本分別為 、 或 。所以 至少等於該形式對應的候選值,因而至少等於最小值。對 作歸納,把同一論證用於較小的表格項,邊界值提供起點。最後由上一個定理得 。
證明透視
為何只看最後一列就足夠
關鍵一步是只看最優對齊的最後一列。末列恰有三種形式,因為含兩個空位的列是被禁止的;這是用到對齊定義的地方。移去這一列後餘下的是較短前綴的對齊,而成本對各列可加,所以沒有損失資訊;正是這種可加性讓前綴成本表可以取代對所有對齊的搜尋。
論證以 歸納完成,因為每個候選值都指向下標和更小的表格項。上界用的是最優子對齊,下界用的是整體最優對齊;兩個方向缺一不可。若成本依賴相鄰的列,例如較長空位的起始成本較低,移去一列便不再留下獨立的子問題,這個遞推式也就不成立。
同一張表還有第二種等價的描述,即最短路徑的計算。
概念視角組合
對齊就是格點上的路徑
把各項 放在格點上。由 到 的向下一步,是把 與空位配對的一列;向右一步是空位對 ;對角一步把 與 配對,成本為 。 與 的對齊恰好對應從 到 的單調路徑,對齊成本就是路徑長度。於是遞推式就是這個無環格點圖上常見的最短路徑方程, 是 到 的最短距離。
表格與見證
例題 6.2.6
(CAT 與 CUTS 的表格)
對 、,先填空前綴邊界,再逐行由左至右填表:
| 前綴 / 前綴 | 空 | C | CU | CUT | CUTS |
|---|---|---|---|---|---|
| 空 | 0 | 1 | 2 | 3 | 4 |
| C | 1 | 0 | 1 | 2 | 3 |
| CA | 2 | 1 | 1 | 2 | 3 |
| CAT | 3 | 2 | 2 | 1 | 2 |
例如, 對 的表格項是 ,其中對角候選值加上 ,因為 。 對 的表格項是 ,因為 使對角一步免費。右下角的值證明兩次編輯已是最優;前面給出的對齊提供相符的見證。
一般而言,要重構最優解,從 開始,每步選擇任一達到遞推式最小值的前驅並記錄對齊列。對角步記錄匹配或替換,向上步記錄刪除,向左步記錄插入。在 時繼續向左,在 時繼續向上,直至 ,然後把所記列次序反轉。並列可能產生不同的最優對齊;若實作需要確定輸出,必須指定並列處理規則。反向讀取後若不再反轉,列的次序便會錯誤。
定理 6.2.7
(回溯給出最優對齊)
從 出發,每步移到一個達到遞推式最小值的前驅(當 或 時沿邊界移動),並記錄各列。把所記錄的列反轉,便得到 與 的一個成本為 的對齊,因此它是最優的。
證明
(每一步剝去最優前綴對齊的一列)
斷言:從格點 回溯到 所記錄的各列,反轉後構成前 個與前 個符號的一個對齊,成本為 。對 歸納。在 處對齊為空,成本為 。在邊界 上只能向上走,每列刪除一個符號,成本為 ; 的情形對稱。
否則所選前驅 滿足 ,其中 是這一步所記錄那一列的成本。由歸納假設,從 回溯所得各列反轉後構成成本為 的對齊;附加所記錄的一列,便得到較長前綴的對齊,成本為 。在 處這就是 與 的一個最優對齊。
例題 6.2.8
(倒著讀 CAT 與 CUTS 的表格)
從值為 的 開始。對角前驅給出 ,向上的前驅給出 ,向左的前驅給出 ,所以記錄插入 。在 ,對角前驅給出 ,達到該值,所以記錄匹配 。在 ,對角給出 ,另外兩個給出 ,所以記錄替換 。在 ,對角給出 ,所以記錄匹配 ,到達 。
把所記錄的列反轉,得到 、、、,就是前面給出的對齊。這裏每一步都沒有並列,所以這是唯一的最優對齊。
例題 6.2.9
(並列與邊界情形:AB 對 BA)
對 、,表格為
| 前綴 / 前綴 | 空 | B | BA |
|---|---|---|---|
| 空 | 0 | 1 | 2 |
| A | 1 | 1 | 1 |
| AB | 2 | 1 | 2 |
在角落 ,三個候選值都等於二:向上給出 ,向左給出 ,對角給出 。每種選擇都通向一個最優對齊:兩次替換 、;或各列 、、;或各列 、、。它們的成本都是二。特別地,對調 在此模型中成本為二,而表格顯示不存在只用一次操作的序列,因為 。
下面的互動圖逐格填表,列出每格的三個候選值及達到最小值的前驅,並按所選並列規則回溯讀出最優對齊。
填好表格,再讀出最優對齊
按填表次序逐格查看 D[i,j]。對當前格會列出三個候選值 D[i−1,j]+1、D[i,j−1]+1 及 D[i−1,j−1]+c,並標出所有達到最小值者。表格填滿後,回溯由 (m,n) 沿達到最小值的前驅走回 (0,0);把所記錄的欄反轉,便得到成本等於 D[m,n] 的對齊。
| X 前綴 / Y 前綴 | 空 | C | CU | CUT | CUTS |
|---|---|---|---|---|---|
| 空 | ●0 | 1 | 2 | 3 | 4 |
| C | 1 | ●0 | 1 | 2 | 3 |
| CA | 2 | 1 | ●1 | ○2 | ○3 |
| CAT | 3 | 2 | 2 | ●1 | ●2 |
◆ 當前格 · ○ 候選格 · ● 在回溯路徑上
當前格的候選值
格 (3,4): D[3,4] = 2. X_i ≠ Y_j,故 c = 1.
| 規則 | 來自 | 數值 | 最小值 |
|---|---|---|---|
| 向上:D[i−1,j] + 1(刪除 X_i) | (2,4) | 3 + 1 = 4 | × 高於最小值 |
| 向左:D[i,j−1] + 1(插入 Y_j) | (3,3) | 1 + 1 = 2 | ✓ 達到最小值 |
| 對角:D[i−1,j−1] + c(X_i 與 Y_j 配對) | (2,3) | 2 + 1 = 3 | × 高於最小值 |
由 (m,n) 回溯
| 步 | 格 | 方向 | 記錄的欄 |
|---|---|---|---|
| 1 | (3,4) | 向左 | - / S (插入) |
| 2 | (3,3) | 對角 | T / T (匹配) |
| 3 | (2,2) | 對角 | A / U (替換) |
| 4 | (1,1) | 對角 | C / C (匹配) |
反轉所記錄的欄後得到的對齊
| X 行 | C | A | T | - |
|---|---|---|---|---|
| Y 行 | C | U | T | S |
| 欄成本 | 0 | 1 | 0 | 1 |
1: 匹配; 2: 替換; 3: 匹配; 4: 插入.
- m = |X|
- 3
- n = |Y|
- 4
- 已填格數
- 20/20
- D[m,n]
- 2
- 對齊成本
- 2
- 欄數
- 4
- 另一並列規則下的對齊
- 相同的對齊: C A T - / C U T S
對齊成本 = D[m,n] = 2。
為何回溯所得的見證成本恰為 D[m,n]
回溯每一步都走到達到遞推式最小值的前驅,所以離開的格之值,等於進入的格之值加上所記錄那一欄的成本:對角匹配為 0,其餘為 1。
沿 (m,n) 至表值為 0 的 (0,0) 的路徑求和,各欄成本之和便是 D[m,n]。反轉之後,這些欄亦按次序恰好用上 X 與 Y 的每個符號各一次。
遞推式只要求某個達到最小值的前驅,因此並列時回溯可以任選;不同選擇給出總成本相同的不同對齊。若讀出所記錄的欄而不反轉,所得便是倒序的對齊。
兩種並列規則一定給出不同的對齊嗎?
不一定。CAT / CUTS 每一步都只有一個達到最小值的前驅,兩種規則結果相同。AB / BA 在 (2,2) 有三個達到最小值的前驅,兩種規則分別給出兩次替換,以及刪除 A 後再插入 A,成本同為 2。
字串只用字母 A 至 Z,各至多 8 個。模型只有成本為一的插入、刪除與替換;相鄰對調不是操作,所以 AB 變 BA 的成本為 2。游標顯示按逐行次序已填的前 k 格;回溯只在表格填滿時顯示。所有數值都是精確整數。
成本、記憶體與模型選擇
共有 個表格項,每項用常數時間計算,故完整表格的時間和空間成本均為 。若只需要距離,遞推式只需保留上一行和當前行,工作空間可降至 ;保留完整表格則支援上述簡單回溯。用更少記憶體恢復對齊需要額外工作,不能丟棄所有舊行後仍按原方法回溯。
改變操作成本會改變遞推式,也可能改變其數學性質。特別是上述模型不包含一次相鄰對調: 到 的距離在此模型為二,雖然另設對調操作時可花一。動態規劃返回最小編輯成本,並非判斷兩個句子語意是否相同。
反例模式
只有插入與刪除會得到另一種距離
一個看似合理的說法是 ,其中 LCS 是最長公共子序列的長度。對 、,最長公共子序列是 ,長度為二,因為 不在 中出現。公式給出 ,但表格給出 ,見證是把 替換成 再插入 。該公式是只容許插入與刪除的模型中的距離,在那個模型裏替換必須用一次刪除加一次插入來模擬,成本為二。容許單位成本的替換時,必須使用上面的遞推式。
常見錯誤
常見錯誤
(把空前綴邊界初始化為零)
設 等於說把空字串變成長度為 的字串不需要成本。對 、,被破壞的表格給出 ,可是 ,真實距離是一(插入 )。邊界 記錄的是 的 個符號都必須被插入。
常見錯誤
(對角步比較了錯誤的符號)
處的對角候選值使用 ,它比較的是 與 ,即兩個前綴的最後一個符號。若實作從零開始編號,在按前綴長度編號的表格中卻比較 與 ,就差了一位。對 與 的 ,它會比較 與 ,得到 ,而正確值是 。
練習
快速檢查
(計算 到 的距離,並給出一個最優操作序列。)
先比較兩個字串的長度。
解答 · 答案
距離是一。刪除最後的符號 的操作序列,以成本一把 變成 。因為兩個字串不同,不存在成本為零的序列,所以一是最優的。
快速檢查
(解釋為何空前綴邊界必須是 。若初始化為零會出甚麼問題?)
想一想 的空前綴能與甚麼配對。
解答 · 答案
空前綴沒有符號可與 的前 個符號配對,所以它們每個都與空位配對,每列成本為一;故 。若初始化為零,表格就聲稱在空字串中插入符號不需成本。對 、,它會給出 ,但兩個字串不同,真實距離是一。
快速檢查
(假設兩個轉移候選值在 並列最小。對這兩種末列選擇,是否各有一個相應前綴的最優對齊?解釋為何不在任何由 出發的最優回溯上的表格項,即使有並列,也未必給出完整字串的兩個最優對齊。)
第二部分可試 與 中 對 的表格項。
解答 · 答案
是。若某個候選值達到最小值,則在較小前綴的最優對齊後附加相應末列,便得到成本為 的對齊,因而是最優的,並且以該列結尾。所以兩種結尾都存在。
表格項上的並列並不表示該項屬於完整字串的最優對齊。在 與 的表格中, 的值為二,既可由上方()也可由對角()達到。兩者都給出 對 的最優對齊。但要把任一個補成 ,仍須插入 與 ,總成本至少為 ,大於 。這個表格項不在任何由 出發的最優回溯上。