基于AC_QS多模式匹配算法的優(yōu)化研究

董志鑫+方濱興

摘要：隨著互聯(lián)網(wǎng)的日益強(qiáng)大，互聯(lián)網(wǎng)上數(shù)據(jù)急劇增多，如何在海量的數(shù)據(jù)中快速準(zhǔn)確地找到所需信息，就顯得尤為重要，這就需要多模式串匹配算法。多模式串匹配算法在越來(lái)越多的領(lǐng)域里都有應(yīng)用，比如：信息安全領(lǐng)域中，入侵檢測(cè)系統(tǒng)、防火墻等，在醫(yī)學(xué)領(lǐng)域、數(shù)據(jù)挖掘、信息檢索等等領(lǐng)域中均有廣泛的應(yīng)用。AC算法在多模式串匹配算法中是一個(gè)能達(dá)到線性時(shí)間的算法，其算法效率較高，AC_QS算法是在AC算法基礎(chǔ)上增加壞字符規(guī)則，進(jìn)一步增加了AC算法的匹配效率，但其空間復(fù)雜度較高。本文在AC_QS算法的基礎(chǔ)上，對(duì)算法預(yù)處理和匹配過(guò)程中繼續(xù)優(yōu)化，并對(duì)字典樹存儲(chǔ)時(shí)進(jìn)行了優(yōu)化，使算法在空間和時(shí)間復(fù)雜度上得到進(jìn)一步優(yōu)化，提高了算法性能。實(shí)驗(yàn)結(jié)果也驗(yàn)證了該算法的高效性。

關(guān)鍵詞： 多模式； 模式匹配； AC算法； QS算法

中圖分類號(hào)： TP301

文獻(xiàn)標(biāo)志碼： A

文章編號(hào)： 2095-2163（2017）05-0100-04

Abstract： With the Internet becoming more and more powerful and the data increasing dramatically on the internet， it is very important to find the needed information quickly and accurately in the mass of data， so it is determined to require multipatterns string matching algorithm. Multi-patterns string matching algorithm has been used in more and more fields such as information security， intrusion detection system and firewall， data mining and medicine， and also has a wide range of applications in the field of information retrieval and so on. AC algorithm in multipatterns string matching algorithm is a linear time algorithm， which can achieve high efficiency. AC_QS algorithm is to increase the bad character in the AC algorithm and then improve the matching efficiency of AC algorithm， but its space complexity is high. In this paper， based on the AC_QS algorithm， the algorithm will continue to optimize the preprocessing and matching process， and in the dictionary tree storage are optimized. After that， the algorithm in space/time complexity is further optimized， therefore the algorithm performance is improved. The experimental results also verify the efficiency of the algorithm.

Keywords： multiple patterns； pattern matching； AC algorithm； QS algorithm

0引言

模式串匹配算法，適用于從某個(gè)序列中，找到具有某種屬性的模式段或者位置等信息。其中字符串查找就是最簡(jiǎn)單最常用的模式串匹配問(wèn)題。多模式串匹配算法，就是從某個(gè)序列中，查找發(fā)現(xiàn)多個(gè)屬性的模式段。在現(xiàn)實(shí)的應(yīng)用里，多模式串匹配算法更加常用有效，有著許多典型的應(yīng)用場(chǎng)景和巨大的需求。例如，應(yīng)用在數(shù)據(jù)挖掘領(lǐng)域從新聞流里來(lái)尋找一些被選擇的模式；應(yīng)用在計(jì)算機(jī)、網(wǎng)絡(luò)安全領(lǐng)域中檢測(cè)識(shí)別某些敏感危險(xiǎn)關(guān)鍵詞來(lái)避免計(jì)算機(jī)或者網(wǎng)絡(luò)被攻擊；應(yīng)用在生物信息DNA搜索識(shí)別中[1]，將DNA序列的近似搜索轉(zhuǎn)換為大量精確模式的搜索。

基于現(xiàn)今主要的多模式串匹配算法，本文分析了各主流算法的優(yōu)缺點(diǎn)，考慮到算法的有效實(shí)現(xiàn)的簡(jiǎn)易程度和算法復(fù)雜度等方面，對(duì)AC_QS算法[2]進(jìn)行了優(yōu)化，取得了良好的實(shí)驗(yàn)效果。

1主流多模匹配算法介紹

AC自動(dòng)機(jī)算法[3]對(duì)于多模式串匹配問(wèn)題給出了一個(gè)線性時(shí)間的算法，該算法基于一個(gè)有限自動(dòng)機(jī)。一個(gè)線性時(shí)間的算法在最壞情況下，算法的運(yùn)行效率是具有相當(dāng)優(yōu)勢(shì)的。但另一種單模式串匹配的BM算法[4]，就可以在匹配過(guò)程中進(jìn)行跳躍，在文本匹配過(guò)程中跳過(guò)一部分不可能包括待匹配模式串的文本串繼續(xù)搜索。CW算法[5]就是將上述2種算法進(jìn)行結(jié)合，處理多模式串匹配問(wèn)題，增加了AC算法在模式串匹配過(guò)程中的跳躍距離，減少了比較次數(shù)，算法更高效，但是占用的空間更多。其后，Horspool根據(jù)BM算法提出Horspool算法[6]，該算法考慮了BM算法過(guò)于復(fù)雜，對(duì)算法進(jìn)行了精簡(jiǎn)。Horspool算法應(yīng)用于多模串匹配問(wèn)題中的算法被稱為Set Horspool算法[6]。后來(lái)，Wu與Manber 發(fā)現(xiàn)Set-Horspool算法在多模式串匹配中效果欠佳，提出與模式串結(jié)尾的2個(gè)字符進(jìn)行比較的WM算法[7]。QS算法[8]也是一個(gè)單模式串匹配算法，相對(duì)于較經(jīng)典的單模式匹配KMP算法[9]，該算法在字符串匹配失敗時(shí)，至少能夠保證移動(dòng)一位。AC_QS算法則是將上述2種算法的思想進(jìn)行合并，對(duì)AC算法進(jìn)行了優(yōu)化，使得算法的效率進(jìn)一步提升。在這之后，不斷地出現(xiàn)各種基于AC算法以及其他多模式串匹配算法的優(yōu)化算法。endprint

2優(yōu)化算法DAC_QS算法

本文對(duì)于AC_QS算法的優(yōu)化主要考慮從加大算法跳躍距離和減少每輪匹配字符比較次數(shù)兩方面對(duì)其進(jìn)行改進(jìn)。本文主要在預(yù)處理、字典樹存儲(chǔ)和匹配過(guò)程三個(gè)方面進(jìn)行優(yōu)化，在減少匹配字符的比較次數(shù)上進(jìn)行了一些特殊的優(yōu)化，以達(dá)到提高算法效率的目的。

2.1預(yù)處理的優(yōu)化

首先當(dāng)網(wǎng)絡(luò)上采集到數(shù)據(jù)，對(duì)數(shù)據(jù)分析處理后得到用于串匹配的數(shù)據(jù)，研究中用目標(biāo)串T來(lái)表示。對(duì)于模式集合中的模式串，首先獲得模式串集合的字符集S，即包含所有模式串中的字符的最小集合。對(duì)于目標(biāo)串T中的每個(gè)字符，檢驗(yàn)其是否在字符集S中出現(xiàn)，若字符c未出現(xiàn)在字符集S中，則以該字符為標(biāo)準(zhǔn)對(duì)目標(biāo)串T進(jìn)行分段，字符c前的字符串記為T1，字符c后面的字符記為T2，將字符c刪除；依次繼續(xù)向后進(jìn)行檢驗(yàn)，直到檢驗(yàn)到目標(biāo)串T的最后一個(gè)字符，此時(shí)目標(biāo)串T被分為{ T1，T2，…，Tt+1}，其中t為目標(biāo)串T中不出現(xiàn)在字符集S中的字符個(gè)數(shù)。

因?yàn)樽址疭不會(huì)經(jīng)常變動(dòng)，為了提高查找效率，對(duì)字符集采取哈希表的方式進(jìn)行存儲(chǔ)，提高查找效率，哈希函數(shù)即為每個(gè)字符對(duì)應(yīng)的地址，因每個(gè)字符占用一個(gè)地址，所以不會(huì)出現(xiàn)冗余的情況，具體方法如下：

1）申請(qǐng)一段大小為28=256 B的內(nèi)存M，每個(gè)內(nèi)存地址對(duì)應(yīng)字符集S中的一個(gè)字符。

2）對(duì)于目標(biāo)串中的每個(gè)字符c，計(jì)算其哈希地址，判斷是否在1）中的內(nèi)存表M中，若在則表示該字符在模式串集合S中，即該字符在某個(gè)模式串中。

3）若字符c不在模式串集合S中，將目標(biāo)串T以字符c進(jìn)行分段，字符c前的字符串記為T1，字符c后面的字符記為T2，將字符c刪除。

4）依次繼續(xù)向后進(jìn)行檢驗(yàn)，直到檢驗(yàn)到目標(biāo)串T的最后一個(gè)字符，此時(shí)目標(biāo)串T被分為{T1，T2，…，Tt+1}，其中t為目標(biāo)串T中不出現(xiàn)在字符集S中的字符個(gè)數(shù)。

5）記模式串中最短模式串長(zhǎng)度為PLmin，若在目標(biāo)串T劃分的集合{ T1 ，T2，…，Tt+1}中，刪除其中存在的長(zhǎng)度小于PLmin的目標(biāo)子串Ti，其中0

綜上可得，該優(yōu)化算法的流程如圖1所示。

這種方式處理后，相當(dāng)于把原先在目標(biāo)串與模式串匹配的時(shí)候的比較提前實(shí)現(xiàn)，因而并沒有增加比較次數(shù)，同時(shí)因?yàn)椴捎玫氖枪５刂酚成涞姆椒?，時(shí)間也是相當(dāng)快的，首先若存在上述第5）種情況，則能進(jìn)一步減少比較次數(shù)，減少的比較次數(shù)為刪除的目標(biāo)子串Ti長(zhǎng)度之和，理論最好情況下，是刪除了全部的目標(biāo)子串，不需要進(jìn)行自動(dòng)機(jī)匹配算法，直接可以確定該數(shù)據(jù)不包含模式串。

對(duì)目標(biāo)子串Ti的處理，可以采用2種思路：一是采用并行思想，在多臺(tái)機(jī)器或者多個(gè)并行處理器上運(yùn)行；二是針對(duì)每一個(gè)子串繼續(xù)使用匹配算法進(jìn)行匹配。因?yàn)槟繕?biāo)串的不確定和字符集S的未知，無(wú)法確定具體情形下分出的目標(biāo)子串個(gè)數(shù)，而且目標(biāo)串本身的大小就并未超過(guò)常規(guī)，所以并行的思想并不一定能時(shí)刻發(fā)揮重要作用，且并行的時(shí)間會(huì)高于模式匹配的時(shí)間。針對(duì)每個(gè)目標(biāo)子串進(jìn)行匹配的時(shí)候仍然可以優(yōu)化，以下2節(jié)將介紹具體的優(yōu)化方法。

2.2對(duì)字典Trie樹的優(yōu)化

在利用AC算法建立AC自動(dòng)機(jī)的過(guò)程中，在Trie樹上進(jìn)行優(yōu)化，本文采用建立有序的字典Trie樹的方式，即對(duì)Trie樹的每條分支，Trie樹同一層中表示的字符，左邊小于右邊，這樣當(dāng)對(duì)目標(biāo)串進(jìn)行匹配時(shí)，假設(shè)目標(biāo)待匹配的目標(biāo)串字符為h，總是在字典Trie樹當(dāng)前狀態(tài)的下一層中選擇中間狀態(tài)對(duì)應(yīng)的字符k進(jìn)行比較，若目標(biāo)串中的待匹配字符h大于字符k，則只需在字典樹的右側(cè)進(jìn)行匹配，而無(wú)須比較同一深度內(nèi)左側(cè)的字符；同理，若目標(biāo)串中的待匹配字符h小于字符k，則需在字典樹的左側(cè)進(jìn)行匹配。舉例說(shuō)明如下：

對(duì)于模式集{abc， abd， abe， aee， afc， afd， afe， bd， cbc， cbd， cbe， cef， cmc， cmd， cme}，圖4展示了有序字典Trie的構(gòu)建過(guò)程，構(gòu)建的字典樹如下：

在具體的實(shí)現(xiàn)上，可以對(duì)每個(gè)狀態(tài)設(shè)置一個(gè)新的degree變量，用來(lái)存儲(chǔ)當(dāng)前狀態(tài)的所能達(dá)到的下一狀態(tài)的總數(shù)和，即相當(dāng)于樹的出度，當(dāng)degree>2時(shí)，對(duì)此算法的優(yōu)勢(shì)即能體現(xiàn)出來(lái)，每次從degree/2所對(duì)應(yīng)的狀態(tài)開始比較。

該方法在字典樹中的分布比較平均，每一狀態(tài)所對(duì)應(yīng)的下一狀態(tài)較多，即對(duì)應(yīng)較多的分支時(shí)，可明顯減少比較次數(shù)，相當(dāng)于二分查找，最優(yōu)時(shí)間復(fù)雜度可達(dá)到O（log n），平均情況也明顯好于未排序的Trie字典樹。但此方法在建立字典樹時(shí)會(huì)造成一定的時(shí)間和空間開銷，但這都是在預(yù)處理時(shí)可以做到的，對(duì)于高效的匹配來(lái)說(shuō)是值得的。

[BT5]2.3匹配過(guò)程中的優(yōu)化

在實(shí)際中，可能存在這樣的情況：某個(gè)或者某幾個(gè)模式串并沒有在目標(biāo)串中出現(xiàn)，但是如果單純地計(jì)算每個(gè)模式串中的每個(gè)字符在目標(biāo)串中出現(xiàn)時(shí)，會(huì)花費(fèi)大量的時(shí)間，特別是當(dāng)模式串和目標(biāo)串都比較有規(guī)模的情況下。因此，本文利用每個(gè)模式串的最后2個(gè)字符，若最后2個(gè)字符未在目標(biāo)文本中出現(xiàn)，則表示該模式串肯定不在目標(biāo)文本中出現(xiàn)，相對(duì)于完整的查找比較，可以大量減少比較次數(shù)，查找較高效。同時(shí)，因?yàn)樵撨^(guò)程與模式匹配屬于不同的處理過(guò)程，可以并行運(yùn)行，在時(shí)效要求較高的時(shí)候可以采用一邊對(duì)目標(biāo)串進(jìn)行串匹配，另一邊并行地運(yùn)行查找。

在并行處理的時(shí)候，需要對(duì)字典樹進(jìn)行相應(yīng)的處理，最簡(jiǎn)單的處理為：當(dāng)發(fā)現(xiàn)某個(gè)模式串最后2個(gè)字符未在目標(biāo)串中出現(xiàn)時(shí)，直接將字典樹中的該節(jié)點(diǎn)置為NONE，在自動(dòng)機(jī)匹配時(shí)遇見為NONE的節(jié)點(diǎn)，不進(jìn)行比較，直接利用fail函數(shù)進(jìn)行跳轉(zhuǎn)。因?yàn)槭遣⑿羞M(jìn)行的，提高了總的匹配效率。每檢查出一個(gè)模式串不在目標(biāo)串中，就可以減少一次比較次數(shù)，但這種處理在實(shí)際效果中提高甚是有限，除非遇到特定的數(shù)據(jù)。

然后提出了另一種處理方法：當(dāng)檢測(cè)到某個(gè)模式串未在目標(biāo)串中出現(xiàn)時(shí)，從頭開始對(duì)字典樹進(jìn)行掃描，找到未匹配串，若該串只有自己一條分支，則將該串上的所有值置為NONE，所有fail函數(shù)指針指向root；否則找到該串中只有自己的部分分支，即由父狀態(tài)只通過(guò)一個(gè)字符到達(dá)該模式中該字符的狀態(tài)，而沒有其他狀態(tài)，并且該狀態(tài)的所有子狀態(tài)也只有一個(gè)狀態(tài)，即按照從下到上的方式，找到2.2節(jié)中該模式串對(duì)應(yīng)的degree連續(xù)為1的最上狀態(tài)，將該狀態(tài)的上一狀態(tài)所對(duì)應(yīng)的字符置為NONE，fail函數(shù)指針指向root，該狀態(tài)的degree減一，該狀態(tài)之后的狀態(tài)則不會(huì)被訪問(wèn)到，相當(dāng)于刪除。該方法的流程圖如圖3所示。

上述方法的舉例說(shuō)明如下：針對(duì)圖2中的有序字典樹，若檢測(cè)到模式串cef不在當(dāng)前匹配的目標(biāo)串中，發(fā)現(xiàn)狀態(tài)8的degree為1，繼續(xù)向上，發(fā)現(xiàn)狀態(tài)3的degree不為1，將狀態(tài)8所對(duì)應(yīng)的字符e設(shè)置為NONE，同時(shí)將狀態(tài)3對(duì)應(yīng)的fail函數(shù)指針指向root。

并行的時(shí)候并不會(huì)發(fā)生阻塞，是因?yàn)槠ヅ溥^(guò)程是對(duì)字典樹進(jìn)行訪問(wèn)，并不改變字典樹的值，而只有上述方法的進(jìn)程改變字典樹，只有一個(gè)寫進(jìn)程，所以，并不會(huì)發(fā)生阻塞。

3實(shí)驗(yàn)

為了對(duì)上述優(yōu)化算法進(jìn)行合理全面的驗(yàn)證，本節(jié)中將針對(duì)正常的AC_QS算法和優(yōu)化后的算法在相同環(huán)境下，對(duì)同樣的模式串和目標(biāo)串進(jìn)行驗(yàn)證，驗(yàn)證的主要標(biāo)準(zhǔn)是比較運(yùn)行后的時(shí)間效率，通過(guò)對(duì)結(jié)果的分析得出最終結(jié)論。

3.1實(shí)驗(yàn)環(huán)境

操作系統(tǒng)：Ubuntu 16.04（64位）；

處理器：Intel（R）Core（TM） i7-2670QM CPU @ 2.20 GHz；

處理器核心數(shù)：4核；

編譯器：gcc version 5.4.0；

編程語(yǔ)言：c語(yǔ)言。

[BT5]3.2實(shí)驗(yàn)結(jié)果

因本文主要研究算法的高效性，而且是在線匹配的高效，所以只對(duì)2種算法的匹配時(shí)間效率進(jìn)行分析，暫不考慮算法的空間效率（占用內(nèi)存大?。┖退惴ǖ念A(yù)處理時(shí)間。

[JP2]實(shí)驗(yàn)選擇數(shù)據(jù)中，測(cè)試目標(biāo)文本大小分別為：10 M、100 M、500 M、[JP]1 024 M；模式串集個(gè)數(shù)分別為10、100、300，模式串長(zhǎng)度則為5-1 000內(nèi)，任意長(zhǎng)度。

當(dāng)模式串個(gè)數(shù)固定為300時(shí)，對(duì)應(yīng)不同的目標(biāo)文本長(zhǎng)度，算法測(cè)試數(shù)據(jù)結(jié)果如表1所示。

2種算法對(duì)不同目標(biāo)文本效率對(duì)比則如圖4所示。

2種算法對(duì)不同模式串個(gè)數(shù)效率對(duì)比即如圖5所示。

3.3實(shí)驗(yàn)分析

通過(guò)對(duì)以上結(jié)果的分析，可以得出本文所提出的優(yōu)化算法在效率上具有更好的匹配效率，能達(dá)到15%左右的優(yōu)化幅度，跟模式串的個(gè)數(shù)和文本大小關(guān)系不大。

4結(jié)束語(yǔ)

本文在AC_QS算法的基礎(chǔ)上，對(duì)原算法運(yùn)行過(guò)程中的幾

[LL]個(gè)重要步驟：模式串預(yù)處理、字典樹存儲(chǔ)和匹配過(guò)程中提出了針對(duì)性的優(yōu)化，提出了DAC_QS算法，實(shí)驗(yàn)結(jié)果顯示，提出的優(yōu)化算法在空間和時(shí)間復(fù)雜度上得到進(jìn)一步優(yōu)化，在效率上具有更好的匹配效率，能達(dá)到15%左右的優(yōu)化幅度，證明了DAC_QS算法的有效性。

參考文獻(xiàn)ALTSCHUL S F， GISH W， MILLER W， et al， Basic local alignment search tool[J]. J. Molecular Biology， 1990，215（3）：403-410.

[2]FAN J J， SU K Y. An efficient algorithm for matching multiple patterns[J]. IEEE Transactions on Knowledge and Data Engineering， 1993，5（2）：339-351.

[3] AHO A V， CORASICK M J. Efficient string matching： An aid to bibliographic search[J]. Communications of the ACM， 1975， 18（6）：333-340.

[4]BOYER R S. MOORE J S. A fast string searching algorithm[J]. Communications of the ACM，1977，20（10）：762-772.

[5] COMMENTZWALTER B.A string matching algorithm fast on the average[C]//Proc. 6th International Colloquium on Automata， Languages， and Programming. London， UK：ACM， 1979：118-132.

[6]HORSPOOL R N. Practical fast searching in strings[J]. Software Practice and Experience， 1980，10（6）：501-506.

[7] WU Sun， MANBER U. A fast algorithm for multipattern searching[R]. Tucson， AZ：University of Arizona， 1994.

[8] [JP4]SUNDAY D M. A very fast substring search algorithm[J]. Communications of the ACM，1990，33（8）：132-142.

[9] KNUTH D E， Jr MORRIS J H， PRATT V R. Fast pattern matching in strings[J]. SIAM Journal on Computing，1976（2）：323-350.[endprint