問題
搜尋時可能反覆把模式與相同的文字位置比較。出現不匹配並不代表已匹配的資訊全部無用:已匹配部分的後綴可能同時是模式的前綴。前綴函數正是記錄這些可供回退的候選。
設 為長度 的非空序列, 為長度 的序列。位置從零開始。我們報告 在 中每次出現的起始位置,包括互相重疊的出現。符號可以是字元、整數或其他記號;其相等測試必須是穩定的等價關係,並把每次測試計為一次運算。我們亦假設對模式和前綴表的索引存取為常數時間,逐個順序讀取文字符號亦為常數時間。本單元刻意不處理空模式的約定。
邊界與前綴表
定義 6.1.1
(邊界與前綴函數)
序列的邊界是同時為真前綴及後綴的序列;允許空序列,真是指長度嚴格小於整個序列。對每個 ,令 為 最長邊界的長度。因此 ,而且始終有 。
引理 6.1.2
(前綴回退)
若長度 的模式前綴與已處理文字的後綴相同,而下一個符號不匹配,則在比較下一個符號前,任何能匹配已處理文字後綴的較短前綴,都是該長度 前綴的邊界。當 ,最長可能的回退長度是 。重複此步驟便可考慮更短候選,無須重新讀取文字。
證明
(每個可行的回退都是邊界,而且邊界構成一條鏈)
假設長度 的較短前綴也匹配同一個已處理文字的後綴。那麼已匹配的長度 前綴的最後 個符號,便是模式最前面的 個符號: 是邊界長度。最長的此類邊界長度為 。更短的邊界也必是這個最長邊界的邊界,所以反覆套用同一規則會走訪所有剩餘的邊界長度,直至零。不相等排除了剛測試的候選,而可行候選不會被丟棄。
證明透視
為何邊界鏈不會遺漏
關鍵一步是只透過文字來比較兩個前綴:兩者都等於已處理文字的同一個後綴,所以較短的那個就是較長那個的末段。這是唯一要求相等必須表現為等價關係的地方。若在整數上採用「相差至多為一」的容差關係,則 、 但 ,兩個前綴可以都匹配文字,而較短的卻不是較長的邊界,邊界鏈便會遺漏候選。
邊界鏈是完整的,因為邊界的邊界仍是原序列的邊界。過程在長度為零處結束,而零永遠是一個邊界。只在比較失敗之後才丟棄候選是安全的,因為失敗的比較表示該候選無法被下一個文字符號延長。
建表按同一條鏈,在模式本身上進行。
定理 6.1.3
(前綴表的建構)
對 ,先取 。只要 且 ,便令 。若 ,將 加一。然後 。每個表項只依賴較早的表項。
證明
( 的邊界來自 的邊界)
設 是 的一個邊界長度。把前綴與後綴各去掉最後一個符號,便得到 的一個長度為 的邊界,而被去掉的符號相等:。反過來,若 是 的邊界長度且 ,則得到 的長度為 的邊界;因為 ,它是真邊界。
所以,若存在, 就是 的邊界長度 中滿足 的最大者。因為邊界的邊界仍是邊界, 的邊界長度由大至小依次是 ,而迴圈恰好按此次序逐個測試。它在第一個滿足 的 處停止,得到 。若鏈在 結束而 ,則不存在正長度的邊界,。當 時,仍須測試相等與否,判斷第一個符號能否開始一個邊界。
例題 6.1.4
(為 ababaca 與 abaab 建表)
對 ,各項為 :前綴 的最長邊界是 ,而符號 不能延續任何邊界,所以該項降為 。
再取 。;因為 ,;。對 ,先取 ;,回退至 ,此時 ,故 。對 ,先取 ;這時 ,故 。表為 ,而 確實是 的最長邊界。
不丟失重疊的掃描
定義 6.1.5
(掃描狀態)
處理了文字的一個前綴之後, 是已處理文字後綴中最長的真模式前綴之長度。當長度為 的模式前綴匹配時,便偵測到在當前符號結束的完整出現,並在重設 之前報告。
維持 ,表示已處理文字的某個後綴所匹配的模式前綴長度。讀取下一個文字符號之前,。對每個符號 ,只要 且 ,就令 ;若 ,便把 加一。若它變成 ,報告起始位置,然後重設 。此重設保留已匹配模式的最長真邊界,使後續出現可以與剛報告的出現重疊。
定理 6.1.6
(掃描恰好報告全部出現)
上述掃描按遞增次序報告 在 中每個出現的起始位置,不報告其他位置。處理每個符號及可能的報告後, 是已處理文字後綴中最長的真模式前綴之長度。
證明
(對已處理符號的個數作歸納)
在讀取任何符號之前,,結論成立。設讀取 之前結論成立。能匹配包含 在內的文字後綴的模式前綴,其長度為 ,前 個符號匹配較早文字的後綴,最後一個符號等於 。由歸納假設,候選的 就是從 開始的邊界鏈:最長的是 ,其次是 、,如此類推(由前綴回退引理)。迴圈由長至短測試它們,在第一個滿足 的 處停止,所以找到最長的延伸;若不存在,測試後 為零。若 變成 ,該後綴便是在當前位置結束的完整出現,於是報告起始位置。它的最長真邊界恰是讀取下一個符號所需的狀態。反過來,若有一個全長前綴匹配到在當前符號結束的文字後綴,那就是長度為 的延伸,是可能的最長者,所以迴圈恰好在出現處達到 。因此不會漏報,也不會誤報。
概念視角結構
把掃描看成有限自動機
狀態 是一個確定型自動機的狀態。讀入符號 時,它轉移到「同時是 的後綴的最長模式前綴(允許是整個模式)」的長度,這正是回退迴圈所計算的;完整匹配就是這個長度將會是 的事件。前綴表以回退鏈的形式隱含地儲存轉移,而不必為整個字母表儲存 行轉移。
例題 6.1.7
(不匹配時重用前綴)
對 ,表為 。搜尋 。處理五個文字符號後,;下一個符號是 ,而 。回退至 ,同一個文字符號便能匹配。繼續後找到模式,起始位置為從零計數的 。造成不匹配的文字符號無須從輸入重新讀取。
例題 6.1.8
(邊界情形:全部符號相同,以及比模式短的文字)
取 ,,。讀第一個符號得 ,讀第二個得 ,報告位置 ,並重設為 。之後每個符號又把 升到 ,分別報告位置 與 。互相重疊的出現位置是 。
若 為空或比 短,任何符號序列都不可能使 達到 ,掃描以 步不報告任何位置;表仍以 建成。
反例模式
重設為零可能丟失匹配
在 中,模式 出現在位置 和 。第一次匹配後, 保留最後的 作為下一個候選的起點;若改為重設至零,便會丟失重疊的出現:接著讀入的 只令 ,掃描結束時並沒有報告位置 。
為何總工作量是線性
定理 6.1.9
(線性運行時間)
若相等測試為常數成本,建表需 時間,掃描文字需 時間,總運算量為 。表佔 空間。
證明
(以 q 為勢能作攤還分析)
掃描文字時,每個符號最多令 增加一次;每次回退都嚴格減少 ,而 不會變成負數。因此回退總次數不超過增加的總次數,為 ;報告後的重設是多一次減少。建表同理,對值 ,每個模式位置最多增加一次,故需 。表有 項。
若儲存全部 個報告位置,輸出需要 空間;逐個輸出便不需該儲存量。此界把符號相等測試視為常數成本;若記號本身是長字串或結構化對象,須另計比較成本。算法處理精確相等匹配,不處理近似或語意相似。
常見錯誤
常見錯誤
(回退到 q 處的表項,而不是 q 減一處的表項)
回退使用的是 ,即長度 的已匹配前綴的邊界,而不是 。在用 搜尋 時,不匹配發生在 。正確值是 。若用 ,便掉到 ,其餘符號 再也無法重建前綴,位置 的出現就漏掉了。
常見錯誤
(把整個前綴也算作邊界)
邊界必須是真前綴。若表允許整個前綴,則對 表會是 。匹配之後重設 , 仍等於模式長度,下一次比較就會讀取模式之外的 ;而每次回退 也永遠不會令 減少。
練習
快速檢查
(求 的 。)
求前綴 、、、 各自的最長邊界。
解答 · 答案
表為 :每個前綴的最長真邊界都比它少一個末尾符號。
快速檢查
(列出 在 中所有從零計數的位置,並給出第一次匹配後的重設值。)
此模式的 。
解答 · 答案
位置為 ;第一次匹配後重設為 。
快速檢查
(當 且文字符號與 不同時,該符號如何處理?)
想一想有哪個非空模式前綴能以該符號結尾。
解答 · 答案
沒有非空前綴能以該符號結尾,故 保持零,掃描前進至下一個符號。
快速檢查
(為何一次很長的回退鏈不會令整次掃描變成二次時間?)
把 看成必須先賺取才能花費的量。
解答 · 答案
每次回退都減少非負的 ;整次掃描中的減少次數受先前增加次數限制,而每個文字符號最多令其增加一次。