1 概念和原理

一般的字符串匹配算法都是匹配一個(gè)子串，例如KMP、Trie，那么如果同時(shí)匹配多個(gè)子串呢？此時(shí)就需要用到AC自動(dòng)機(jī)了。

AC自動(dòng)機(jī)算法是一個(gè)多模式字符串匹配算法，在模式匹配領(lǐng)域被廣泛應(yīng)用，例如違禁詞查找替換、搜索關(guān)鍵詞查找等等。

關(guān)于Trie樹和KMP算法，我們此前已經(jīng)講解過了：

• 前綴樹Trie的實(shí)現(xiàn)原理以及Java代碼的實(shí)現(xiàn)
• KMP算法詳解以及Java代碼實(shí)現(xiàn)

AC自動(dòng)機(jī)算法常被認(rèn)為是Trie樹+KMP算法的結(jié)合體，為什么呢？我們先看看它的構(gòu)建步驟：

• 對所有的關(guān)鍵詞構(gòu)建Trie前綴樹。
• 為Trie樹上的所有節(jié)點(diǎn)構(gòu)建fail失配指針。

第一步，對所有的關(guān)鍵詞構(gòu)建Trie前綴樹。這一步利用Trie的特點(diǎn)構(gòu)建快速前綴查找結(jié)構(gòu)，trie樹的特點(diǎn)是可以從字符串頭部開始匹配，并且相同前綴的詞共用前面的節(jié)點(diǎn)，因此它可以避免相同前綴pattern的重復(fù)匹配，但是對于相同的后綴無能為力。

第二步，為Trie樹上的所有節(jié)點(diǎn)構(gòu)建fail失配指針，即匹配失敗后應(yīng)該跳到哪個(gè)節(jié)點(diǎn)。所謂節(jié)點(diǎn)的失配指針，就是指向當(dāng)前字符串最長真后綴位置的指針節(jié)點(diǎn)。這里需要理解KMP的next數(shù)組的概念，這一步就是利用KMP前后綴匹配的思想實(shí)現(xiàn)關(guān)鍵詞前綴失配時(shí)利用相同的后綴信息快速跳轉(zhuǎn)到另一個(gè)關(guān)鍵詞繼續(xù)前綴匹配。他們的區(qū)別是：

• 在KMP算法中，是針對單個(gè)關(guān)鍵詞匹配，求出的最長匹配長度的前綴和后綴都位于同一個(gè)關(guān)鍵詞內(nèi)。例如關(guān)鍵詞abcdabc，最長匹配前后綴，為abc，他們屬于該關(guān)鍵詞。
• 在AC自動(dòng)機(jī)算法中，是針對多個(gè)關(guān)鍵詞匹配，求出的最長匹配長度的前綴和后綴分別屬于不同的關(guān)鍵詞的前綴和后綴。

例如兩個(gè)關(guān)鍵詞dabab，ababd，那么關(guān)鍵詞dabab中第二個(gè)b位置的失敗指針應(yīng)該指向關(guān)鍵詞ababd中的第二個(gè)b。即dabab的后綴與ababd的前綴能夠匹配的最長子串為abab。

2 節(jié)點(diǎn)定義

在這里，我們給出一個(gè)比較簡單的節(jié)點(diǎn)的定義。

• next，表示經(jīng)過該節(jié)點(diǎn)的模式串的下層節(jié)點(diǎn)，這是Trie樹結(jié)構(gòu)的保證，存儲(chǔ)著子節(jié)點(diǎn)的值到對應(yīng)的節(jié)點(diǎn)的映射關(guān)系。
• depth，表示以當(dāng)前即誒單結(jié)尾的模式串的長度，也是節(jié)點(diǎn)的深度，默認(rèn)為0。
• failure，失配指針，其指向表示另一個(gè)關(guān)鍵詞前綴的最長后綴節(jié)點(diǎn)，如果當(dāng)前節(jié)點(diǎn)沒有匹配到，則跳轉(zhuǎn)到此節(jié)點(diǎn)繼續(xù)匹配。如果當(dāng)前節(jié)點(diǎn)匹配到了，那么可以通過此指針找到該節(jié)點(diǎn)的模式串包含的最長后綴模式串。

class AcNode {
    /**
     * 經(jīng)過該節(jié)點(diǎn)的模式串的下層節(jié)點(diǎn)
     */
    Map<Character, AcNode> next = new HashMap<>();

    /**
     * 模式串的長度，也是節(jié)點(diǎn)的深度
     */
    int depth;

    /**
     * 失配指針，如果沒有匹配到，則跳轉(zhuǎn)到此狀態(tài)。
     */
    AcNode failure;

    public boolean hashNext(char nextKey) {
        return next.containsKey(nextKey);
    }

    public AcNode getNext(char nextKey) {
        return next.get(nextKey);
    }
}

3 構(gòu)建Trie前綴樹

構(gòu)建Ac自動(dòng)機(jī)的Trie的方法和構(gòu)建普通Trie的方法幾乎一致。在添加每個(gè)模式串成功后，會(huì)為最后一個(gè)節(jié)點(diǎn)的depth賦值為當(dāng)前模式串的長度。

/**
 * trie根節(jié)點(diǎn)
 */
private AcNode root;
/**
 * 加入模式串，構(gòu)建Trie
 *
 * @param word 模式串，非空
 */
public void insert(String word) {
    AcNode cur = root;
    for (char c : word.toCharArray()) {
        if (!cur.next.containsKey(c)) {
            cur.next.put(c, new AcNode());
        }
        cur = cur.next.get(c);
    }
    cur.depth = word.length();
}

4 構(gòu)建fail失配指針

構(gòu)建fail失配指針的一種常見的方法如下，實(shí)際上是一個(gè)BFS層序遍歷的算法：

1.Trie的root節(jié)點(diǎn)沒有失配指針，或者說失配指針為null，其他節(jié)點(diǎn)都有失配指針，或者說不為null。

2.遍歷root節(jié)點(diǎn)的所有下一層直接子節(jié)點(diǎn)，將它們的失配指針設(shè)置為root。因?yàn)檫@些節(jié)點(diǎn)代表著所有模式串的第一個(gè)字符，基于KMP的next數(shù)組定義，單個(gè)字符沒有最長真后綴，此時(shí)直接指向root。

3.繼續(xù)循環(huán)向下遍歷每一層的子節(jié)點(diǎn)，由于bfs的遍歷，那么上一層父節(jié)點(diǎn)的失配指針肯定都已經(jīng)確定了。基于next數(shù)組的構(gòu)建思想，子節(jié)點(diǎn)的失配指針可以通過父節(jié)點(diǎn)的是失配指針快速推導(dǎo)出來。設(shè)當(dāng)前遍歷的節(jié)點(diǎn)為c，它的父節(jié)點(diǎn)為p，父節(jié)點(diǎn)的失配指針為pf。

• 如果pf節(jié)點(diǎn)的子節(jié)點(diǎn)對應(yīng)的字符中，包含了當(dāng)前節(jié)點(diǎn)的所表示的字符。那么基于求最長后綴的原理，此時(shí)c節(jié)點(diǎn)的失配指針可以直接指向pf節(jié)點(diǎn)下的相同字符對應(yīng)的子節(jié)點(diǎn)。
• 如果pf節(jié)點(diǎn)的子節(jié)點(diǎn)對應(yīng)的字符中，沒有包含了當(dāng)前節(jié)點(diǎn)的所表示的字符。那么繼續(xù)獲取pf節(jié)點(diǎn)的失配指針節(jié)點(diǎn)，繼續(xù)重復(fù)判斷。直到滿足第一種情況，或者pf指向了根節(jié)點(diǎn)，并且根節(jié)點(diǎn)的子節(jié)點(diǎn)也沒有匹配，那么此時(shí)直接將c節(jié)點(diǎn)的失配指針指向根節(jié)點(diǎn)。

/**
 * 為所有節(jié)點(diǎn)構(gòu)建失配指針，一個(gè)bfs層序遍歷
 */
public void buildFailurePointer() {
    ArrayDeque<AcNode> queue = new ArrayDeque<AcNode>();
    //將所有root的直接子節(jié)點(diǎn)的failure設(shè)置為root，并且加入queue
    for (AcNode acNode : root.next.values()) {
        acNode.failure = root;
        queue.addLast(acNode);
    }
    //bfs構(gòu)建失配指針
    while (!queue.isEmpty()) {
        //父節(jié)點(diǎn)出隊(duì)列
        AcNode parent = queue.pollFirst();
        //遍歷父節(jié)點(diǎn)的下層子節(jié)點(diǎn)，基于父節(jié)點(diǎn)求子節(jié)點(diǎn)的失配指針
        for (Map.Entry<Character, AcNode> characterAcNodeEntry : parent.next.entrySet()) {
            //獲取父節(jié)點(diǎn)的失配指針
            AcNode pf = parent.failure;
            //獲取子節(jié)點(diǎn)
            AcNode child = characterAcNodeEntry.getValue();
            //獲取子節(jié)點(diǎn)對應(yīng)的字符
            Character nextKey = characterAcNodeEntry.getKey();
            //如果pf節(jié)點(diǎn)不為null，并且pf節(jié)點(diǎn)的子節(jié)點(diǎn)對應(yīng)的字符中，沒有包含了當(dāng)前節(jié)點(diǎn)的所表示的字符
            while (pf != null && !pf.hashNext(nextKey)) {
                //繼續(xù)獲取pf節(jié)點(diǎn)的失配指針節(jié)點(diǎn)，繼續(xù)重復(fù)判斷
                pf = pf.failure;
            }
            //pf為null，表示找到了根節(jié)點(diǎn)，并且根節(jié)點(diǎn)的子節(jié)點(diǎn)也沒有匹配
            if (pf == null) {
                //此時(shí)直接將節(jié)點(diǎn)的失配指針指向根節(jié)點(diǎn)
                child.failure = root;
            }
            //pf節(jié)點(diǎn)的子節(jié)點(diǎn)對應(yīng)的字符中，包含了當(dāng)前節(jié)點(diǎn)的所表示的字符
            else {
                //節(jié)點(diǎn)的失配指針可以直接指向pf節(jié)點(diǎn)下的相同字符對應(yīng)的子節(jié)點(diǎn)
                child.failure = pf.getNext(nextKey);
            }
            //最后不要忘了，將當(dāng)前節(jié)點(diǎn)加入隊(duì)列
            queue.addLast(child);
        }
    }
}

5 匹配文本

構(gòu)建完AC自動(dòng)機(jī)之后，下面我們需要進(jìn)行文本的匹配，匹配的方式實(shí)際上比較簡單。

1.遍歷文本的每個(gè)字符，依次匹配，從Trie的根節(jié)點(diǎn)作為cur節(jié)點(diǎn)開始匹配：

2.將當(dāng)前字符作為nextKey，如果cur節(jié)點(diǎn)不為null且節(jié)點(diǎn)的next映射中不包含nextKey，那么當(dāng)前cur節(jié)點(diǎn)指向自己的failure失配指針。

3.如果cur節(jié)點(diǎn)為null，說明當(dāng)前字符匹配到了root根節(jié)點(diǎn)且失敗，那么cur設(shè)置為root繼續(xù)從根節(jié)點(diǎn)開始進(jìn)行下一輪匹配。

4.否則表示匹配成功的節(jié)點(diǎn)，cur指向匹配節(jié)點(diǎn)，獲取該節(jié)點(diǎn)繼續(xù)判斷：

• 如果該節(jié)點(diǎn)是某個(gè)關(guān)鍵詞的結(jié)尾，那么取出來，也就是depth不為0，那么表示匹配到了一個(gè)關(guān)鍵詞。
• 繼續(xù)判斷該節(jié)點(diǎn)的失配指針節(jié)點(diǎn)表示的模式串。因?yàn)槭渲羔樄?jié)點(diǎn)表示的模式串是當(dāng)前匹配的模式串的在這些關(guān)鍵詞中的最長后綴，且由于當(dāng)前節(jié)點(diǎn)的路徑包括了失配指針的全部路徑，并且失配指針路徑也是一個(gè)完整的關(guān)鍵詞，需要找出來。

/**
 * 匹配文本
 *
 * @param text 文本字符串
 */
public List<ParseResult> parseText(String text) {
    List<ParseResult> parseResults = new ArrayList<>();
    char[] chars = text.toCharArray();
    //從根節(jié)點(diǎn)開始匹配
    AcNode cur = root;
    //遍歷字符串的每個(gè)字符
    for (int i = 0; i < chars.length; i++) {
        //當(dāng)前字符
        char nextKey = chars[i];
        //如果cur不為null，并且當(dāng)前節(jié)點(diǎn)的的子節(jié)點(diǎn)不包括當(dāng)前字符，即不匹配
        while (cur != null && !cur.hashNext(nextKey)) {
            //那么通過失配指針轉(zhuǎn)移到下一個(gè)節(jié)點(diǎn)繼續(xù)匹配
            cur = cur.failure;
        }
        //如果節(jié)點(diǎn)為null，說明當(dāng)前字符匹配到了根節(jié)點(diǎn)且失敗
        //那么繼續(xù)從根節(jié)點(diǎn)開始進(jìn)行下一輪匹配
        if (cur == null) {
            cur = root;
        } else {
            //匹配成功的節(jié)點(diǎn)
            cur = cur.getNext(nextKey);
            //繼續(xù)判斷
            AcNode temp = cur;
            while (temp != null) {
                //如果當(dāng)前節(jié)點(diǎn)是某個(gè)關(guān)鍵詞的結(jié)尾，那么取出來
                if (temp.depth != 0) {
                    int start = i - temp.depth + 1, end = i;
                    parseResults.add(new ParseResult(start, end, new String(chars, start, temp.depth)));
                    //System.out.println(start + " " + end + " " + new String(chars, start, temp.depth));
                }
                //繼續(xù)判斷該節(jié)點(diǎn)的失配指針節(jié)點(diǎn)
                //因?yàn)槭渲羔樄?jié)點(diǎn)表示的模式串是當(dāng)前匹配的模式串的在這些關(guān)鍵詞中的最長后綴，且由于當(dāng)前節(jié)點(diǎn)的路徑包括了失配指針的全部路徑
                //并且失配指針路徑也是一個(gè)完整的關(guān)鍵詞，需要找出來。
                temp = temp.failure;
            }
        }
    }
    return parseResults;
}

class ParseResult {
    int startIndex;
    int endIndex;
    String key;

    public ParseResult(int startIndex, int endIndex, String key) {
        this.startIndex = startIndex;
        this.endIndex = endIndex;
        this.key = key;
    }

    @Override
    public String toString() {
        return "{" +
                "startIndex=" + startIndex +
                ", endIndex=" + endIndex +
                ", key='" + key + '\'' +
                '}';
    }
}

6 案例演示

基于上面的方法，假如關(guān)鍵詞為：he、shes、shers、hes、h、e，那么最終構(gòu)建的AC自動(dòng)機(jī)的結(jié)構(gòu)如下（紅色圈表示某個(gè)關(guān)鍵詞的結(jié)束位置）。

假如我們的文本為sheshe，那么我們來看看AC自動(dòng)機(jī)匹配的過程：

遍歷文本，cur首先指向root。

nextKey=s，cur.next包含s，表示這是一個(gè)匹配成功的節(jié)點(diǎn)，那么獲取到該節(jié)點(diǎn)s，cur=s，s不是某個(gè)關(guān)鍵詞的結(jié)尾，failure節(jié)點(diǎn)也不包含模式串，那么查找完畢進(jìn)行下一輪。

nextKey=h，cur=s，cur.next包含h，表示這是一個(gè)匹配成功的節(jié)點(diǎn)，那么獲取到該節(jié)點(diǎn)h，cur=h，h節(jié)點(diǎn)不是某個(gè)關(guān)鍵詞的結(jié)尾，但是它的failure節(jié)點(diǎn)包含模式串h，因此找到了第1個(gè)匹配的關(guān)鍵詞h，查找完畢后進(jìn)行下一輪。

nextKey=e，cur=h，cur.next包含e，表示這是一個(gè)匹配成功的節(jié)點(diǎn)，那么獲取到該節(jié)點(diǎn)e，cur=e，e節(jié)點(diǎn)不是某個(gè)關(guān)鍵詞的結(jié)尾，但是它的failure節(jié)點(diǎn)包含模式串he，因此找到了第2個(gè)匹配的關(guān)鍵詞he。

而fuilure節(jié)點(diǎn)e又包含另一個(gè)模式串e，因此找到了第3個(gè)匹配的關(guān)鍵詞e，查找完畢后進(jìn)行下一輪。

nextKey=s，cur=e，cur.next包含s，表示這是一個(gè)匹配成功的節(jié)點(diǎn)，那么獲取到該節(jié)點(diǎn)e，cur=e，s節(jié)點(diǎn)是關(guān)鍵詞shes的結(jié)尾，因此找到了第4個(gè)匹配的關(guān)鍵詞shes。

繼續(xù)判斷s的failure，它的failure節(jié)點(diǎn)包含模式串hes，因此找到了第5個(gè)匹配的關(guān)鍵詞hes，查找完畢后進(jìn)行下一輪。

nextKey=h，cur=s，cur.next不包含h，表示這是一個(gè)匹配失敗的節(jié)點(diǎn)，那么繼續(xù)匹配它的failure節(jié)點(diǎn)，經(jīng)過s-s-s的匹配，最終匹配到子節(jié)點(diǎn)h。

該節(jié)點(diǎn)h并不是關(guān)鍵詞的結(jié)尾，但是h的failure，它的failure節(jié)點(diǎn)包含模式串h，因此找到了第6個(gè)匹配的關(guān)鍵詞h，查找完畢后進(jìn)行下一輪。

nextKey=e，cur=h，cur.next包含e，表示這是一個(gè)匹配成功的節(jié)點(diǎn)，那么獲取到該節(jié)點(diǎn)e，cur=e，e節(jié)點(diǎn)不是某個(gè)關(guān)鍵詞的結(jié)尾，但是它的failure節(jié)點(diǎn)包含模式串he，因此找到了第7個(gè)匹配的關(guān)鍵詞he。

而fuilure節(jié)點(diǎn)e又包含另一個(gè)模式串e，因此找到了第8個(gè)匹配的關(guān)鍵詞e。

到此字符串遍歷完畢，查找完畢！

最終文本sheshe，匹配到關(guān)鍵詞如下：

[{startIndex=1, endIndex=1, key='h'}, {startIndex=1, endIndex=2, key='he'}, 
{startIndex=2, endIndex=2, key='e'}, {startIndex=0, endIndex=3, key='shes'}, 
{startIndex=1, endIndex=3, key='hes'}, {startIndex=4, endIndex=4, key='h'}, 
{startIndex=4, endIndex=5, key='he'}, {startIndex=5, endIndex=5, key='e'}]

7 總結(jié)

AC自動(dòng)機(jī)匹配某個(gè)文本text，需要遍歷文本的每個(gè)字符，每次遍歷過程中，都可能涉及到循環(huán)向上查找失配指針的情況，但是這里的循環(huán)次數(shù)不會(huì)超過Trie樹的深度，在最后匹配成功時(shí)，同樣涉及到向上查找失配指針的情況，這里的循環(huán)次數(shù)不會(huì)超過Trie樹的深度。

設(shè)匹配的文本長度m，模式串平均長度n，那么AC自動(dòng)機(jī)算法的匹配的時(shí)間復(fù)雜度為O(m*n)?？梢园l(fā)現(xiàn)，匹配的時(shí)間復(fù)雜度和關(guān)鍵詞的數(shù)量無關(guān)，這就是AC自動(dòng)機(jī)的強(qiáng)大之處。如果考慮模式串平均長度不會(huì)很長，那么時(shí)間復(fù)雜度近似O(m)。

到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)之AC自動(dòng)機(jī)算法的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Java AC自動(dòng)機(jī)算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論