|
簡介 Aho-Corasick算法簡稱AC算法，通過將模式串預(yù)處理為確定有限狀態(tài)自動(dòng)機(jī)，掃描文本一遍就能結(jié)束。其復(fù)雜度為O(n)，即與模式串的數(shù)量和長度無關(guān)。 思想 自動(dòng)機(jī)按照文本字符順序，接受字符，并發(fā)生狀態(tài)轉(zhuǎn)移。這些狀態(tài)緩存了“按照字符轉(zhuǎn)移成功（但不是模式串的結(jié)尾）”、“按照字符轉(zhuǎn)移成功（是模式串的結(jié)尾）”、“按照字符轉(zhuǎn)移失敗”三種情況下的跳轉(zhuǎn)與輸出情況，因而降低了復(fù)雜度。 基本構(gòu)造 AC算法中有三個(gè)核心函數(shù)，分別是： success; 成功轉(zhuǎn)移到另一個(gè)狀態(tài)（也稱goto表或success表） failure; 不可順著字符串跳轉(zhuǎn)的話，則跳轉(zhuǎn)到一個(gè)特定的節(jié)點(diǎn)（也稱failure表），從根節(jié)點(diǎn)到這個(gè)特定的節(jié)點(diǎn)的路徑恰好是失敗前的文本的一部分。 emits; 命中一個(gè)模式串（也稱output表） 舉例 以經(jīng)典的ushers為例，模式串是he/ she/ his /hers，文本為“ushers”。構(gòu)建的自動(dòng)機(jī)如圖  其實(shí)上圖省略了到根節(jié)點(diǎn)的fail邊，完整的自動(dòng)機(jī)如下圖：  匹配過程 自動(dòng)機(jī)從根節(jié)點(diǎn)0出發(fā) 首先嘗試按success表轉(zhuǎn)移（圖中實(shí)線）。按照文本的指示轉(zhuǎn)移，也就是接收一個(gè)u。此時(shí)success表中并沒有相應(yīng)路線，轉(zhuǎn)移失敗。 失敗了則按照failure表回去（圖中虛線）。按照文本指示，這次接收一個(gè)s，轉(zhuǎn)移到狀態(tài)3。 成功了繼續(xù)按success表轉(zhuǎn)移，直到失敗跳轉(zhuǎn)步驟2，或者遇到output表中標(biāo)明的“可輸出狀態(tài)”（圖中紅色狀態(tài)）。此時(shí)輸出匹配到的模式串，然后將此狀態(tài)視作普通的狀態(tài)繼續(xù)轉(zhuǎn)移。 算法高效之處在于，當(dāng)自動(dòng)機(jī)接受了“ushe”之后，再接受一個(gè)r會(huì)導(dǎo)致無法按照success表轉(zhuǎn)移，此時(shí)自動(dòng)機(jī)會(huì)聰明地按照failure表轉(zhuǎn)移到2號(hào)狀態(tài)，并經(jīng)過幾次轉(zhuǎn)移后輸出“hers”。來到2號(hào)狀態(tài)的路不止一條，從根節(jié)點(diǎn)一路往下，“h→e”也可以到達(dá)。而這個(gè)“he”恰好是“ushe”的結(jié)尾，狀態(tài)機(jī)就仿佛是壓根就沒失敗過（沒有接受r），也沒有接受過中間的字符“us”，直接就從初始狀態(tài)按照“he”的路徑走過來一樣（到達(dá)同一節(jié)點(diǎn)，狀態(tài)完全相同）。 構(gòu)造過程 看來這三個(gè)表很厲害，不過，它們是怎么計(jì)算出來的呢？ goto表 很簡單，了解一點(diǎn)trie樹知識(shí)的話就能一眼看穿，goto表就是一棵trie樹。把上圖的虛線去掉，實(shí)線部分就是一棵trie樹了。 output表 output表也很簡單，與trie樹里面代表這個(gè)節(jié)點(diǎn)是否是單詞結(jié)尾的結(jié)構(gòu)很像。不過trie樹只有葉節(jié)點(diǎn)才有“output”，并且一個(gè)葉節(jié)點(diǎn)只有一個(gè)output。下圖卻違背了這兩點(diǎn)，這是為什么呢？其實(shí)下圖的output會(huì)在建立failure表的時(shí)候進(jìn)行一次拓充。 以上兩個(gè)表通過一個(gè)dfs就可以構(gòu)造出來。關(guān)于trie樹的更詳細(xì)內(nèi)容，請參考：《Ansj分詞雙數(shù)組Trie樹實(shí)現(xiàn)與arrays.dic詞典格式》，《Trie樹分詞》，《雙數(shù)組Trie樹(DoubleArrayTrie)Java實(shí)現(xiàn)》。 failure表 這個(gè)表是trie樹沒有的，加了這個(gè)表，AC自動(dòng)機(jī)就看起來不像一棵樹，而像一個(gè)圖了。failure表是狀態(tài)與狀態(tài)的一對(duì)一關(guān)系，別看圖中虛線亂糟糟的，不過你仔細(xì)看看，就會(huì)發(fā)現(xiàn)節(jié)點(diǎn)只會(huì)發(fā)出一條虛線，它們嚴(yán)格一對(duì)一。 這個(gè)表的構(gòu)造方法是： 首先規(guī)定與狀態(tài)0距離為1（即深度為1）的所有狀態(tài)的fail值都為0。 然后設(shè)當(dāng)前狀態(tài)是S1，求fail(S1)。我們知道，S1的前一狀態(tài)必定是唯一的（剛才說的一對(duì)一），設(shè)S1的前一狀態(tài)是S2，S2轉(zhuǎn)換到S1的條件為接受字符C，測試S3= goto(fail(S2), C)。 如果成功，則fail(S1) = goto(fail(S2), C) = S3。 如果不成功，繼續(xù)測試S4= goto(fail(S3), C)是否成功，如此重復(fù)，直到轉(zhuǎn)換到某個(gè)有效的狀態(tài)Sn，令fail(S1) = Sn。 Java實(shí)現(xiàn) 原理誰都可以說幾句的，可是優(yōu)雅健壯的代碼卻不是那么容易寫的。我考察了Git上幾個(gè)AC算法的實(shí)現(xiàn)，發(fā)現(xiàn)robert-bor的實(shí)現(xiàn)非常好。一趟代碼看下來，學(xué)到了不少設(shè)計(jì)上的知識(shí)。我fork了下來，針對(duì)Ascii做了優(yōu)化，添加了中文注釋。 另外，我實(shí)現(xiàn)了基于雙數(shù)組Trie樹的AC自動(dòng)機(jī)：《Aho Corasick自動(dòng)機(jī)結(jié)合DoubleArrayTrie極速多模式匹配》。性能更高，內(nèi)存可控。 ``` //創(chuàng)建set集合 Set stringSet =new HashSet<>(); stringSet.add("高危"); stringSet.add("并發(fā)"); stringSet.add("江蘇"); stringSet.add("彩信"); String[] value =new String[stringSet.size()]; stringSet.toArray(value); Trie.TrieBuilder trieBuilder = Trie.builder(); if(false){ trieBuilder.stopOnHit(); } for (String key:value) { trieBuilder.addKeyword(key); } Trie trie = trieBuilder.build(); System.out.println("查看是否包含這些字樣"); System.out.println(trie.containsMatch("江蘇高危短信彩信錫")); System.out.println("----------查看有哪些-----------------"); Collection emits = trie.parseText("江蘇高危短信彩信錫"); for(Emit temp : emits) { System.out.println("包含集合："+temp.getKeyword()); } ``` |
|
|
