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

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

中圖分類號： TN919?34; TP301.6 ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識碼： 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 ?引 ?言

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

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

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

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

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

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

1.1 ?AC算法

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

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

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

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

步驟2：fail表的構(gòu)建。fail（i）在狀態(tài)匹配不成功時(shí)轉(zhuǎn)移到下一個(gè)狀態(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)，設(shè)當(dāng)前狀態(tài)為S2，S2前一狀態(tài)為S1，則狀態(tài)S的失敗跳轉(zhuǎn)狀態(tài)為fail（S）=goto（fail（S1），c）。最終得到的fail表如表1所示。

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

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

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

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

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

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

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

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

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

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

1.2 ?雙數(shù)組Trie樹

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

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

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

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

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

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

1） 字符編碼。按照模式串P中字符的入樹順序?qū)ψ址M(jìn)行編碼，得到編碼結(jié)果為：新?1，美?2，中?3，疆?4，麗?5，國?6，大?7，的?8，學(xué)?9。其稱之為字符序列碼表[3] ;

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

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

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

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

最終得到如表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)，從而得到匹配結(jié)果為“新中國”。

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

2 ?改進(jìn)AC算法

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

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

base數(shù)組本質(zhì)就是一種狀態(tài)轉(zhuǎn)移，即字符匹配成功跳向下一狀態(tài)，匹配失敗跳向根節(jié)點(diǎn)，所以base數(shù)組與goto表的作用是一樣的，所以只需將剩下的fail表，output表轉(zhuǎn)換成數(shù)組形式。改進(jìn)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）設(shè)為當(dāng)前狀態(tài)，取下一個(gè)字符，轉(zhuǎn)到步驟2繼續(xù)匹配，直至目標(biāo)串中的所有字符完成匹配。

3 ?實(shí)驗(yàn)及結(jié)果分析

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

3.1 ?多模式匹配查全率實(shí)驗(yàn)

該實(shí)驗(yàn)?zāi)康氖球?yàn)證改進(jìn)AC算法能否進(jìn)行多模式匹配，以及能否返回目標(biāo)串中所有的本文所要匹配的模式串。實(shí)驗(yàn)是以使用Microsoft Word的查找功能得到的結(jié)果為比較標(biāo)準(zhǔn)，假如通過Word查找功能得模式串的個(gè)數(shù)共有m個(gè)，通過改進(jìn)AC算法得到的模式串的個(gè)數(shù)為n個(gè)，則查全率R為：

[R=nm] ? ? ? （3）

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

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

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

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

查全率R為1，說明改進(jìn)AC算法不僅能夠進(jìn)行多模式匹配，而且可以匹配到目標(biāo)串中全部的結(jié)果，查全率達(dá)到了要求的水平。

3.2 ?匹配速度實(shí)驗(yàn)

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

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

4 ?結(jié) ?語

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

參考文獻(xiàn)

[1] 蔣莉莉.字符串模式匹配算法的改進(jìn)研究[J].電腦知識與技術(shù)，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].蘭州：西北師范大學(xué)，2010.

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

[3] 楊波.基于有限狀態(tài)自動機(jī)的中文多模式匹配算法研究[D].合肥：合肥工業(yè)大學(xué)，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ìn)的字符串模式匹配算法[J].電腦編程技巧與維護(hù)，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] 李明月，張善卿，陸劍鋒，等.一種改進(jìn)的Sunday匹配算法[J].杭州電子科技大學(xué)學(xué)報(bào)（自然科學(xué)版），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] 劉麗霞，張志強(qiáng).基于Trie樹的相似字符串查找算法[J].計(jì)算機(jī)應(yīng)用，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].浙江大學(xué)學(xué)報(bào)（理學(xué)版），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.