基于雙數組的AC比對算法學習
0. 前言
閱讀本文之前，你需要了解KMP算法的原理以及AC自動機的相關概念。
1. AC算法
1.1. AC算法簡述
AC算法基于有限狀态自動機，在進行串比對之前，先對模式串集合進行預處理，得到樹形有限自動機，然後隻需對文本進行一次掃描，便可以找到所有比對成功的模式串。
例如以模式串集合P{she, he, her, him, hers, his}為例，建構樹形狀态轉移自動機。
其中圓圈對應自動機的各個狀态，邊對應目前狀态輸入的字元。
1.2. AC與KMP的比較
AC多模式串比對算法的思想與KMP算法有相通之處。AC算法從某種程度上可以說是KMP算法在多模式環境下的擴充。KMP算法比普通的字元比較方法的優點在于目标串不需要回溯，模式串回溯的距離盡可能小。從這句話可以看出，KMP算法需要解決模式串回溯的問題，也就說需要一個next數組來存儲模式串中每個位置比對失配之後，模式串目前的比較下标需要回溯的位置。AC算法也是這個思想，當比較到某個字元串的某個位置失配時，需要決定目标串的目前比較字元與模式串中的哪個字元串的哪個位置進行比較。是以，我們可以在這裡引入一個狀态轉移矩陣，矩陣的行向量表示為若幹個狀态（具體有多少狀态，取決于模式串的個數和各模式串的内部結構），矩陣的列向量表示為模式串中出現的所有字元，則具體某一個(i, j)元表示在狀态為j的情況下，遇到一個字元i，所轉移到的下一個狀态的取值。
1.3. AC中的三個函數
AC算法的整個過程中需要實作三個函數：轉移函數、輸出函數、失敗函數。
1.3.1. 轉移函數
顧名思義，轉移函數實作的就是狀态轉移。我們設轉移函數為t=goto(s, c)，表示當狀态s遇到一個字元c後轉移為狀态t。若狀态s不存在一條标記為c的有向邊，則傳回為-1，表示狀态轉移失敗。
1.3.2. 輸出函數
輸出函數與每個狀态對應，表示比對到某個狀态後，輸出比對成功的模式串。用output(s)表示，其中s為狀态。output(s)在這裡實作的相當于是狀态和模式串之間的映射。是以，我們可以在比對的過程中，對每個狀态進行查詢，看是否有比對成功的模式串，若有，則輸出。
1.3.3. 失敗函數
失敗函數也與每個狀态對應，表示輸入字元在目前狀态比對失敗時所轉移到的新的狀态。用fail(s)表示，其中s為狀态。
1.3.4. 典型的AC算法僞代碼
s = INIT_STATE;
while (scanf(“%c”, &ch) != ch)
{
t = g(s, ch);
while (invalid(t))
{
s = fail(s);
t = g(s, ch);
}
output(t);
}
2. 基于雙數組trie樹的AC算法
2.1. 雙數組trie樹與AC算法的關系
從前面知道，AC算法需要三個函數來進行字元串比對，而且這三個函數的求解都和一個确定的DFA（有限狀态自動機）有關，那麼我們必須得先求出這樣一個DFA才行。DFA為一個樹形結構，是以我們考慮用trie樹來表示DFA，而且我們還得保證TRIE樹檢索速度的前提下，提高空間使用率，是以最終我們用基于雙數組的trie樹來存儲DFA。
2.2. trie樹
又稱單詞查找樹，Trie樹，是一種樹形結構。所有含有公共字首的字元串将挂在樹中同一個結點下。實際上trie簡明的存儲了存在于串集合中的所有公共字首。利用字元串的公共字首來減少查詢時間，最大限度地減少無謂的字元串比較。字典樹trie 搜尋關鍵碼的時間和關鍵碼自身及其長度有關，最快是0(1)，即在第一層即可判斷是否搜尋到，最壞的情況是0(n), n為Trie樹的層數。由于很多時候Trie樹的大多數結點分支很少，是以Trie樹結構空間浪費比較多。Trie樹是搜尋樹的一種，它在本質上是一個确定的有限狀态自動機DFA，每個結點代表一個狀态，根據輸入變量的不同，進行狀态轉移。
通常，一個DFA是用一個transition table表示，它的行對應狀态s，它的列對應轉換标簽s。每一個單元中的資料當輸入與标記相同時，給定一個狀态後要到達的狀态。
這是一個的周遊高效方法，因為每次轉換可以通過計算二維的數組索引得到。但是，從空間使用的角度看，這是相當浪費的，因為，在trie這種情況中，大多數結點隻有少量的分枝，表中大多數單元是空白的。同時，一個更緊湊的方式是用連結清單儲存每個狀态的轉移，但這種方式會比較慢，因為要進行線性搜尋。
是以，建議使用可以快速通路的表壓縮技術。
2.3. 基于雙數組的trie樹
雙數組Trie（Double-Array Trie）是trie樹的一個簡單而有效的實作，由兩個整數數組構成，一個是base[]，另一個是check[]。base和check數組擁有一緻的下标，（下标）即DFA中的每一個狀态，也即TRIE樹中所說的節點，base數組中的每個元素存儲的是一個偏移量，用來計算下一個狀态t，即t = base[s] + c，s為目前狀态，base[s]為狀态s的偏移量，c為輸入字元，check數組用于檢驗轉移的正确性。是以，從狀态s輸入c到狀态t的一個轉移必須滿足如下條件：
若 base[s] + c == t，則check[t] == s。
由上述可知，構造基于雙數組的trie樹，關鍵在于求得每個狀态的base[s]值。
2.4. 建構雙數組trie樹
假設模式串集合中所有字元對應的序列碼為：
e=1, h=2, i=3, m=4, r=5, s=6
1).初始時base數組和check數組全為0，下标為0的狀态不使用。下标為1的狀态為初始狀态。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| base | |||||||||||||||||
| check |
2).引入函數q = x_check(char *str, int len)用來求出一個最小的正整數q滿足對于字元串str中所有字元’c’有,CHECK[q+c] = 0，即尋找一個合适的偏移量，使得可以容納所有可能出現的子節點。
3).插入可以分為3種情況：
case 1:當雙數組trie為空時，插入模式串。
case 2:雙數組trie不為空，插入時沒有出現沖突。
case 3:雙數組trie不為空，插入時出現沖突。
是以，在插入的過程中需要對這三種情況分别做處理。
4).插入過程的僞代碼：
for str in p{str1, str2, …} //依次取出每一個模式串。
{
s = 1; //設s為初始狀态
i = 0;
while (str[i])
{
if (base[s] == 0)
{
base[s] = x_check(str + i, 1);
}
t = base[s] + str[i];
if (check[t] == s)
{
; //字元str[i]為公共字首，且已插入trie樹中。
} else if (check[t] == 0)
{
check[t] = s; //沒有出現沖突，直接插入
} else //插入時出現沖突
{
m = check[t];
//此時需要确定check[t]最終是由m占據，還是s占據？
//這取決于移動m和s各自的所有子節點所花費的工作量，取工作量較小者移動
//這裡以移動m為例
if (child_count(m) < child_count(s) + 1)
//重新确定狀态m的base[m]，并移動m的所有子節點
{
old_base=base[m];
base[m] = x_check(child_str(m), child_count(m));
for i in child_str(m)
{
d=old_base + i;
base[base[m] + i] = base[d];
check[base[m] + i] = m;
for j in child_str(d)
{
check[base[d] + j] = base[m] + i;
}
base[d] = 0;
check[d] = 0;
}
} else //重新确定狀态s的base[s]，并移動s的所有子節點
{
//同移動m類似
}
check[t] = s;
}
s = t;
++i;
}
}
4).對于模式串中的第1個字元串”she”，設目前狀态s為初始狀态，即s=1。
首字元為’s’，計算base[s]=q=x_check(“s”, 1)，得base[s]=1，由base[s]+ ’s’=t=7, check[7]=0,表示狀态7可用，則check[7]=1，轉移目前狀态s=t;
第2個字元為’h’, 計算base[s]=q=x_check(“h”, 1)，得base[s]=1，由base[s] + ‘h’=t=3, check[3]=0,表示狀态3可用，則check[3]=7，轉移目前狀态s=t;
第3個字元為’e’，計算base[s]=q=x_check(“e”，1)，得base[s]=1，由base[s] + ‘e’=t=2, check[t]=0,表示狀态2可用，則check[2]=3;
插入字元串“she”後，雙數組中的值為：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| base | 1 | 1 | 1 | ||||||||||||||
| check | 3 | 7 | 1 |
5).對于模式串中的第2個字元串”he”，設目前狀态s為初始狀态，即s=1。
首字元為’h’，由base[s] + ‘h’=t=3,check[3]=7≠1，表示遇到沖突，狀态s=1有2個節點(’s’,’h’)，狀态check[t]=7有1個節點(‘h’)，是以需要移動狀态7的所有子節點，并轉移目前狀态s=t，移動後雙數組中的值為:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| base | 1 | 1 | 2 | ||||||||||||||
| check | 4 | 1 | 7 | 1 |
第2個字元為’e’，計算base[s]=q=x_check(“e”, 1)，得base[s]=4，由base[s] + ‘e’=t=5，check[t]=0,表示狀态5可用，則check[5]=3;
6).對于模式串中的第3個字元串“her”，設目前狀态s為初始狀态，即s=1。
對于前兩個字元’h’、’e’，都不用插入；
對于第3個字元’r’，目前狀态為s=5，計算base[s]=q=x_check(“r”, 1)，得base[s]=1，由base[s]+’r’=t=6，check[6]=0,表示狀态6可用，則check[6]=5;
插入字元串“her”後，雙數組中的值為：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| base | 1 | 4 | 1 | 1 | 2 | ||||||||||||
| check | 4 | 1 | 7 | 3 | 5 | 1 |
7).按照4)中給出的算法依次插入剩下的所有字元串。
2.4. goto函數的實作
建構好了雙數組，goto函數的實作就簡單多了。
int goto_foo(int s, char c)
{
int t = base[s] + c;
if (check[t] == s)
{
return t;
}
return -1;
}
2.5. fail函數和output函數的實作
首先明确一點，建構雙數組trie是為了快速、高效的實作狀态轉移函數t=goto(s,c)。但我們還得實作fail函數和output函數，實作的思想和KMP算法構造next的思想有異曲同工之妙。具體描述，可參考《再談AC算法》。
回想在KMP中如何構造next數組？我們知道在KMP算法中，是通過回溯的方法來求next值的，也就是目前位置（對應一個字元）的next值是通過前一個位置的next值和目前字元這兩個元素來決定，就是前一個位置的next值所對應的字元是否和目前字元相等，若相等則目前位置的next為前一個位置的next值加1，若不相等，則目前字元回溯比較前一個位置的next值所對應的位置的next值所對應的字元（有點繞），依次類推，直到比較到第1個位置。
同理，在trie樹中求fail值，也需要通過回溯的方法來求。若要求目前狀态的fail值，同樣我們需要兩個值，一個是前一個狀态的fail值，另一個是前一個狀态轉移到目前狀态的輸入字元。目前狀态失配後，我們需要得到前一個狀态的fail值。（在樹形結構中，前一個狀态即為父節點所對應的狀态。）然後我們檢視輸入字元在前一個狀态的fail值所對應的狀态下是否可以轉移，若可以則傳回轉移後的結果，若不可以，則通過回溯的方法繼續對更前一個狀态進行檢視，直到回溯到初始狀态。
即若goto(m, c)=n, 則fail[n]的計算方法為：
int fail(int m, char c)
{
int p = fail[m];
while (p != 1 && goto_foo(p, c) == -1) //1為初始狀态
{
p = fail[p];
}
if (goto_foo(p, c) == -1)
{
return 1;
}
return goto_foo(p, c);
}
若求得fail[n]的值不為1（初始狀态），即fail[n]=g(p, c)，則還須将output[p]中比對的模式串，全部加入output[n]中。
從這裡可看出來，在求目前狀态的fail值時，它的前一個狀态（父節點）的fail值必須先求出來，是以我們可以通過BFS的方法來實作。首先，令trie樹中的第一層節點的fail值都為1，并依次入隊列，這相當于初始化。然後，依次取出每一個節點m，計算m的所有子節點n的fail值，如果節點n還有子節點，則将節點n入隊列，直到隊列為空。
3.參考資料
- http://blog.csdn.net/nocml/article/details/6880154
- http://blog.sina.com.cn/s/blog_5cf4a61d0100yemd.html
- http://blog.csdn.net/zhoubl668/article/details/6957830
- http://my.oschina.net/amince/blog/222806?fromerr=5pVdTyDG
- http://ansjsun.iteye.com/blog/702255
- http://linux.thai.net/~thep/datrie/datrie.html
- http://blog.csdn.net/maotianwang/article/details/34559755
- http://blog.csdn.net/joylnwang/article/details/6793192
- http://blog.csdn.net/joylnwang/article/details/6884450
- http://www.hankcs.com/program/algorithm/aho-corasick-double-array-trie.html
![資料結構與算法：34 | 字元串比對（下）：KMP算法[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)