模式匹配自動機全面理論分析

模式匹配是什么

模式匹配是計算機科學中一個基礎且重要的問題，廣泛應用于文本編輯、信息檢索、網絡安全、生物信息學等多個領域。簡單來說，模式匹配就是在一個主文本中查找一個或多個特定模式串的出現位置。隨著計算機處理能力的提升和數據規模的擴大，高效的模式匹配算法變得尤為重要。

常見模式匹配算法

BF 模式匹配算法

算法原理

BF 算法（Brute Force Algorithm），也稱為暴力匹配算法或樸素匹配算法，是最基礎、最簡單的字符串匹配方法。其基本思想是：從主文本的第一個字符開始，與模式串的第一個字符進行比較，如果相等，則繼續逐個比較后續字符；如果不相等，則將主文本的比較位置回退到起始位置的下一個字符，模式串的比較位置重置為起始字符，重新開始比較。?
BF 算法的設計思想非常直觀，沒有任何技巧，就是簡單粗暴地將主文本和模式串中的字符一一比對，直到找到匹配的位置或遍歷完整個主文本。這種算法的匹配順序是按照模式串的下標從小到大的順序，依次與主文本中的字符進行匹配的。

算法流程

BF 算法的具體步驟如下：?

初始化兩個指針 i 和 j，分別指向主文本和模式串的起始位置（通常為 0）。?
進入循環，當 i 小于主文本長度且 j 小于模式串長度時：?

a. 如果主文本第 i 個字符與模式串第 j 個字符相等，則 i 和 j 都向后移動一位。
?b. 如果不相等，則將 i回退到起始位置的下一個字符（即 i = i - j + 1），j 重置為 0。?

當 j 等于模式串長度時，說明匹配成功，返回 i - j 作為匹配的起始位置。?
如果循環結束后仍未找到匹配，則返回 - 1 表示匹配失敗。

RK 模式匹配算法

算法原理

RK 算法（Rabin-Karp Algorithm）由 Michael O. Rabin 和 Richard M. Karp 發明，它使用哈希技術來快速找到可能的匹配位置，然后再進行字符比較驗證。RK 算法基于 BF 算法進行優化，利用哈希算法將主文本中的 n-m+1 個子串分別求哈希值，然后利用哈希值進行比較，這樣省去了逐個字符比較的時間。
RK 算法的核心思想是：

計算模式串的哈希值。
計算主文本中每個與模式串長度相同的子串的哈希值。
比較模式串哈希值與子串哈希值，若相等則進行字符級比較驗證。
若驗證通過，則找到匹配位置；否則繼續檢查下一個子串。

滾動哈希技術

RK 算法的關鍵在于使用滾動哈希（Rolling Hash）技術，將每次計算子串哈希值的時間復雜度從 O (m) 降到了 O (1)，從而提升了整個算法效率。滾動哈希算法利用了子串中每一位字符的哈希值，并且可以根據上一個子串的哈希值，快速計算相鄰子串的哈希值。

假設主文本為 T，模式串為 P，長度分別為 n 和 m。滾動哈希的基本原理如下：

選擇一個基數 d（通常取字符集大小，如 26）和一個大質數 q（用于取模防止溢出）。
模式串 P 的哈希值計算方式為：

Hash(P) = P_0 × d^(m-1) + P_1 × d^(m-2) + … + P_{m-1} × d^0

主文本中起始于位置 i 的子串 T [i…i+m-1] 的哈希值可以通過前一個子串的哈希值計算得到：

Hash(T[i+1..i+m]) = [Hash(T[i..i+m-1]) - T[i] × d^(m-1)] × d + T[i+m]

每次計算新的哈希值時，都需要對結果取模 q，以防止數值過大。

哈希碰撞

在 RK 算法中，使用滾動哈希技術存在潛在的 “失誤” 可能，其核心原因是哈希碰撞（Hash Collision）

哈希函數的基本特性是將任意長度的輸入（如字符串）映射到一個固定范圍的輸出（如取模后的整數）。由于可能的輸入（子串）數量遠大于輸出范圍（0 到 q-1），根據 “鴿巢原理”，必然存在不同的子串被映射到相同的哈希值 —— 這就是哈希碰撞。

算法流程

RK 算法的具體步驟如下：?

計算模式串 P 的哈希值 hash_p。?
計算主文本 T 中第一個子串（長度為 m）的哈希值 hash_t。?
計算 d^(m-1) mod q，用于后續哈希值的更新。?
遍歷主文本中所有可能的子串起始位置 i（從 0 到 n-m）：?

a. 如果 hash_p == hash_t，進行字符級比較驗證。?
b. 如果驗證通過，返回 i 作為匹配起始位置。?
c. 如果 i < n-m，計算下一個子串的哈希值：

hash_t = (hash_t - ord(T[i]) × power) % q
hash_t = (hash_t × d + ord(T[i + m])) % q
hash_t = (hash_t + q) % q  # 確保hash_t為非負數

如果遍歷結束仍未找到匹配，返回 - 1。

KMP 模式匹配算法

算法原理

KMP 算法（Knuth-Morris-Pratt Algorithm）由 Donald Knuth、Vaughan Pratt 和 James H. Morris 共同發明，它能夠快速地在一個文本串中查找一個模式串，特別是在模式串較長或在一個文本串中多次查找時表現出色。KMP 算法的核心思想是利用已經匹配過的信息，避免不必要的回溯，從而提高匹配效率。?
KMP 算法與 BF 算法的 “開局” 是一樣的，同樣是把主文本和模式串的首位對齊，從左到右逐個字符進行比較。當遇到不匹配的字符時，KMP 算法不是將主文本指針回溯，而是通過一個部分匹配表（也稱為失敗函數或 next 數組）來確定模式串應該滑動多遠，從而避免了主文本指針的回溯。

部分匹配表（next 數組）

KMP 算法的關鍵在于構建部分匹配表（next 數組）。next 數組是一個一維整型數組，數組的下標代表了 “已匹配前綴的下一個位置”，元素的值則是 “最長可匹配前綴子串的下一個位置”。?
構建 next 數組的步驟如下：

初始化 next 數組，next [0] = -1，j = -1，i = 0。
當 i < m（m 為模式串長度）時：
a. 如果 j == -1 或模式串 [i] == 模式串 [j]，則 i++，j++，next [i] = j。?
b. 否則，j = next [j]。

next 數組的意義在于：當模式串在位置 i 處與主文本不匹配時，模式串應該回退到 next [i] 的位置繼續匹配，而不是從頭開始。

舉個例子：模式串 “ABCDABD” 的 next 數組計算過程：

模式串索引	字符	前 i 個字符的子串	最長公共前后綴	next[i]
0	A	無（長度 0）	無	-1
1	B	“A”	無	0
2	C	“AB”	無	0
3	D	“ABC”	無	0
4	A	“ABCD”	無	0
5	B	“ABCDA”	前綴 “A” 和后綴 “A” → 長度 1	1
6	D	“ABCDAB”	前綴 “AB” 和后綴 “AB” → 長度 2	2

主文本：A B C A B C D A B A B C D A B C D A B D E
模式串：A B C D A B D（next 數組：[-1,0,0,0,0,1,2]）

具體過程：

前 4 位：AA→BB→CC→DD，i=4，j=4。
第 5 位：主文本是A，模式串j=4是A→匹配，i=5，j=5。
第 6 位：主文本是B，模式串j=5是B→匹配，i=6，j=6。
第 7 位：主文本是C，模式串j=6是D→不匹配！
→ 此時查next[6]=2，所以j=2（模式串回退到索引 2 的C）。
現在i=7（主文本沒動），j=2：主文本C vs 模式串C→匹配，i=8，j=3。
繼續往后比對，直到j等于模式串長度（7），說明找到匹配，返回i-j（起始位置）。

算法流程

KMP 算法的具體步驟如下：

預處理模式串，構建 next 數組。?
初始化主文本指針 i = 0，模式串指針 j = 0。?
當 i < n（n 為主文本長度）時：
a. 如果 j == -1 或主文本 [i] == 模式串 [j]，則 i++，j++。?
b. 否則，j = next [j]。
如果 j == m，說明找到匹配，返回 i - j 作為起始位置。?
如果遍歷結束仍未找到匹配，返回 - 1。

BM 模式匹配算法

算法原理

BM 算法（Boyer-Moore Algorithm）由 Robert S. Boyer 和 J Strother Moore 發明，它采用從主文本的尾部開始匹配的策略，并在不匹配時利用兩個啟發式規則（壞字符規則和好后綴規則）來移動模式串，從而提高匹配效率。?
與 BF 和 KMP 算法從左到右進行比較不同，BM 算法采用從右向左比較的方法，這是其效率高的關鍵原因之一。BM 算法的基本思想是：當發現某個字符不匹配時，利用壞字符規則和好后綴規則來決定模式串向右移動的距離，盡可能多地跳過那些肯定不會匹配的情況。

壞字符規則

壞字符規則（Bad Character Rule）是 BM 算法的第一個啟發式規則。當從右向左比較時，發現某個字符無法匹配，這個不匹配的字符稱為壞字符（主文本中的字符）。?
壞字符規則的處理步驟如下：

計算壞字符在模式串中的位置（最右出現位置）。?
如果壞字符在模式串中不存在，則將模式串向右移動整個長度。?
如果壞字符存在，則將模式串向右移動，使壞字符的位置與主文本中的壞字符對齊。

數學公式表示：設 Skip (x) 為模式串右移的距離，m 為模式串長度，max (x) 為字符 x 在模式串中最右位置，則：

Skip(x) = {m,                當x不在模式串中時m - 1 - max(x),   當x在模式串中時
}

好后綴規則

好后綴規則（Good Suffix Rule）是 BM 算法的第二個啟發式規則。當發現某個字符不匹配時，已經匹配的后綴部分稱為好后綴。?
好后綴規則的處理步驟如下：

如果在模式串中存在另一個與好后綴相同的子串，則將模式串向右移動，使這兩個子串對齊。
如果在模式串中找不到與好后綴相同的子串，則找到與好后綴的后綴子串相同的模式串最長前綴，將模式串移動到相應位置。

數學公式表示：設 Shift (j) 為模式串右移的距離，m 為模式串長度，j 為當前匹配的字符位置，s 為移動距離，則：

Shift(j) = min{s | (P[j+1..m] = P[j-s+1..m-s]) && (P[j] ≠ P[j-s]) (j > s),P[s+1..m] = P[1..m] (j ≤ s)
}

算法流程

BM 算法的具體步驟如下：?

預處理模式串，構建壞字符表和好后綴表。?
初始化主文本指針 i = m-1（模式串長度減一）。?
進入循環，當 i < n（n 為主文本長度）時：?

a. 從模式串的末尾開始，從右向左比較主文本和模式串的字符。?
b. 如果所有字符都匹配，返回 i - m + 1 作為起始位置。?
c. 如果發現不匹配，計算壞字符規則的移動距離 skip_bad 和好后綴規則的移動距離 skip_good。?
d. 將模式串向右移動 max (skip_bad, skip_good) 位，即 i += max (skip_bad, skip_good)。?

如果循環結束仍未找到匹配，返回 - 1。

AC 自動機多模式匹配算法

算法原理

AC 自動機（Aho-Corasick Algorithm）是一種高效的多模式匹配算法，由 Alfred V. Aho 和 Margaret J. Corasick 發明。AC 自動機基于 Trie 樹（前綴樹）和 KMP 算法的失配指針（失敗指針），能夠在一次掃描中同時匹配多個模式串，特別適合處理大量模式串的匹配問題。
AC 自動機的核心思想是：

將所有模式串構建成一個 Trie 樹結構，共享公共前綴以節省空間。?
為 Trie 樹的每個節點構建失配指針，類似于 KMP 算法的 next 數組，用于在匹配失敗時進行回退。?
通過一次遍歷主文本，同時匹配所有模式串，利用失配指針高效地處理不匹配的情況。

Trie 樹構建

AC 自動機的第一步是構建 Trie 樹（前綴樹）來存儲所有模式串。構建過程如下：

創建根節點。?
對于每個模式串，從根節點開始，逐個字符插入到 Trie 樹中。?
相同的前綴共享節點，不同的分支表示不同的字符路徑。
在每個模式串的結尾節點記錄該模式串的信息（如模式串的索引或內容）。

例如，對于模式集合 {“he”, “she”, “his”, “hers”}，構建的 Trie 樹如下：

根節點
├─ h
│  ├─ e (標記"he")
│  └─ i
│     └─ s (標記"his")
└─ s└─ h├─ e (標記"she")└─ r└─ s (標記"hers")

失配指針構建

AC 自動機的第二步是構建失配指針（失敗指針），類似于 KMP 算法的 next 數組，但更為復雜，因為需要處理多模式的情況。構建過程如下：

使用廣度優先搜索（BFS）遍歷 Trie 樹。?
根節點的失配指針指向自身。?
對于每個節點的子節點，找到其父節點的失配指針，然后沿著該失配指針向上查找，直到找到一個節點有對應的子節點，或者回到根節點。?
將當前子節點的失配指針指向找到的節點。?
同時，將失配指針路徑上的所有輸出模式串合并到當前節點，以便在匹配失敗時能夠找到所有可能的匹配模式。

例如，對于上述 Trie 樹，各節點的失配指針如下：

h 節點的失配指針指向根節點。?
he 節點的失配指針指向根節點。?
his 節點的失配指針指向 s 節點。?
she 節點的失配指針指向 he 節點。?
hers 節點的失配指針指向 his 節點。

模式匹配過程

AC 自動機的第三步是對主文本進行匹配，過程如下：

初始化當前節點為根節點。?
遍歷主文本的每個字符：?

a. 沿著當前節點的子節點查找與當前字符匹配的節點。?
b. 如果找到匹配節點，移動到該節點。?
c. 如果未找到匹配節點，沿著失配指針回溯，直到找到匹配節點或回到根節點。?
d. 檢查當前節點及其失配路徑上的所有輸出模式串，記錄匹配結果。?

遍歷結束后，返回所有找到的匹配位置。

Wu-Manber 多模式匹配算法

算法原理

Wu-Manber 算法是一種高效的多模式匹配算法，由吳升（Sun Wu）和 Udi Manber 發明。Wu-Manber 算法基于 BM 算法的思想，采用哈希的方式以及 BM 算法中的壞字符規則達到快速檢索、跳躍式步進的效果。Wu-Manber 算法特別適合處理大量模式串的匹配問題，在許多情況下性能優于 AC 自動機。
Wu-Manber 算法的核心思想是：

預處理所有模式串，構建三個關鍵表：SHIFT 表、HASH 表和 PREFIX 表。?
使用塊字符（多個連續字符）作為比較單位，而不是單個字符，提高匹配效率。?
在掃描主文本時，根據當前塊字符的哈希值查找 SHIFT 表，決定模式串的移動距離，盡可能多地跳過不可能匹配的位置。?
當需要驗證可能的匹配時，使用 HASH 表和 PREFIX 表快速縮小候選模式串集合，減少不必要的比較。

預處理階段

Wu-Manber 算法的預處理階段主要構建三個表：

1. SHIFT 表：

SHIFT 表用于記錄每個可能的字符塊在模式串中出現的最右位置，從而確定當該字符塊出現在主文本中時，模式串應該移動的距離。?
構建步驟：?
a. 確定所有模式串中最短模式串的長度 m。?
b. 選擇塊長度 B（通常取 2 或 3），根據字符集大小和模式串數量確定。?
c. 對每個模式串的前 m 個字符，提取所有長度為 B 的子串。?
d. 對每個子串 Bl，計算其在模式串中出現的最右位置 j，設置 SHIFT [Bl] = m - j。?
e. 對于未出現在任何模式串中的塊，設置 SHIFT [Bl] = m - B + 1。

2. HASH 表：?

HASH 表用于存儲每個塊 Bl 對應的模式串列表，這些模式串的末尾 B 個字符等于 Bl。?
構建步驟：?
a. 對每個模式串，提取其最后 B 個字符作為塊 Bl。?
b. 計算 Bl 的哈希值 h，將該模式串添加到 HASH [h] 的列表中。?
c. 對 HASH 表進行排序，以便快速查找。

3. PREFIX 表：?

PREFIX 表用于存儲每個模式串前 B’ 個字符（通常 B’=2）的哈希值，用于進一步縮小候選模式串集合。?
構建步驟：?
a. 對每個模式串，提取其前 B’ 個字符作為前綴。?
b. 計算前綴的哈希值，存儲在 PREFIX 表中，與對應的模式串關聯。

匹配過程

Wu-Manber 算法的匹配過程如下：?

初始化主文本指針 i = 0。?
當 i ≤ n - m 時（n 為主文本長度，m 為最短模式串長度）：?
a. 提取主文本中位置 i 到 i+B-1 的塊 Bl。?
b. 計算 Bl 的哈希值 h。?
c. 查找 SHIFT [h]：?

     如果 SHIFT [h] > 0，將 i 增加 SHIFT [h]。?如果 SHIFT [h] = 0，執行以下步驟：

  		i. 提取主文本中位置 i 到 i+m-1 的子串 T。?ii. 計算 T 的前 B' 個字符的哈希值 hp。?iii. 查找 HASH [h] 中的所有模式串，檢查其 PREFIX 值是否等于 hp。?iv. 對匹配 PREFIX 的模式串，逐個與 T 進行完整比較，記錄匹配結果。?v. 將 i 增加 1（因為 SHIFT [h]=0 時，必須逐個檢查每個可能的起始位置）。

返回所有找到的匹配位置。

算法比較與總結

下表總結了六種模式匹配算法的時間復雜度、空間復雜度和適用場景：

算法	時間復雜度（平均）	時間復雜度（最壞）	空間復雜度	適用場景
BF	O(n+m)	O(n×m)	O(1)	小規模文本，簡單場景
RK	O(n+m)	O(n×m)	O(1)	中等規模文本，哈希沖突少
KMP	O(n+m)	O(n+m)	O(m)	長文本，單模式匹配
BM	O(n)	O(n×m)	O(s+m)	長文本，單模式匹配
AC 自動機	O(n+z)	O(n×m)	O(k)	多模式匹配，固定模式集合
Wu-Manber	O(n+z)	O(n×m)	O(k+s^B)	多模式匹配，動態模式集合

算法設計思想比較

從設計思想上看，這六種算法代表了不同的優化策略：?

暴力匹配： BF 算法是最基礎的暴力匹配方法，沒有任何優化，直接逐個字符比較。RK 算法通過哈希技術優化了比較過程，但本質上仍屬于暴力匹配的范疇。?
避免回溯： KMP 算法通過部分匹配表（next 數組）避免了主文本指針的回溯，從而提高了效率。BM 算法則通過從右向左比較和壞字符規則，減少了不必要的比較次數。?
多模式匹配： AC 自動機和 Wu-Manber 算法專門針對多模式匹配問題設計。AC 自動機基于 Trie 樹和失配指針，能夠在一次掃描中匹配多個模式串；Wu-Manber 算法則基于 BM 算法的思想，使用哈希表和塊字符技術提高匹配效率。?
空間換時間： RK 算法使用哈希值比較代替字符比較，KMP 算法使用 next 數組存儲預處理信息，AC 自動機使用 Trie 樹存儲模式串，Wu-Manber 算法使用三個預處理表，都是以空間換取時間效率的優化策略。