AC自動機
AC自動機：Aho-Corasick automation，該算法在1975年產(chǎn)生于貝爾實驗室，是著名的多模匹配算法之一。一個常見的例子就是打游戲聊天時，你說的一些銘感詞會變成‘*’。要搞懂AC自動機，先得有模式樹（字典樹）Trie和KMP模式匹配算法的基礎(chǔ)知識。KMP算法是單模式串的字符匹配算法，AC自動機是多模式串的字符匹配算法。
基于單模式串和Trie樹實現(xiàn)的敏感詞過濾
字符串匹配算法中：BF算法、RK算法、BM算法、KMP算法 是單模式串匹配算法。 而 Trie樹是多模式串匹配算法。
單模式串匹配算法：是在一個模式串和一個主串之間進行匹配，也就是說，在一個主串中查找一個模式串。
多模式串匹配算法：是在多個模式串和一個主串之間做匹配，也就是說，在一個主串中查找多個模式串。
盡管，單模式串匹配算法也能完成多模式串的匹配工作。但是效率是比較低的。
如：我們可以針對每個敏感詞，通過單模式串匹配算法(比如KMP算法)與用戶輸入的 文字內(nèi)容進行匹配。但是，這樣做的話，每個匹配過程都需要掃描一遍用戶輸入的內(nèi)容。整個過程下來就要掃描很多遍用戶輸入的內(nèi)容。如果敏感詞很多，比如 幾千個，并且用戶輸入的內(nèi)容很長，假如有上千個字符，那我們就需要掃描幾千遍這樣的輸入內(nèi)容。很顯然，這種處理思路比較低效。
與單模式匹配算法相比，多模式匹配算法在這個問題的處理上就很高效了。它只需要掃描一遍主串，就能在主串中一次性查找多個模式串是否存在，從而大大提 高匹配效率。我們知道，Trie樹就是一種多模式串匹配算法。那如何用Trie樹實現(xiàn)敏感詞過濾功能呢?
我們可以對敏感詞字典進行預(yù)處理，構(gòu)建成Trie樹結(jié)構(gòu)。這個預(yù)處理的操作只需要做一次，如果敏感詞字典動態(tài)更新了，比如刪除、添加了一個敏感詞，那我們只 需要動態(tài)更新一下Trie樹就可以了。
當(dāng)用戶輸入一個文本內(nèi)容后，我們把用戶輸入的內(nèi)容作為主串，從第一個字符(假設(shè)是字符C)開始，在Trie樹中匹配。當(dāng)匹配到Trie樹的葉子節(jié)點，或者中途遇 到不匹配字符的時候，我們將主串的開始匹配位置后移一位，也就是從字符C的下一個字符開始，重新在Trie樹中匹配。
基于Trie樹的這種處理方法，有點類似單模式串匹配的BF算法。單模式串匹配算法中，KMP算法對BF算法進行改進，引入了next數(shù)組，讓匹配失敗 時，盡可能將模式串往后多滑動幾位。想借鑒單模式串的優(yōu)化改進方法，對多模式串Trie樹進行改進，進一步提高Trie樹的效率，這就需要AC自動機了。
AC自動機節(jié)點定義
public static class AcTrieNode {
public char data;
public AcTrieNode[] children = new AcTrieNode[26];// 字符集只包含 a-z 26個英文字母
public boolean isEndingChar = false; //結(jié)尾字符標(biāo)識
public int length = -1; //當(dāng)isEndingChar 為 true 時， 記錄模式串長度
public AcTrieNode fail;// 失敗指針
public AcTrieNode(char data) {
this.data = data;
}
}
Trie樹跟AC自動機之間的關(guān)系，就像單串匹配中樸素的串匹配算法，跟KMP算法之間的關(guān)系一樣，只不過前者針對的是多模式串而已。所以，AC自動機實際上就是在Trie樹之上，加了類似KMP的next數(shù)組，只不過此處的next數(shù)組是構(gòu)建在樹上罷了。
AC自動機的構(gòu)建，包含兩個操作:
將多個模式串構(gòu)建成Trie樹.
在Trie樹上構(gòu)建失敗指針(相當(dāng)于KMP中的失效函數(shù)next數(shù)組)。
AC自動機關(guān)鍵點一：字典樹的構(gòu)建過程
關(guān)于如何構(gòu)建Trie樹點這里
AC自動機關(guān)鍵點二：找Fail指針
在KMP算法中，當(dāng)我們比較到一個字符發(fā)現(xiàn)失配的時候我們會通過next數(shù)組，找到下一個開始匹配的位置，然后進行字符串匹配，KMP算法是用與單模式匹配。
AC自動機,在tire樹的基礎(chǔ)上,增加一個fail指針,如果當(dāng)前點匹配失敗,則將指針轉(zhuǎn)移到fail指針指向的地方,這樣就不用回溯,而可以源路匹配下去了.(當(dāng)前模式串后綴和fail指針指向的模式串部分前綴相同,如abce和bcd,我們找到c,需要c的下一個節(jié)點e,但是e不是我們想要的,就跳到bcd中的c處,看看此處的下一個字符(d)是不是應(yīng)該找的那一個)
例：
這里有4個模式串，分別是c，bc，bcd，abcd;主串是abcd。
計算每個節(jié)點的失敗指針這個過程看起來有些復(fù)雜。其實，如果我們把樹中相同深度的節(jié)點放到同一層，那么某個節(jié)點的失敗指針只有可能出現(xiàn)在它所在層的上
一層。
我們可以像KMP算法那樣，當(dāng)我們要求某個節(jié)點的失敗指針的時候，我們通過已經(jīng)求得的、深度更小的那些節(jié)點的失敗指針來推導(dǎo)。也就是說，我們可以逐層依 次來求解每個節(jié)點的失敗指針。所以，失敗指針的構(gòu)建過程，是一個按層遍歷樹的過程。
假設(shè)節(jié)點p的失敗指針指向節(jié)點q，我們看節(jié)點p的子節(jié)點pc對應(yīng)的字符，是否也可以在節(jié)點q的子節(jié)點中找到。如果找到了節(jié)點q的一個子節(jié)點qc，對應(yīng)的字符 跟節(jié)點pc對應(yīng)的字符相同，則將節(jié)點pc的失敗指針指向節(jié)點qc。
如果節(jié)點q中沒有子節(jié)點的字符等于節(jié)點pc包含的字符，需要找q->fail->fail 這個節(jié)點，直到root為止，如果還沒有找到相同字符的子節(jié)點，就讓節(jié)點pc的失敗指針指向root。
/**
* 構(gòu)建fail指針
*/
public void buildFailurePointer() {
Queue<AcTrieNode> queue = new LinkedList<>();
this.root.fail = null;
queue.add(root);
while (!queue.isEmpty()) {
AcTrieNode p = queue.remove(); // 出隊
for (int i = 0; i < 26; i++) {
AcTrieNode pc = p.children[i];
if (pc == null) {
continue;
}
if (p == root) {
pc.fail = root;
} else {
AcTrieNode q = p.fail;
while (q != null) {
AcTrieNode qc = q.children[pc.data - 'a'];
if (qc != null) {
pc.fail = qc;
break;
}
q = q.fail;
}
if (q == null) {
pc.fail = root;
}
}
queue.add(pc);
}
}
}
假設(shè)我們改變下trie的元素，失敗指針可得到如下圖：
最終4個模式串，c，bc，bcd，abcd;生成的AC自動機圖如下：
AC自動機關(guān)鍵點三：匹配
在匹配過程中，主串從i=0開始，AC自動機從指針p=root開始，假設(shè)模式串是b，主串是a。
如果p指向的節(jié)點有一個等于b[i]的子節(jié)點x，我們就更新p指向x，這個時候我們需要通過失敗指針，檢測一系列失敗指針為結(jié)尾的路徑是否是模式串。這一 句不好理解，你可以結(jié)合代碼看。處理完之后，我們將i加一，繼續(xù)這兩個過程;
如果p指向的節(jié)點沒有等于b[i]的子節(jié)點，那失敗指針就派上用場了，我們讓p=p->fail，找p->fail->fail這個節(jié)點，然后繼續(xù)這兩個過程。
看下實現(xiàn)代碼會更清晰。
/**
* 文本匹配
*
* @param text 輸入的文本
* @return 返回已起始位置為key, 匹配長度為value的map
*/
public Map<Integer, Integer> match(char[] text) {
Map<Integer, Integer> resMap = new HashMap<>();
int n = text.length;
AcTrieNode p = root;
for (int i = 0; i < n; i++) {
int idx = text[i] - 'a';
while (p.children[idx] == null && p != root) {
p = p.fail; // 失敗指針發(fā)揮作用的地方
}
p = p.children[idx];
if (p == null) {
p = root;//如果沒有匹配的，從 root 重新開始
}
AcTrieNode tmp = p;
while (tmp != root) { // 打印出可以匹配的模式串
if (tmp.isEndingChar) {
int pos = i - tmp.length + 1;
System.out.println("匹配起始下標(biāo)" + pos + ";長度" + tmp.length);
resMap.put(pos, tmp.length);
}
tmp = tmp.fail;
}
}
return resMap;
}
時間復(fù)雜度分析
構(gòu)建時間復(fù)雜度
Trie樹
Trie樹構(gòu)建的時間復(fù)雜度是O(mlen)，其中l(wèi)en表示敏感詞的平均長度，m表示敏感詞的個數(shù)。
失敗指針
一個不是很嚴(yán)謹(jǐn)?shù)纳蠈茫僭O(shè)Trie樹中總的節(jié)點個數(shù)是k，每個節(jié)點構(gòu)建失敗指針的時候，(你可以看下代碼)最耗時的環(huán)節(jié)是while循環(huán)中的q=q->fail，每運行一次這個語句，q指向節(jié)點的
深度都會減少1，而樹的高度最高也不會超過len，所以每個節(jié)點構(gòu)建失敗指針的時間復(fù)雜度是O(len)。整個失敗指針的構(gòu)建過程就是O(klen)。 不過，AC自動機的構(gòu)建過程都是預(yù)先處理好的，構(gòu)建好之后，并不會頻繁地更新，所以不會影響到敏感詞過濾的運行效率。
匹配時間復(fù)雜度
for循環(huán)依次遍歷主串中的每個字符，for循環(huán)內(nèi)部最耗時的部分也是while循環(huán)，而這一部分的時間復(fù)雜度也是O(len)，所以總的 匹配的時間復(fù)雜度就是O(n*len)。因為敏感詞并不會很長，而且這個時間復(fù)雜度只是一個非常寬泛的上限，實際情況下，可能近似于O(n)，所以AC自動機做敏感 詞過濾，性能非常高。
從時間復(fù)雜度上看，AC自動機匹配的效率跟Trie樹一樣啊。實際上，因為失效指針可能大部分情況下都指向root節(jié)點，所以絕大部分情況下， 在AC自動機上做匹配的效率要遠(yuǎn)高于剛剛計算出的比較寬泛的時間復(fù)雜度。只有在極端情況下，如圖所示，AC自動機的性能才會退化的跟Trie樹一樣。
小結(jié)
單模式串匹配算法是為了快速在主串中查找一個模式串，而多模式串匹配算法是為了快速在主串中查找多個模式 串。
AC自動機是基于Trie樹的一種改進算法，它跟Trie樹的關(guān)系，就像單模式串中，KMP算法與BF算法的關(guān)系一樣。KMP算法中有一個非常關(guān)鍵的next數(shù)組，類比 到AC自動機中就是失敗指針。而且，AC自動機失敗指針的構(gòu)建過程，跟KMP算法中計算next數(shù)組極其相似。所以，要理解AC自動機，最好先掌握KMP算法，因
為AC自動機其實就是KMP算法在多模式串上的改造。 整個AC自動機算法包含兩個部分，第一部分是將多個模式串構(gòu)建成AC自動機，第二部分是在AC自動機中匹配主串。第一部分又分為兩個小的步驟，一個是將模式串構(gòu)建成Trie樹，另一個是在Trie樹上構(gòu)建失敗指針。
package test;
import java.util.*;
public class AC {
/**
* 節(jié)點
*/
public static class AcTrieNode {
public char data;
public AcTrieNode[] children = new AcTrieNode[26];// 字符集只包含 a-z 26個英文字母
public boolean isEndingChar = false; //結(jié)尾字符標(biāo)識
public int length = -1; //當(dāng)isEndingChar 為 true 時， 記錄模式串長度
public AcTrieNode fail;// 失敗指針
public AcTrieNode(char data) {
this.data = data;
}
}
public static class AcTrie {
private AcTrieNode root = new AcTrieNode('/');
/**
* 插入數(shù)據(jù)生成，Trie樹
*
* @param text
*/
public void insert(char[] text) {
AcTrieNode p = root;
for (char v : text) {
int idx = v - 'a';// 'a' 等于 95 ，'b'-'a' = 1 這里計算出 v 應(yīng)該存儲的索引
if (p.children[idx] == null) { // 該節(jié)點不存在
p.children[idx] = new AcTrieNode(v);
}
p = p.children[idx]; // 走向下一個節(jié)點
}
p.isEndingChar = true;
p.length = text.length;
}
/**
* 構(gòu)建fail指針
*/
public void buildFailurePointer() {
Queue<AcTrieNode> queue = new LinkedList<>();
this.root.fail = null;
queue.add(root);
while (!queue.isEmpty()) {
AcTrieNode p = queue.remove(); // 出隊
for (int i = 0; i < 26; i++) {
AcTrieNode pc = p.children[i];
if (pc == null) {
continue;
}
if (p == root) {
pc.fail = root;
} else {
AcTrieNode q = p.fail;
while (q != null) {
AcTrieNode qc = q.children[pc.data - 'a'];
if (qc != null) {
pc.fail = qc;
break;
}
q = q.fail;
}
if (q == null) {
pc.fail = root;
}
}
queue.add(pc);
}
}
}
/**
* 文本匹配
*
* @param text 輸入的文本
* @return 返回已起始位置為key, 匹配長度為value的map
*/
public Map<Integer, Integer> match(char[] text) {
Map<Integer, Integer> resMap = new HashMap<>();
int n = text.length;
AcTrieNode p = root;
for (int i = 0; i < n; i++) {
int idx = text[i] - 'a';
while (p.children[idx] == null && p != root) {
p = p.fail; // 失敗指針發(fā)揮作用的地方
}
p = p.children[idx];
if (p == null) {
p = root;//如果沒有匹配的，從 root 重新開始
}
AcTrieNode tmp = p;
while (tmp != root) { // 打印出可以匹配的模式串
if (tmp.isEndingChar) {
int pos = i - tmp.length + 1;
System.out.println("匹配起始下標(biāo)" + pos + ";長度" + tmp.length);
resMap.put(pos, tmp.length);
}
tmp = tmp.fail;
}
}
return resMap;
}
/**
* 查詢指定的文本是否存在
*
* @param text
* @return
*/
public boolean find(char[] text) {
AcTrieNode p = root;
for (char v : text) {
int idx = v - 'a';
if (p.children[idx] == null) {
return false; //沒找到
}
p = p.children[idx]; // 走向下一個節(jié)點
}
return p.isEndingChar; // 是結(jié)束字符，表示找到了，反之則表示沒找到
}
/**
* 輸入前綴，提示預(yù)設(shè)的完整詞
*
* @param text
* @return
*/
public List<String> likeFind(char[] text) {
List<String> resList = new ArrayList<>();
AcTrieNode p = root;
for (char v : text) {
int idx = v - 'a';// 'a' 等于 95 ，'b'-'a' = 1 這里計算出 v 應(yīng)該存儲的索引
if (p.children[idx] == null) {
return resList;
}
p = p.children[idx];// 走向下一個節(jié)點
}
if (p.isEndingChar) {
resList.add(new String(text));
}
like(p, resList, new String(text));
return resList;
}
public String like(AcTrieNode p, List<String> resList, String path) {
for (AcTrieNode v : p.children) {
if (v != null) {
path += v.data;
path = like(v, resList, path);
}
}
if (p.isEndingChar) {
resList.add(path);
}
path = path.substring(0, path.length() - 1);
return path;
}
}
public static void main(String[] args) {
System.out.println("========== hello Trie ============");
AcTrie trie = new AcTrie();
trie.insert("how".toCharArray());
trie.insert("hi".toCharArray());
trie.insert("her".toCharArray());
trie.insert("hello".toCharArray());
trie.insert("so".toCharArray());
trie.insert("see".toCharArray());
trie.insert("word".toCharArray());
trie.insert("fuck".toCharArray());
for (String v : new String[]{"hello", "baozi", "see", "li", "hai", "le", "word", "ge"}) {
System.out.printf("find %s ,%s \n", v, trie.find(v.toCharArray()));
}
System.out.println("\n========== 神奇的分割線 =============\n\n");
for (String v : new String[]{"h", "he", "hi", "s"}) {
List<String> strings = trie.likeFind(v.toCharArray());
System.out.printf("輸入：%s , 提示：%s\n", v, strings);
}
System.out.println("\n========== Ac Trie 神奇的分割線 =============\n\n");
trie.buildFailurePointer();
for (String v : new String[]{"seeifuckyou", "lihailewordge"}) {
char[] valChars = v.toCharArray();
Map<Integer, Integer> match = trie.match(valChars);
for (Integer star : match.keySet()) {
Integer end = match.get(star);
for (int i = 0; i < valChars.length; i++) {
if (i >= star && i < star + end) {
valChars[i] = '*';
}
}
}
System.out.println("輸入：" + v + "\n輸出：" + new String(valChars) + "\n");
}
}
}
