基于AC_QS多模式匹配算法的優化研究

董志鑫+方濱興

摘要：隨著互聯網的日益強大，互聯網上數據急劇增多，如何在海量的數據中快速準確地找到所需信息，就顯得尤為重要，這就需要多模式串匹配算法。多模式串匹配算法在越來越多的領域里都有應用，比如：信息安全領域中，入侵檢測系統、防火墻等，在醫學領域、數據挖掘、信息檢索等等領域中均有廣泛的應用。AC算法在多模式串匹配算法中是一個能達到線性時間的算法，其算法效率較高，AC_QS算法是在AC算法基礎上增加壞字符規則，進一步增加了AC算法的匹配效率，但其空間復雜度較高。本文在AC_QS算法的基礎上，對算法預處理和匹配過程中繼續優化，并對字典樹存儲時進行了優化，使算法在空間和時間復雜度上得到進一步優化，提高了算法性能。實驗結果也驗證了該算法的高效性。

關鍵詞： 多模式； 模式匹配； AC算法； QS算法

中圖分類號： TP301

文獻標志碼： A

文章編號： 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引言

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

基于現今主要的多模式串匹配算法，本文分析了各主流算法的優缺點，考慮到算法的有效實現的簡易程度和算法復雜度等方面，對AC_QS算法[2]進行了優化，取得了良好的實驗效果。

1主流多模匹配算法介紹

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

2優化算法DAC_QS算法

本文對于AC_QS算法的優化主要考慮從加大算法跳躍距離和減少每輪匹配字符比較次數兩方面對其進行改進。本文主要在預處理、字典樹存儲和匹配過程三個方面進行優化，在減少匹配字符的比較次數上進行了一些特殊的優化，以達到提高算法效率的目的。

2.1預處理的優化

首先當網絡上采集到數據，對數據分析處理后得到用于串匹配的數據，研究中用目標串T來表示。對于模式集合中的模式串，首先獲得模式串集合的字符集S，即包含所有模式串中的字符的最小集合。對于目標串T中的每個字符，檢驗其是否在字符集S中出現，若字符c未出現在字符集S中，則以該字符為標準對目標串T進行分段，字符c前的字符串記為T1，字符c后面的字符記為T2，將字符c刪除；依次繼續向后進行檢驗，直到檢驗到目標串T的最后一個字符，此時目標串T被分為{ T1，T2，…，Tt+1}，其中t為目標串T中不出現在字符集S中的字符個數。

因為字符集S不會經常變動，為了提高查找效率，對字符集采取哈希表的方式進行存儲，提高查找效率，哈希函數即為每個字符對應的地址，因每個字符占用一個地址，所以不會出現冗余的情況，具體方法如下：

1）申請一段大小為28=256 B的內存M，每個內存地址對應字符集S中的一個字符。

2）對于目標串中的每個字符c，計算其哈希地址，判斷是否在1）中的內存表M中，若在則表示該字符在模式串集合S中，即該字符在某個模式串中。

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

4）依次繼續向后進行檢驗，直到檢驗到目標串T的最后一個字符，此時目標串T被分為{T1，T2，…，Tt+1}，其中t為目標串T中不出現在字符集S中的字符個數。

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

綜上可得，該優化算法的流程如圖1所示。

這種方式處理后，相當于把原先在目標串與模式串匹配的時候的比較提前實現，因而并沒有增加比較次數，同時因為采用的是哈希地址映射的方法，時間也是相當快的，首先若存在上述第5）種情況，則能進一步減少比較次數，減少的比較次數為刪除的目標子串Ti長度之和，理論最好情況下，是刪除了全部的目標子串，不需要進行自動機匹配算法，直接可以確定該數據不包含模式串。

對目標子串Ti的處理，可以采用2種思路：一是采用并行思想，在多臺機器或者多個并行處理器上運行；二是針對每一個子串繼續使用匹配算法進行匹配。因為目標串的不確定和字符集S的未知，無法確定具體情形下分出的目標子串個數，而且目標串本身的大小就并未超過常規，所以并行的思想并不一定能時刻發揮重要作用，且并行的時間會高于模式匹配的時間。針對每個目標子串進行匹配的時候仍然可以優化，以下2節將介紹具體的優化方法。

2.2對字典Trie樹的優化

在利用AC算法建立AC自動機的過程中，在Trie樹上進行優化，本文采用建立有序的字典Trie樹的方式，即對Trie樹的每條分支，Trie樹同一層中表示的字符，左邊小于右邊，這樣當對目標串進行匹配時，假設目標待匹配的目標串字符為h，總是在字典Trie樹當前狀態的下一層中選擇中間狀態對應的字符k進行比較，若目標串中的待匹配字符h大于字符k，則只需在字典樹的右側進行匹配，而無須比較同一深度內左側的字符；同理，若目標串中的待匹配字符h小于字符k，則需在字典樹的左側進行匹配。舉例說明如下：

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

在具體的實現上，可以對每個狀態設置一個新的degree變量，用來存儲當前狀態的所能達到的下一狀態的總數和，即相當于樹的出度，當degree>2時，對此算法的優勢即能體現出來，每次從degree/2所對應的狀態開始比較。

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

[BT5]2.3匹配過程中的優化

在實際中，可能存在這樣的情況：某個或者某幾個模式串并沒有在目標串中出現，但是如果單純地計算每個模式串中的每個字符在目標串中出現時，會花費大量的時間，特別是當模式串和目標串都比較有規模的情況下。因此，本文利用每個模式串的最后2個字符，若最后2個字符未在目標文本中出現，則表示該模式串肯定不在目標文本中出現，相對于完整的查找比較，可以大量減少比較次數，查找較高效。同時，因為該過程與模式匹配屬于不同的處理過程，可以并行運行，在時效要求較高的時候可以采用一邊對目標串進行串匹配，另一邊并行地運行查找。

在并行處理的時候，需要對字典樹進行相應的處理，最簡單的處理為：當發現某個模式串最后2個字符未在目標串中出現時，直接將字典樹中的該節點置為NONE，在自動機匹配時遇見為NONE的節點，不進行比較，直接利用fail函數進行跳轉。因為是并行進行的，提高了總的匹配效率。每檢查出一個模式串不在目標串中，就可以減少一次比較次數，但這種處理在實際效果中提高甚是有限，除非遇到特定的數據。

然后提出了另一種處理方法：當檢測到某個模式串未在目標串中出現時，從頭開始對字典樹進行掃描，找到未匹配串，若該串只有自己一條分支，則將該串上的所有值置為NONE，所有fail函數指針指向root；否則找到該串中只有自己的部分分支，即由父狀態只通過一個字符到達該模式中該字符的狀態，而沒有其他狀態，并且該狀態的所有子狀態也只有一個狀態，即按照從下到上的方式，找到2.2節中該模式串對應的degree連續為1的最上狀態，將該狀態的上一狀態所對應的字符置為NONE，fail函數指針指向root，該狀態的degree減一，該狀態之后的狀態則不會被訪問到，相當于刪除。該方法的流程圖如圖3所示。

上述方法的舉例說明如下：針對圖2中的有序字典樹，若檢測到模式串cef不在當前匹配的目標串中，發現狀態8的degree為1，繼續向上，發現狀態3的degree不為1，將狀態8所對應的字符e設置為NONE，同時將狀態3對應的fail函數指針指向root。

并行的時候并不會發生阻塞，是因為匹配過程是對字典樹進行訪問，并不改變字典樹的值，而只有上述方法的進程改變字典樹，只有一個寫進程，所以，并不會發生阻塞。

3實驗

為了對上述優化算法進行合理全面的驗證，本節中將針對正常的AC_QS算法和優化后的算法在相同環境下，對同樣的模式串和目標串進行驗證，驗證的主要標準是比較運行后的時間效率，通過對結果的分析得出最終結論。

3.1實驗環境

操作系統：Ubuntu 16.04（64位）；

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

處理器核心數：4核；

編譯器：gcc version 5.4.0；

編程語言：c語言。

[BT5]3.2實驗結果

因本文主要研究算法的高效性，而且是在線匹配的高效，所以只對2種算法的匹配時間效率進行分析，暫不考慮算法的空間效率（占用內存大小）和算法的預處理時間。

[JP2]實驗選擇數據中，測試目標文本大小分別為：10 M、100 M、500 M、[JP]1 024 M；模式串集個數分別為10、100、300，模式串長度則為5-1 000內，任意長度。

當模式串個數固定為300時，對應不同的目標文本長度，算法測試數據結果如表1所示。

2種算法對不同目標文本效率對比則如圖4所示。

2種算法對不同模式串個數效率對比即如圖5所示。

3.3實驗分析

通過對以上結果的分析，可以得出本文所提出的優化算法在效率上具有更好的匹配效率，能達到15%左右的優化幅度，跟模式串的個數和文本大小關系不大。

4結束語

本文在AC_QS算法的基礎上，對原算法運行過程中的幾

[LL]個重要步驟：模式串預處理、字典樹存儲和匹配過程中提出了針對性的優化，提出了DAC_QS算法，實驗結果顯示，提出的優化算法在空間和時間復雜度上得到進一步優化，在效率上具有更好的匹配效率，能達到15%左右的優化幅度，證明了DAC_QS算法的有效性。

參考文獻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