一種基于Aho?Corasick算法改進的多模式匹配算法

陳永杰 吾守爾·斯拉木 于清

關鍵詞： 字符串匹配; 多模式匹配; Trie樹; 雙數(shù)組; AC算法; 匹配速度

中圖分類號： TN919?34; TP301.6 ? ? ? ? ? ? ? 文獻標識碼： A ? ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2019）04?0089?05

An improved multi?pattern matching algorithm based on Aho?Corasick algorithm

CHEN Yongjie， Wushour Silamu， YU Qing

（School of Information Science and Engineering， Xinjiang University， Urumqi 830046， China）

Abstract： There exists a large amount of text data on the Internet currently. In allusion to the problem that how to search out multiple different target character strings accurately and quickly in such large text， an improved fast multi?pattern matching algorithm is proposed on the basis of introducing the advantages and disadvantages of common pattern matching algorithms， and combining with the idea of converting the Trie tree into the double array form. A comparison experiment was carried out. The analysis results show that the improved AC algorithm can successfully match all the to?be queried pattern strings in the text， and its matching speed is about 5 times of that of the AC algorithm， which shows that the improved AC algorithm has good effects in aspects of matching speed， recall ratio and space utilization rate.

Keywords： character string matching; multi?pattern matching; Trie tree; double array; AC algorithm; matching speed

0 ?引 ?言

當今信息社會，數(shù)據(jù)量空前的龐大，如何快速正確地從百萬字符的文本中找到想要的字符是當前研究的一個熱點，這就催生出字符串模式匹配[1]這個研究領域。模式匹配的概念：字符串模式匹配是從指定的文本當中，通過某種方式找到想要的字符或者字符串。把這個文本稱為目標串，把要找到的字符或者字符串稱為模式串。經(jīng)過幾十年的發(fā)展，字符串模式匹配廣泛應用于計算機、敏感詞檢測、生物學、文本處理、統(tǒng)計等領域。當前也存在許多匹配算法，根據(jù)模式個數(shù)的多少可以分為兩種算法：一種是單模式匹配算法;另一種是多模式匹配算法[2]，單模式匹配代表算法有BF算法、KMP算法、Sunday算法等，多模式匹配算法有AC自動機等[3]。

BF算法是一種最基本的匹配算法，該算法要求逐個比較目標串和模式串中的字符，若匹配正確，則繼續(xù)匹配，否則取當前目標串字符隨后的字符，繼續(xù)與模式串的首字符進行匹配。當目標串和模式串的長度分別為a，b，則BF算法的時間復雜度最大為O（ab），而在一般的實際應用中近似為O（a+b），不過在有些情況下算法效果會大大降低。文獻[4]改良了傳統(tǒng)的BF算法，雖然效率有所提高，但是在某些情況下會出現(xiàn)匹配次數(shù)不減反增的異常情況。

KMP算法的核心思想是假如字符對比不成功，則根據(jù)已匹配成功的子串將模式串向右移動最大的距離后再進行匹配。例如：目標串為“abcabcde”，模式串為“abcabb”，當?shù)?個字符時匹配失敗，這時匹配成功的子串是“abcab”;發(fā)現(xiàn)子串的前綴和后綴都存在“ab”，長度為2，則模式串向右移動2個距離，即從子串的第三個字符“c”與目標串的下一個字符即第7個字符“d”進行比較。由于BF算法的每次移動距離為1，所以KMP算法有著較高的效率，但當目標串和模式串有多個一樣的字符時會重復匹配，這會影響算法的效率。

Sunday算法：當目標串和模式串匹配失敗的時候，Sunday算法會先得到目標串中下一個未匹配的字符，如果該字符在模式串當中，則移動的長度為模式串中最右端的該字符到結束的字符長度，否則移動的長度為模式串的字符個數(shù)加1。例如，目標串為“abcabcde”，模式串為“abcabb”，當?shù)?個字符時匹配失敗，而且目標串的下一個字符為“d”，字符“d”在模式串中未出現(xiàn)，則移動距離為6+1，即字符“e”，用該字符繼續(xù)從模式串的首字符“a”依次進行匹配，對比KMP算法，Sunday移動的距離更大，所以效率更高。文獻[5]改進了該算法，根據(jù)是否滿足條件去掉了冗余的匹配，給出了一種執(zhí)行效率更高的算法。

針對常見模式算法的特點，本文結合Trie樹轉化成雙數(shù)組形式的思想，提出一種改進的快速多模式匹配算法。

1 ?AC算法及雙數(shù)組Trie樹

1.1 ?AC算法

AC（Aho?Corasick）算法屬于多模式匹配算法，能夠從文本中匹配出多個字符串，也能夠得到這些字符串的相關信息，比如位置和總數(shù)。假定目標串T的總長為n，模式串集合為P={p1，p2，…，pm}，則時間復雜度是O（n），也就是在該復雜度內，必定能在n內匹配到所有的模式串，不會受m大小的影響。

AC算法本質上由3張表組成，也就是goto表：字符匹配成功時從一個狀態(tài)轉移到另一個狀態(tài)，根據(jù)全部的模式串創(chuàng)建的狀態(tài)轉移自動機;fail表：字符匹配失敗時從一個狀態(tài)轉移到對應的失敗狀態(tài);output表：是由匹配成功的模式串構成。

設模式串集合P={新疆，美麗的新疆，新中國，新疆大學}，目標串為T=“新疆大學位于新中國美麗的新疆自治區(qū)”，以此為例說明AC算法的構造過程：

步驟1：goto表的構建。用goto（i，c）表示狀態(tài)i匹配字符c后的下一個狀態(tài)，goto表本質上是根據(jù)模式串集合P構造的確定有限狀態(tài)自動機，首先將“新疆”構建到goto表中，用公式表示為goto（1，‘疆）=2，依次將模式串集合中剩余的模式串加入goto表，最終得到如圖1所示的有限狀態(tài)自動機[3]。

步驟2：fail表的構建。fail（i）在狀態(tài)匹配不成功時轉移到下一個狀態(tài)。和狀態(tài)0相鄰的全部狀態(tài)的失敗狀態(tài)均為狀態(tài)0。比如在圖1中，狀態(tài)1與狀態(tài)0相鄰，則fail（1）=0。對于其他與狀態(tài)0不相鄰的狀態(tài)，設當前狀態(tài)為S2，S2前一狀態(tài)為S1，則狀態(tài)S的失敗跳轉狀態(tài)為fail（S）=goto（fail（S1），c）。最終得到的fail表如表1所示。

步驟3：output表的構建。根據(jù)圖1的有限狀態(tài)自動機可知，圓圈帶陰影的4個狀態(tài)是輸出狀態(tài)，當目標串沿著自動機達到這幾個狀態(tài)時，說明匹配成功了相應的模式串。使用output表存儲這一可輸出狀態(tài)，在確定有限狀態(tài)自動機中用背景為灰色的圓圈表示。得到output表如表2所示。

下面進行匹配，匹配的方法：從初始狀態(tài)0開始進行匹配，若字符相同，則根據(jù)完整自動機，當前狀態(tài)跳轉到對應的狀態(tài)，當?shù)竭_可輸出狀態(tài)（背景為陰影的狀態(tài)）時表示模式匹配成功，則根據(jù)output表輸出對應模式串;若字符不同，則當前狀態(tài)變?yōu)閷膄ail狀態(tài)，然后進行下一步匹配。具體過程為：

1） 自動機從0狀態(tài)出發(fā)，首先按照goto表（實線）進行字符匹配;

2） 接收目標串首字符“新”，字符匹配成功，轉移到狀態(tài)1;

3） 接收字符“疆”，字符匹配成功，轉移到狀態(tài)2，因為狀態(tài)2是輸出狀態(tài)，根據(jù)output表輸出模式串“新疆”;

4） 依次接收字符“大”“學”，轉移到狀態(tài)11，根據(jù)output表輸出模式串“新疆大學”;

5） 接收字符“位”，字符匹配失敗，跳轉到狀態(tài)11的失敗狀態(tài)0，同理接收字符“于”，跳轉到狀態(tài)0;

6） 依次接收字符“新”“中”“國”，跳轉到狀態(tài)9，輸出模式串“新中國”;

7） 依次接收字符“美”“麗”“的”“新”“疆”，跳轉到狀態(tài)11，輸出模式串“美麗的新疆”和“新疆”;

8） 最后匹配字符“自”“治”“區(qū)”，無模式串輸出。

1.2 ?雙數(shù)組Trie樹

Trie樹[6]是哈希樹的另一種表示形式，空間復雜度為O（n），數(shù)據(jù)結構通常很繁瑣，占用的空間比較大，為了解決這些問題，Aoe. J用2個數(shù)組構建Trie樹，即雙數(shù)組Trie樹[7?8]。

雙數(shù)組Trie[9]由兩個正數(shù)數(shù)組表示，即base[]和check[]，在數(shù)組中，狀態(tài)和數(shù)組下標是一一對應并且值相等，即狀態(tài)s所對應的數(shù)組下標也是s。狀態(tài)轉移需要滿足式（1）式（2），其中c是收到的字符，s是當前狀態(tài)，t是下一狀態(tài)。

[checkbases+c=s] ? ?（1）

[bases+c=t] ? ? ? ? （2）

狀態(tài)轉移圖如圖3所示。狀態(tài)s所對應的base值為base[s]，接收字符c后轉移到狀態(tài)t，即t=base[s]+c，而狀態(tài)t所對應的check數(shù)組值為s，即check[t]=s。

以圖1為例，結合以上條件構建雙數(shù)組Trie的過程如下：

1） 字符編碼。按照模式串P中字符的入樹順序對字符進行編碼，得到編碼結果為：新?1，美?2，中?3，疆?4，麗?5，國?6，大?7，的?8，學?9。其稱之為字符序列碼表[3] ;

2） 接收字符“新”，由于“新”的序列碼為1，所以對應的數(shù)組位置為1，初始化為base[1]=1，check[0]=0;

3） 接收“中”，在數(shù)組當中的索引值為前一狀態(tài)對應的base值和接收字符的編碼值之和，即base[1]+3=4，因而base[4]=base[1]=1，check[4]=1。接收 “國”，同理，base[base[4]+6]=base[7]=1，check[7]=4。依次接收所有的字符，根據(jù)條件確定相應的值。

4） 如果index對應的是結束狀態(tài)，使base[index]=（-1）* index，比如index=7對應的字符串“新中國”是結束狀態(tài)，則base[7]=-7;如果index對應的是中間輸出狀態(tài)，則base[index]=（-1）*base[index]，比如index=5，“新疆”是輸出狀態(tài)但不是結束狀態(tài)，則令base[5]=（-1）*

base[5]=-1，同理將其他所有結束狀態(tài)設置為相應的值。

最終得到如表3所示的雙數(shù)組表。

匹配過程：以匹配“新中國”為例，接收字符“新”，根據(jù)序列碼表定位到數(shù)組的位置為index=1，base[1]=1為非輸出狀態(tài);繼續(xù)接收字符“中”，定位到index=base[1]+3=4，為非輸出狀態(tài);繼續(xù)接收字符“國”，定位到index=base[4]+1=7，得到base[7]=-7，是輸出狀態(tài)，從而得到匹配結果為“新中國”。

當進行字符個數(shù)為n的單模式字符串查詢時，雙數(shù)組Trie的時間復雜度為O（n），但是對于多模式查詢，首先要進行前綴的匹配，之后通過多次獲得文本后綴方可實現(xiàn)多模式查詢，從而造成進行多次目標串匹配的問題，因而當進行多模式匹配時效率很差。

2 ?改進AC算法

由第1節(jié)可知，AC自動機在多模式匹配方面效率很高，但是占用空間過大;雙數(shù)組Trie樹雖然解決了Trie樹占用空間大的問題，但是在多模式匹配方面性能不理想，所以在此介紹一種結合兩者的改進方法，該方法在保證多模式匹配的前提下盡量提高匹配速度和減少占用的內存。

改進AC算法主要思想：將AC自動機的3張表（goto表、fail表和output表）以數(shù)組的形式表示，與雙數(shù)組Trie樹的base，check數(shù)組相結合，形成一種多數(shù)組關系。

base數(shù)組本質就是一種狀態(tài)轉移，即字符匹配成功跳向下一狀態(tài)，匹配失敗跳向根節(jié)點，所以base數(shù)組與goto表的作用是一樣的，所以只需將剩下的fail表，output表轉換成數(shù)組形式。改進AC算法圖示如圖4所示。

字符匹配流程圖如圖5所示。字符串匹配過程為：

步驟1：初始狀態(tài)o收到字符c;

步驟2：若字符匹配成功，則跳到下一狀態(tài)t=base[s]+c;若字符匹配失敗，則跳到下一狀態(tài)o=fail[s];

步驟3：若base[t]<0（或者base[o]<0），則狀態(tài)t（或者o）是輸出狀態(tài)，輸出模式串output[t]（或者output[o]），否則不輸出;

步驟4：將狀態(tài)t（或者o）設為當前狀態(tài)，取下一個字符，轉到步驟2繼續(xù)匹配，直至目標串中的所有字符完成匹配。

3 ?實驗及結果分析

本實驗的硬件環(huán)境是CPU 3.4 GHz（Intel Core i7 4770），內存為8 GB，64位Windows 10操作系統(tǒng)，軟件使用的是Myecplise 2014。模式串的數(shù)據(jù)來自《現(xiàn)代漢語常用詞匯表》，總計38 285個詞匯，其中雙字詞23 573個、三字詞5 289個、四字詞9 423個;目標串數(shù)據(jù)來自文學作品《平凡的世界》的完整版，大小為2.28 MB，大約共79萬字?？偣策M行兩項實驗，分別為多模式匹配查全率實驗和匹配速度實驗。

3.1 ?多模式匹配查全率實驗

該實驗目的是驗證改進AC算法能否進行多模式匹配，以及能否返回目標串中所有的本文所要匹配的模式串。實驗是以使用Microsoft Word的查找功能得到的結果為比較標準，假如通過Word查找功能得模式串的個數(shù)共有m個，通過改進AC算法得到的模式串的個數(shù)為n個，則查全率R為：

[R=nm] ? ? ? （3）

式中：R的值為1時，說明能夠查找到全部的模式串;越接近于1，說明改進AC算法的查找效果越好。

隨機抽取9個詞語為樣本，作為模式串集合，得到的實驗數(shù)據(jù)及結果如表5所示。

根據(jù)表5中的數(shù)據(jù)和式（3）計算出改進AC算法的查全率R：

[24+19+1+5+121+36+124+16+124+19+1+5+121+36+124+16+1=1]

查全率R為1，說明改進AC算法不僅能夠進行多模式匹配，而且可以匹配到目標串中全部的結果，查全率達到了要求的水平。

3.2 ?匹配速度實驗

該實驗在相同的條件下比較了AC算法和改進AC算法的匹配速度，根據(jù)模式串個數(shù)的不同共進行8組測試，分別為模式串個數(shù)為5 000，10 000，…，35 000和38 285。為了避免由于偶然性所導致的異常結果，每個模式串組分別進行10次匹配，對得到的匹配時間求平均值。最終得到對比結果如圖6所示。

從圖6中可以看出，改進AC算法的匹配時間明顯低于AC算法的匹配時間，在模式串個數(shù)為30 000個時，改進AC算法匹配所有的2.28 MB目標串只需50 ms，匹配速度達到了45.6 MB/s，而AC算法的匹配速度為10.2 MB/s，改進AC算法的匹配速度是原AC算法的4～5倍，說明改進AC算法的匹配速度要遠遠高于AC算法的匹配速度。

4 ?結 ?語

本文介紹AC算法和雙數(shù)組Trie樹的原理，在此基礎之上將雙數(shù)組Trie樹的思想應用于AC算法，也就是用數(shù)組表示AC自動機的多模式匹配算法。通過實驗對比原有算法和改進AC算法的查全率和速度可知：改進AC算法不僅能夠匹配出所有的模式串，而且匹配速度提高了4～5倍，改進AC算法取得了良好的效果。

參考文獻

[1] 蔣莉莉.字符串模式匹配算法的改進研究[J].電腦知識與技術，2008（3）：526?528.

JIANG Lili. The research of improved matching algorithm of string pattern [J]. Computer knowledge and technology， 2008（3）： 526?528.

[2] 張利香.基于后綴數(shù)組的字符串模式查找的算法[D].蘭州：西北師范大學，2010.

ZHANG Lixiang. The string pattern searching algorithms based on suffix arrays [D]. Lanzhou： Northwest Normal University， 2010.

[3] 楊波.基于有限狀態(tài)自動機的中文多模式匹配算法研究[D].合肥：合肥工業(yè)大學，2013.

YANG Bo. Research on multi?pattern matching algorithm for Chinese based on finite state automata [D]. Hefei： Hefei University of Technology， 2013.

[4] 蔡恒，張帥.基于BF算法改進的字符串模式匹配算法[J].電腦編程技巧與維護，2014（22）：14?15.

CAI Heng， ZHANG Shuai. An improved string pattern matching algorithm based on BF algorithm [J]. Computer programming skills & maintenance， 2014（22）： 14?15.

[5] 李明月，張善卿，陸劍鋒，等.一種改進的Sunday匹配算法[J].杭州電子科技大學學報（自然科學版），2015，35（1）：93?96.

LI Mingyue， ZHANG Shanqing， LU Jianfeng， et al. A modified Sunday matching algorithm [J]. Journal of Hangzhou Dianzi University （Natural Sciences）， 2015， 35（1）： 93?96.

[6] 劉麗霞，張志強.基于Trie樹的相似字符串查找算法[J].計算機應用，2013，33（8）：2375?2378.

LIU Lixia， ZHANG Zhiqiang. Similar string search algorithm based on Trie tree [J]. Journal of computer applications， 2013， 33（8）： 2375?2378.

[7] YANG Wenchuan， FANG Zeyang， LI Pengfei. Study for the double?array Trie tree based algorithm in word segmentation [C]// Proceedings of 2015 International Conference on Computer Science and Environmental Engineering. Beijing： DEStech Publications Inc.， 2015： 7.

[8] 徐聰，張豐，杜震洪，等.基于哈希和雙數(shù)組Trie樹的多層次地址匹配算法[J].浙江大學學報（理學版），2014，41（2）：217?222.

XU Cong， ZHANG Feng， DU Zhenhong， et al. A multi?level address?matching algorithm based on Hash function and double?array Trie?tree [J]. Journal of Zhejiang University （Science edition）， 2014， 41（2）： 217?222.

[9] KAROONBOONYANAN T. An implementation of double?array Trie [EB/OL]. [2018?11?21]. https：//linux.thai.net/～thep/datrie/datrie.html.