快捷導(dǎo)航

詳解Java中AC自動機(jī)的原理與實(shí)現(xiàn)

更新時間：2022年05月14日 09:16:03 作者：Carol

AC自動機(jī)是一個多模式匹配算法，在模式匹配領(lǐng)域被廣泛應(yīng)用。本文將詳細(xì)為大家介紹AC自動機(jī)的原理與實(shí)現(xiàn)方法，感興趣的可以了解一下

簡介

AC自動機(jī)是一個多模式匹配算法，在模式匹配領(lǐng)域被廣泛應(yīng)用，舉一個經(jīng)典的例子，違禁詞查找并替換為***。AC自動機(jī)其實(shí)是Trie樹和KMP 算法的結(jié)合,首先將多模式串建立一個Tire樹，然后結(jié)合KMP算法前綴與后綴匹配可以減少不必要比較的思想達(dá)到高效找到字符串中出現(xiàn)的匹配串。

如果不知道什么是Tire樹，可以先查看：詳解Java中字典樹(Trie樹)的圖解與實(shí)現(xiàn)

如果不知道KMP算法，可以先查看：詳解Java中KMP算法的圖解與實(shí)現(xiàn)

工作過程

首先看一下AC自動機(jī)的結(jié)構(gòu)，從造型上看，跟我們之前講Tire樹幾乎一樣，但是多了紅色線條（這里因?yàn)楫嬐晏珌y，沒有畫完），這個紅色線條我們稱為失敗指針。其匹配規(guī)則與KMP一致，后綴和前綴的匹配，不一樣的是，KMP是同一個模式串的前綴和后綴進(jìn)行匹配，而這里是當(dāng)前模式串的后綴，與另一個模式串的前綴進(jìn)行匹配。如果能夠匹配上，因?yàn)檫@兩個模式串的前綴一定不同（相同的前綴已經(jīng)聚合），將當(dāng)前已匹配的后綴拿出來，比如abo，后綴為o，bo，abo，這時候我們再找另一個模式串的最長前綴與當(dāng)前后綴匹配上（對應(yīng)kmp中的最長前綴后綴子串），這時候我們可以找到out的o，則about中的o節(jié)點(diǎn)的失敗指針指向out的o節(jié)點(diǎn)，這么做的意義就是主串可以一直往后比較，不用往前回溯（比如ab，之前匹配過能匹配上，但是到o是失敗了，其他匹配串不可能出現(xiàn)ab前綴，所以不必再匹配，一定失?。?。

構(gòu)建過程：建立一棵Tire樹，結(jié)尾節(jié)點(diǎn)需要標(biāo)志當(dāng)前模式串的長度，構(gòu)建失敗指針。

查找過程：從根節(jié)點(diǎn)出發(fā)，查找當(dāng)前節(jié)點(diǎn)的孩子節(jié)點(diǎn)是否有與當(dāng)前字符匹配的字符，匹配則判斷是否為尾節(jié)點(diǎn)，是則匹配成功，記錄。不是尾節(jié)點(diǎn)繼續(xù)匹配。如果孩子節(jié)點(diǎn)沒有與字符匹配的，則直接轉(zhuǎn)到失敗指針繼續(xù)操作。

數(shù)據(jù)結(jié)構(gòu)

一個value記錄當(dāng)前節(jié)點(diǎn)的值，childNode記錄當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)（假設(shè)僅出現(xiàn)26個小寫字母，空間存在浪費(fèi)，可使用hash表，有序二分，跳表進(jìn)行優(yōu)化），isTail標(biāo)志當(dāng)前節(jié)點(diǎn)是否為尾節(jié)點(diǎn)，failNode表示失敗指針，即當(dāng)前節(jié)點(diǎn)的孩子節(jié)點(diǎn)與當(dāng)前字符均不匹配的時候，轉(zhuǎn)到哪個節(jié)點(diǎn)接續(xù)進(jìn)行匹配，tailLength，記錄模式串的長度，方便快速拿出模式串的值（根據(jù)長度以及匹配的index，從主串中拿）。

public?static?class?Node{
? ? ? ?//當(dāng)前節(jié)點(diǎn)值
? ? ? ?private?char?value;
? ? ? ?//當(dāng)前節(jié)點(diǎn)的孩子節(jié)點(diǎn)
? ? ? ?private?Node[]?childNode;
? ? ? ?//標(biāo)志當(dāng)前節(jié)點(diǎn)是否是某單詞結(jié)尾
? ? ? ?private?boolean?isTail;
? ? ? ?//失敗指針
? ? ? ?private?Node?failNode;
? ? ? ?//匹配串長度，當(dāng)isTail==true時，表示從root當(dāng)當(dāng)前位置是一個完整的匹配串，記錄這個匹配串的長度，便于之后快速找到匹配串
? ? ? ?private?Integer?tailLength;
? ? ? ?public?Node(char?value) {
? ? ? ? ? ?this.value?=?value;
? ? ? }
? }

初始化

初始化一棵僅存在root的根節(jié)點(diǎn)，root的失敗指針以及長度均為null。

Node?root;
? ?public?void?init() {
? ? ? ?root?=?new?Node('\0');
? ? ? ?root.childNode?=?new?Node[26];
? }

構(gòu)建字典樹

這個過程之前Tire樹中已經(jīng)講過，不再贅述，唯一的區(qū)別是需要在結(jié)尾節(jié)點(diǎn)上標(biāo)志當(dāng)前模式串的長度。

public?void?insertStr(char[]?chars) {
? ? ? ?//首先判斷首字符是否已經(jīng)在字典樹中，然后判斷第二字符，依次往下進(jìn)行判斷，找到第一個不存在的字符進(jìn)行插入孩節(jié)點(diǎn)
? ? ? ?Node?p?=?root;
? ? ? ?//表明當(dāng)前處理到了第幾個字符
? ? ? ?int?chIndex?=?0;
? ? ? ?while?(chIndex?<?chars.length) {
? ? ? ? ? ?while?(chIndex?<?chars.length?&&?null?!=?p) {
? ? ? ? ? ? ? ?Node[]?children?=?p.childNode;
? ? ? ? ? ? ? ?boolean?find?=?false;
? ? ? ? ? ? ? ?for?(Node?child?:?children) {
? ? ? ? ? ? ? ? ? ?if?(null?==?child) {continue;}
? ? ? ? ? ? ? ? ? ?if?(child.value?==?chars[chIndex]) {
? ? ? ? ? ? ? ? ? ? ? ?//當(dāng)前字符已經(jīng)存在，不需要再進(jìn)行存儲
? ? ? ? ? ? ? ? ? ? ? ?//從當(dāng)前節(jié)點(diǎn)出發(fā)，存儲下一個字符
? ? ? ? ? ? ? ? ? ? ? ?p?=?child;
? ? ? ? ? ? ? ? ? ? ? ?++?chIndex;
? ? ? ? ? ? ? ? ? ? ? ?find?=?true;
? ? ? ? ? ? ? ? ? ? ? ?break;
? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?if?(Boolean.TRUE.equals(find)) {
? ? ? ? ? ? ? ? ? ?//在孩子中找到了 不用再次存儲
? ? ? ? ? ? ? ? ? ?break;
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?//如果把孩子節(jié)點(diǎn)都找遍了，還沒有找到這個字符，直接將這個字符加入當(dāng)前節(jié)點(diǎn)的孩子節(jié)點(diǎn)
? ? ? ? ? ? ? ?Node?node?=?new?Node(chars[chIndex]);
? ? ? ? ? ? ? ?node.childNode?=?new?Node[26];
? ? ? ? ? ? ? ?children[chars[chIndex]?-?'a']?=?node;
? ? ? ? ? ? ? ?p?=?node;
? ? ? ? ? ? ? ?++?chIndex;
? ? ? ? ? }
? ? ? }
? ? ? ?//字符串中字符全部進(jìn)入tire樹中后，將最后一個字符所在節(jié)點(diǎn)標(biāo)志為結(jié)尾節(jié)點(diǎn)
? ? ? ?p.isTail?=?true;
? ? ? ?p.tailLength?=?chars.length;
? }

構(gòu)建失敗指針

從根節(jié)點(diǎn)開始層序遍歷樹結(jié)構(gòu)，構(gòu)建失敗指針。一個節(jié)點(diǎn)的子節(jié)點(diǎn)的失敗指針可以根據(jù)當(dāng)前節(jié)點(diǎn)的失敗指針得到，因?yàn)槲覀兪怯煤缶Y去與前綴匹配，所以如果我們采用層序遍歷，與當(dāng)前后綴的前綴一定在上層，已經(jīng)匹配出來了。那么當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)的失敗指針則可以根據(jù)當(dāng)前節(jié)點(diǎn)的失敗指針，查找失敗指針指向的節(jié)點(diǎn)的子節(jié)點(diǎn)是否有與當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)相等的，相等則這個子節(jié)點(diǎn)的失敗指針直接指向，不相等則繼續(xù)找，找不到直接指向root。根據(jù)上面的圖，我們來舉一個例子，我們已經(jīng)找到about中o節(jié)點(diǎn)（o1）的失敗指針是out中的o節(jié)點(diǎn)（o2），接下來我們怎么找u（u1）的失敗指針呢？首先根據(jù)o1的失敗指針我們找到了o2，o2的子節(jié)點(diǎn)為u（u2），恰好與我們u1的值相等，此時我們就可以將u1的失敗指針指向u2。以此類推，如果訪問到最后為空（root的失敗指針為空），則直接將失敗指針指向root。

public?void?madeFailNext() {
? ? ? ?//層序遍歷，為了保證求解這個節(jié)點(diǎn)失敗指針的時候，它的父節(jié)點(diǎn)的失敗指針以及失敗指針的失敗指針。。。。已經(jīng)求得，可以完全根據(jù)這個找
? ? ? ?Deque<Node>?nodes?=?new?LinkedList<>();
? ? ? ?nodes.add(root);
? ? ? ?while?(!nodes.isEmpty()) {
? ? ? ? ? ?Node?current?=?nodes.poll();
? ? ? ? ? ?Node[]?children?=?current.childNode;
? ? ? ? ? ?for?(Node?child?:?children) {
? ? ? ? ? ? ? ?if?(null?==?child) {
? ? ? ? ? ? ? ? ? ?continue;
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?Node?failNode?=?current.failNode;
? ? ? ? ? ? ? ?while?(null?!=?failNode) {
? ? ? ? ? ? ? ? ? ?//找到當(dāng)前節(jié)點(diǎn)的失敗指針，查看失敗指針子節(jié)點(diǎn)是否有==
? ? ? ? ? ? ? ? ? ?Node[]?failChildren?=?failNode.childNode;
? ? ? ? ? ? ? ? ? ?Node?node?=?failChildren[child.value?-?'a'];
? ? ? ? ? ? ? ? ? ?if?(null?==?node) {
? ? ? ? ? ? ? ? ? ? ? ?//找當(dāng)前指針的下一個指針
? ? ? ? ? ? ? ? ? ? ? ?failNode?=?failNode.failNode;
? ? ? ? ? ? ? ? ? ? ? ?continue;
? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ?//已經(jīng)找到匹配的
? ? ? ? ? ? ? ? ? ?//將失敗指針指向node
? ? ? ? ? ? ? ? ? ?child.failNode?=?node;
? ? ? ? ? ? ? ? ? ?break;
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?//如果找完還沒有找到，指向root
? ? ? ? ? ? ? ?if?(null?==?failNode) {
? ? ? ? ? ? ? ? ? ?child.failNode?=?root;
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?nodes.add(child);
? ? ? ? ? }
? ? ? }
? }

匹配

從首字符，字典樹從root節(jié)點(diǎn)開始進(jìn)行匹配，如果字符與節(jié)點(diǎn)值匹配，則判斷是否為尾字符，如果是匹配上一個違禁詞，記錄下來，如果不匹配則轉(zhuǎn)移到失敗指針繼續(xù)進(jìn)行匹配。

/**
? ??* 匹配出str中所有出現(xiàn)的關(guān)鍵詞
? ??* @param str
? ??* @return
? ??*/
? ?public?List<String>?match(String?str) {
? ? ? ?//遍歷當(dāng)前子串串，從根節(jié)點(diǎn)出發(fā)，如果匹配就一直往下進(jìn)行匹配，同時需要看匹配的節(jié)點(diǎn)是否為結(jié)尾節(jié)點(diǎn)，如果是，匹配上一個
? ? ? ?//如果不匹配則通過失敗指針轉(zhuǎn)移到下一個節(jié)點(diǎn)
? ? ? ?this.dfs(root,?0,?str);
? ? ? ?return?machStr;
? }

? ?//abcdeasdabcebcd
? ?List<String>?machStr?=?new?ArrayList<>();
? ?private?void?dfs(Node?node,?int?chIndex,?String?chars) {
? ? ? ?if?(chIndex?>=?chars.length()) {
? ? ? ? ? ?return;
? ? ? }
? ? ? ?//從將當(dāng)前字符與當(dāng)前node的孩子節(jié)點(diǎn)進(jìn)行匹配，如果當(dāng)前字符與node的孩子節(jié)點(diǎn).value匹配，判斷當(dāng)前字符是否為尾節(jié)點(diǎn)，是，則記錄，匹配到了一個
? ? ? ?//繼續(xù)匹配（子節(jié)點(diǎn)，與下一個元素進(jìn)行匹配）
? ? ? ?//如果不匹配，則轉(zhuǎn)到失敗指針
? ? ? ?Node[]?children?=?node.childNode;
? ? ? ?Node?child?=?children[chars.charAt(chIndex)?-?'a'];
? ? ? ?if?(null?==?child) {
? ? ? ? ? ?//不匹配，轉(zhuǎn)到失敗指針
? ? ? ? ? ?//如果當(dāng)前node==root，從root匹配，root的失敗指針是null
? ? ? ? ? ?if?(node?==?root) {
? ? ? ? ? ? ? ?dfs(root,?++?chIndex,?chars);
? ? ? ? ? }?else?{
? ? ? ? ? ? ? ?dfs(node.failNode,?chIndex,?chars);
? ? ? ? ? }
? ? ? }?else?{
? ? ? ? ? ?//匹配到了
? ? ? ? ? ?if?(child.isTail) {
? ? ? ? ? ? ? ?//并且是結(jié)尾節(jié)點(diǎn)，取從child.value到child.tailLength的字符
? ? ? ? ? ? ? ?machStr.add(chars.substring(chIndex?-?child.tailLength??+?1,?chIndex?+?1));
? ? ? ? ? }
? ? ? ? ? ?dfs(child,?++?chIndex,?chars);
? ? ? }

? }

執(zhí)行結(jié)果

public?static?void?main(String[]?args) {
? ? ? ?ACAutomaton?acAutomaton?=?new?ACAutomaton();
? ? ? ?//初始化一個僅有根節(jié)點(diǎn)的字典樹
? ? ? ?acAutomaton.init();
? ? ? ?//構(gòu)建Tire樹
? ? ? ?acAutomaton.insertStr("out".toCharArray());
? ? ? ?acAutomaton.insertStr("about".toCharArray());
? ? ? ?acAutomaton.insertStr("act".toCharArray());
? ? ? ?//構(gòu)建失敗指針
? ? ? ?acAutomaton.madeFailNext();
? ? ? ?System.out.println("ces");
? ? ? ?//匹配
? ? ? ?List<String>?result?=?acAutomaton.match("abcdeasactdaboutcebcd");
? }