AC 自動機
-
- Ⅰ 前言
- Ⅱ 用 Trie 樹實作敏感詞過濾
- Ⅲ AC 自動機原理及實作
- Ⅳ 敏感詞過濾系統的實作
Ⅰ 前言
很多支援使用者發表文本内容的網站或者軟體，大都會有敏感詞過濾功能，用來過濾掉使用者輸入的一些淫穢、反動、謾罵等内容，這個功能是怎麼實作的呢？
其實，這些功能的最基本的原理就是字元串比對算法，也就是通過維護一個敏感詞的詞典，當使用者輸入的一段文字後，通過字元串比對算法，來查找使用者輸入的這段文字，是否包含敏感詞，如果有，就用 * 把它替代掉。
我在之前的文章中，講過很多種字元串比對算法，它們都可以處理這個問題，但是，對于通路量巨大的網站來說，比如淘寶，使用者每天的評論數有幾億甚至幾十億。這個時候，我們對敏感詞過濾系統的性能要求就要很高。如果，一個使用者輸入内容之後要幾秒後才能發出去，那這個軟體可能就沒人用了。
要實作一個高性能的敏感詞過濾系統，就要用到我們這篇文章要講的多模式串比對算法。
在以前的文章裡，我講了四個單模式串比對算法，還有一個多模式串比對算法就是 Trie 樹。有興趣的同學可以跳轉過去看。
【資料結構與算法】-＞算法-＞字元串比對基礎（上）-＞BF 算法 & RK 算法
【資料結構與算法】-＞算法-＞字元串比對基礎（中）-＞BM算法-＞KMP 三倍性能的強大算法
【資料結構與算法】-＞算法-＞字元串比對基礎（下）-＞KMP 算法
【資料結構與算法】-＞資料結構-＞Trie樹-＞如何實作搜尋引擎的關鍵詞提示功能？
Ⅱ 用 Trie 樹實作敏感詞過濾
再總結一下這兩個概念，單模式串比對算法，就是一個模式串和一個主串之間進行比對，也就是在一個主串中查找一個模式串。多模式串比對算法，就是在多個模式串中和一個主串之間做比對，也就是說，在一個主串中查找多個模式串。
盡管，單模式串比對算法也能完成多模式串比對的工作，比如過濾敏感詞，我們可以針對每個敏感詞，通過但模式比對算法（比如 KMP 算法）與使用者輸入的文字内容進行比對。但是，這樣做的話，每個比對過程都需要掃描一遍使用者輸入的内容。整個過程下來就要掃描很多遍使用者輸入的内容。如果敏感詞很多，假如有上千個字元，那我們就要掃描幾千遍這樣的輸入内容。很顯然，這樣的處理思路比較低效。
與單模式串比對算法相比，多模式比對算法在這個問題的處理上就很高效了。它隻需要掃描一遍主串，就能在主串中一次性查找多個模式串是否存在，進而大大提高比對效率。我們知道，Trie 樹就是一種多模式串比對算法，是以我們可以用 Trie 樹來實作敏感詞過濾功能。
我們可以對敏感詞字典進行預處理，建構成 Trie 樹結構。這個預處理的操作隻需要做一次，如果敏感詞字典動态更新了，比如删除、添加了一個敏感詞，那我們隻需要動态更新一下 Trie 樹就可以了。
當使用者輸入一個文本内容後，我們把使用者輸入的内容作為主串，從第一個字元開始，在 Trie 樹中比對。當比對到 Trie 樹的葉子節點，或者中途遇到不比對字元的時候，我們将主串的開始比對位置後移一位，也就是從第一個字元的下一個字元開始，重新在 Trie 樹 中比對。
基于 Trie 樹的這種處理方法，有點類似單模式串比對中的 BF 算法。我們知道，單模式串比對算法中，KMP 算法對 BF 算法進行改進，引入了一個 next 數組，讓比對失效時，盡可能将模式串往後多移動幾位。借鑒單模式串的優化改進方法，能否對多模式串 Trie 樹進行改進，進一步提高 Trie 樹的效率呢？這就要用到 AC 自動機算法 了。
Ⅲ AC 自動機原理及實作
AC 自動機算法，全稱是 Aho-Corasick 算法。其實， Trie 樹跟 AC 自動機之間的關系，就像單模式串比對中樸素的串比對算法（BF）和 KMP 算法之間的關系一樣，隻不過前者針對的是多模式串而已。是以，AC 自動機實際上就是在 Trie 樹之上，加了類似 KMP 算法的 next 數組，隻不過此處的 next 數組建構在樹上。 用代碼實作就是下面的樣子👇
class AcNode {
char data;
AcNode[] children = new AcNode[SIZE];
boolean isEndingChar = false;
int length = -1; //當isEndingChar = true時。記錄模式串長度
AcNode fail; //失敗指針
AcNode(char data) {
this.data = data;
}
}
是以 AC 自動機的建構，包含兩個操作：
- 将多個模式串建構成 Trie 樹；
- 在 Trie 樹上建構失敗指針（相當于 KMP 中的失效函數 next 數組）。
關于如何建構 Trie 樹，在我講解 Trie 樹的文章中已經分析過了，大家可以跳轉去看。
【資料結構與算法】-＞資料結構-＞Trie樹-＞如何實作搜尋引擎的關鍵詞提示功能？
這裡我們就重點看一下在建構好 Trie 樹之後，如何在它之上建構失敗指針。
我還是用一個例子來講解。這裡有 4 個模式串，分别是 c，bc，bcd，abcd；主串是 abcd。
Trie 樹中的每一個節點都有一個失敗指針，它的作用和建構過程，跟 KMP 算法中的 next 數組極其相似。是以要了解這裡的建構，你最好先了解 KMP 算法中的 next 數組的建構過程。
【資料結構與算法】-＞算法-＞字元串比對基礎（下）-＞KMP 算法
假設我們沿 Trie 樹走到 p 節點，也就是下圖中的紫色節點，那 p 的失敗指針就是從 root 走到紫色節點形成的字元串 abc，跟所有模式串字首比對的最長可比對字尾子串，就是箭頭指的 bc 模式串。
這裡的最長可比對字尾子串我再多解釋一下。字元串 abc 的字尾子串有兩個，一個是 bc，一個屬 c，我們把它們與其他模式串比對，如果某個字尾子串可以比對某個模式串的字首，那我們 就把這個字尾子串叫作可比對字尾子串。
我們從可比對字尾子串中，找出最長的一個，就是最長可比對字尾子串。我們可以将 p 節點的失敗指針指向那個最長比對字尾子串對應的模式串的字首的最後一個節點，就是下圖中箭頭指向的節點。👇
計算每個節點的失敗指針這個過程看起來有些複雜。其實，如果我們把樹中相同深度的節點放到同一層，呢麼某個節點的失敗指針隻有可能出現在它所在層的上一層。
我們可以像 KMP 算法那樣，當我們要求某個節點的失敗指針的時候，我們通過已經求得的、深度更小的那些節點的失敗指針來推導。也就是說，我們可以逐層依次來求解每個節點的失敗指針。是以，失敗指針的建構過程，是一個按層周遊樹的過程。
首先 root 的失敗指針為
null
。當我們已經求得某個節點 p 的失敗指針之後，如何尋找它的子節點的失敗指針呢？
我們假設節點 p 的失敗指針指向節點 q，我們看節點 p 的子節點 pc 對應的字元，是否也可以在節點 q 的子節點中找到。如果找到了節點 q 的一個子結點 qc，對應的字元跟 pc 對應的字元相同，則将節點 pc 的失敗指針指向節點 qc。
如果節點 q 中沒有子節點的字元等于節點 pc 包含的字元，則令
q = q->fail
（fail 表示失敗指針），然後繼續上面的查找，直到 q 是 root 為止，如果還沒有找到相同字元的子節點，就讓節點 pc 的失敗指針指向 root。
我将建構失敗指針的代碼貼上，大家可以對着講解看看。
package com.tyz.string_matching.core;
import java.util.LinkedList;
import java.util.Queue;
/**
* AC自動機的實作
* @author Tong
*/
public class AhoCorasick {
public static final int SIZE = 26;
private AcNode root;
public AhoCorasick() {
this.root = new AcNode('/');
}
/**
* 實作Trie樹的插入功能
* @param text 要插入的字元串
*/
public void insert(char[] text) {
AcNode p = this.root;
for (int i = 0; i < text.length; i++) {
int index = text[i] - 'a';
if (p.children[index] == null) {
AcNode newNode = new AcNode(text[i]);
p.children[index] = newNode;
}
p = p.children[index];
}
p.isEndingChar = true;
p.length = text.length;
}
/**
* 查詢字元串在TrieTree中是否存在
* @param pattern 要查詢的字元串
* @return
*/
public boolean find(char[] pattern) {
AcNode p = this.root;
for (int i = 0; i < pattern.length; i++) {
int index = pattern[i] - 'a';
if (p.children[index] == null) {
return false; //Trie樹中不存在pattern
}
p = p.children[index];
}
return p.isEndingChar;
}
/**
* 建構AC自動機的失敗指針
*/
public void buildFailurePointer() {
Queue<AcNode> queue = new LinkedList<>();
this.root.fail = null;
queue.add(root);
while (!queue.isEmpty()) {
AcNode p = queue.remove();
for (int i = 0; i < SIZE; i++) {
AcNode pc = p.children[i];
if (pc == null) {
continue;
}
if (p == root) {
pc.fail = root;
} else {
AcNode q = p.fail;
while (q != null) {
AcNode 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);
}
}
}
class AcNode {
char data;
AcNode[] children = new AcNode[SIZE];
boolean isEndingChar = false;
int length = -1; //當isEndingChar = true時。記錄模式串長度
AcNode fail; //失敗指針
AcNode(char data) {
this.data = data;
}
}
}
我們前面說了，建構失敗指針的方法其實是要進行一個樹的廣度優先周遊，如果你了解這個，就很好了解這裡的建構失敗指針的代碼了。如果你對樹的廣度優先周遊還有疑惑，可以跳轉去看我這篇文章。👇
【資料結構與算法】-＞資料結構-＞樹與二叉樹
通過按層來計算每個節點的子節點的失效指針，前面舉的例子最後建構完成之後的 AC 自動機就是下面這個樣子👇
AC 自動機到此就建構完成了。我們現在來看一下，如何在 AC 自動機上比對主串。
我們還是拿之前的例子來講解，在比對過程中，主串從
i = 0
開始，AC 自動機從指針 p = root 開始，假設模式串是 b，主串是 a。
- 如果 p 指向的節點有一個等于 b[i] 的子節點 x，我們就更新 p 指向 x，這個時候我們需要通過失敗指針，檢測一系列失敗指針為結尾的路徑是否是模式串，這一句不太好了解，大家可以結合上面建構完成失敗指針的圖和代碼來思考這個邏輯。
- 如果 p 指向的節點沒有等于 b[i] 的子節點，那失敗指針就派上用場了，我們讓
p = p->fail
關于比對的這個部分，我還是将代碼貼出來，有時候代碼是比文字更能說清楚的。
/**
* 在主串中找模式串出現的位置以及長度
* @param text 主串
*/
public void match(char[] text) {
int num = text.length;
AcNode p = root;
for (int i = 0; i < num; i++) {
int index = text[i] - 'a';
while (p.children[index] == null && p != root) {
p = p.fail; //失敗指針的作用
}
p = p.children[index];
if (p == null) {
p = root; //如果沒有比對的，就從root開始重新比對
}
AcNode tmp = p;
while (tmp != root) { //列印出可以比對的模式串
if (tmp.isEndingChar == true) {
int pos = i - tmp.length + 1;
System.out.println("比對起始下标: " + pos + ", 長度: " + tmp.length);
}
tmp = tmp.fail;
}
}
}
這個
match()
方法會将找到主串中出現的所有和模式串比對的子串，并輸出起始下标以及長度。還是建議大家如果不清楚的話，做幾遍變量跟蹤。
AC 自動機完整代碼如下👇
package com.tyz.string_matching.core;
import java.util.LinkedList;
import java.util.Queue;
/**
* AC自動機的實作
* @author Tong
*/
public class AhoCorasick {
public static final int SIZE = 26;
private AcNode root;
public AhoCorasick() {
this.root = new AcNode('/');
}
/**
* 實作Trie樹的插入功能
* @param text 要插入的字元串
*/
public void insert(char[] text) {
AcNode p = this.root;
for (int i = 0; i < text.length; i++) {
int index = text[i] - 'a';
if (p.children[index] == null) {
AcNode newNode = new AcNode(text[i]);
p.children[index] = newNode;
}
p = p.children[index];
}
p.isEndingChar = true;
p.length = text.length;
}
/**
* 查詢字元串在TrieTree中是否存在
* @param pattern 要查詢的字元串
* @return
*/
public boolean find(char[] pattern) {
AcNode p = this.root;
for (int i = 0; i < pattern.length; i++) {
int index = pattern[i] - 'a';
if (p.children[index] == null) {
return false; //Trie樹中不存在pattern
}
p = p.children[index];
}
return p.isEndingChar;
}
/**
* 建構AC自動機的失敗指針
*/
public void buildFailurePointer() {
Queue<AcNode> queue = new LinkedList<>();
this.root.fail = null;
queue.add(root);
while (!queue.isEmpty()) {
AcNode p = queue.remove();
for (int i = 0; i < SIZE; i++) {
AcNode pc = p.children[i];
if (pc == null) {
continue;
}
if (p == root) {
pc.fail = root;
} else {
AcNode q = p.fail;
while (q != null) {
AcNode 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 主串
*/
public void match(char[] text) {
int num = text.length;
AcNode p = root;
for (int i = 0; i < num; i++) {
int index = text[i] - 'a';
while (p.children[index] == null && p != root) {
p = p.fail; //失敗指針的作用
}
p = p.children[index];
if (p == null) {
p = root; //如果沒有比對的，就從root開始重新比對
}
AcNode tmp = p;
while (tmp != root) { //列印出可以比對的模式串
if (tmp.isEndingChar == true) {
int pos = i - tmp.length + 1;
System.out.println("比對起始下标: " + pos + ", 長度: " + tmp.length);
}
tmp = tmp.fail;
}
}
}
class AcNode {
char data;
AcNode[] children = new AcNode[SIZE];
boolean isEndingChar = false;
int length = -1; //當isEndingChar = true時。記錄模式串長度
AcNode fail; //失敗指針
AcNode(char data) {
this.data = data;
}
}
}
測試代碼如下，大家可以看看這個功能👇
package com.tyz.string_matching.test;
import com.tyz.string_matching.core.AhoCorasick;
public class Test {
public static void main(String[] args) {
String strOne = "abc";
String strTwo = "tyz";
String strThree = "yzh";
AhoCorasick ac = new AhoCorasick();
ac.insert(strOne.toCharArray());
ac.insert(strTwo.toCharArray());
ac.insert(strThree.toCharArray());
ac.buildFailurePointer();
ac.match("dsabcastyzyzhshss".toCharArray());
}
}
輸出的結果如下👇
Ⅳ 敏感詞過濾系統的實作
通過上面的講解，相信你已經清楚了這個敏感詞過濾系統實作的思路，我們上面的實作起始已經是一個敏感詞過濾的原型代碼了。它可以找到所有敏感詞出現的位置，你隻要稍加改造，周遊一遍文本内容，就可以将文本中的所有敏感詞替換成 *。
這裡我們着重看一下，AC 自動機實作的敏感詞過濾系統，是否比單模式串比對方法更高效。
首先，我們需要将敏感詞建構成 AC 自動機，包括建構 Trie 樹以及建構失敗指針。
我在 Trie 樹的文章中講過，Trie 樹建構的時間複雜度是 O(m*len)，其中 len 表示敏感詞的平均長度，m 表示敏感詞的個數。那建構失敗指針的時間複雜度是多少呢？我這裡給出一個不是很準确的上界。
假設 Trie 樹中總的節點數是 k，每個節點建構失敗指針的時候，最耗時的環節是 while 循環中的
q = q.fail
，每運作一次這個語句，q 指向節點的深度都會減少 1，而樹的高度最高也不會超過 len，是以每個節點建構失敗指針的時間複雜度是 O(len)。整個失敗指針的建構過程就是 O(k*len)。
不過，AC 自動機的建構過程都是預先處理好的，建構好之後，并不會頻繁地更新，是以不會影響到敏感詞過濾的執行效率。
我們再來看一下，用 AC 自動機做比對的時間複雜度是多少。
和剛剛建構失敗指針的分析類似，for 循環内部最耗時的部分也是 while 循環，而這一部分的時間複雜度就是 O(n*len)，n 表示敏感詞的長度。因為敏感詞并不會很長，而且這個時間複雜度隻是一個非常寬泛的上限，實際情況下，可能近似于 O(n)，是以 AC 自動機做敏感詞過濾，性能非常高。
看到這裡你可能覺得，從時間複雜度上看，AC 自動機比對的效率和 Trie 樹一樣啊，但是實際上，因為失效指針可能大部分情況下都指向 root 節點，是以絕大部分情況下，在 AC 自動機上做比對的效率要遠高于剛剛計算出的比較寬泛的時間複雜度。隻有在極端情況下，如下圖，AC 自動機的性能才會退化的跟 Trie 樹一樣。
另，這篇文章的主要内容來源于極客時間王争的《資料結構與算法之美》。