基于有序二叉樹的快速多模式字符串匹配算法

1、 42基于有序二叉樹的快速多模式字符串匹配算法周 燕 1,侯整風(fēng) 1,何 玲 2(1. 合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院,合肥 230009; 2. 深圳金山信息安全技術(shù)有限公司,深圳 518057摘 要:將有序二叉樹和 QS 算法相結(jié)合,提出一種快速多模式字符串匹配算法,實(shí)現(xiàn)在多模式匹配過程中不匹配字符的連續(xù)跳躍。為提 高匹配速度,利用已匹配的字符串信息進(jìn)行跳躍式的比較,避免文本掃描指針的回溯。實(shí)驗(yàn)結(jié)果表明,與 SMA 算法相比,該算法在預(yù)處 理階段構(gòu)造速度和匹配速度更快,在模式串較長的情況下,性能更優(yōu)越。 關(guān)鍵詞:有序二叉樹;多模式匹配; QS 算法Fast Multi-pattern Str

2、ing Matching AlgorithmBased on Sequential Binary TreeZHOU Yan1, HOU Zheng-feng1, HE Ling2(1. School of Computer and Information, Hefei University of Technology, Hefei 230009; 2. Shenzhen Kingsoft Information Security Technology Co., Ltd., Shenzhen 518057【 Abstract 】 This paper combines sequential bi

3、nary tree with Quick Search(QS algorithm to propose a fast multi-pattern string matching algorithm, which achieves better performance by shifting unmatched characters continuously in the process of multi-pattern matching. It uses jump comparison with unmatched strings to enhance the speed and decrea

4、se character matching operations. Experimental results demonstrate that the algorithm constructs more quickly in preprocessing process and its search speed is higher than SMA algorithm. It achieves better performance in the cases of longer string patterns.【 Key words】 sequential binary tree; multi-p

5、attern matching; Quick Search(QS algorithm計(jì) 算 機(jī) 工 程 Computer Engineering第 36卷 第 17期Vol.36 No.17 2010年 9月September 2010·軟件技術(shù)與數(shù)據(jù)庫· 文章編號:1000 3428(201017 0042 03文獻(xiàn)標(biāo)識碼:A中圖分類號:TP3931 概述模式匹配是指在文本序列 Text=t0t1t2 tn-1中檢索子串 Pattern=p0p1p2 pm-1的問題。 模式匹配廣泛應(yīng) 用于入侵檢測系統(tǒng)、內(nèi)容過濾防火墻、計(jì)算機(jī)病毒特征碼匹 配以及 DNA 序列匹配等領(lǐng)域,研

6、究高效的模式匹配算法具 有非常重要的理論和現(xiàn)實(shí)意義。模式匹配可分為單模式匹配 和多模式匹配。單模式匹配算法一次只能對模式串進(jìn)行一個 模 式 匹 配 , 主 要 有 KMP(Knuth-Morris-Patt算 法 1、 BM (Boyer-Moore算法 2、 QS(Quick Search算法 3等。多模式匹 配算法一次可對模式串同時(shí)進(jìn)行多個模式匹配,包括 AC (Aho-Corasick算法 4、 WM(Wu-Manber算法 5、 AC-BM 算 法 6等。 AC 算法是一種基于自動機(jī)的算法, 首先根據(jù)模式集 構(gòu)建一棵搜索樹,然后對待搜索文本從左至右進(jìn)行掃描。由 于搜索樹的大小與字符集的

7、大小有關(guān),因此 AC 算法一般需 要較大的內(nèi)存資源。 WM 算法主要特點(diǎn)是采用了 BM 算法的 不良字符轉(zhuǎn)移機(jī)制, 利用塊字符擴(kuò)展了不良字符轉(zhuǎn)移的效果, 同時(shí)使用散列表篩選匹配階段應(yīng)進(jìn)行匹配的模式串,減少了 匹配計(jì)算量,因此,應(yīng)用性能較好。 AC-BM 算法基于 BM 算 法,將不同的規(guī)則放在一棵樹上進(jìn)行同時(shí)搜索匹配,能對目 標(biāo)串進(jìn)行跳躍式搜索。文獻(xiàn) 7提出的 SMA 算法采用有序二 叉樹結(jié)構(gòu)來組織有限狀態(tài)自動機(jī),解決了 AC 算法中有限狀 態(tài)自動機(jī)構(gòu)造速度慢、占用內(nèi)存大的問題,但是該算法在查 找過程中必須檢查每一個字符,降低了算法的查找效率。本 文在 SMA 算法的基礎(chǔ)上,吸收 QS 算法的

8、思想,利用匹配過 程中匹配失敗的信息,達(dá)到最大跳躍距離,實(shí)現(xiàn)了快速的多 模式匹配,提高了算法的性能。2 本文的快速多模式字符串匹配算法本文算法分為 2個階段:模式集的預(yù)處理階段和文本的匹配階段。在預(yù)處理階段,借鑒 SMA 算法的思想,對所有待匹配 的模式進(jìn)行分析和處理,構(gòu)造一個關(guān)于這些模式的有序二叉 樹,并計(jì)算失配后文本指針的跳躍和新狀態(tài)。在模式匹配階段,利用建立好的有序二叉樹對文本進(jìn)行 一次性的搜索,同時(shí)結(jié)合 QS 算法思想,以獲得足夠多的跳 躍信息和盡量少的比較次數(shù),從而提高匹配效率。對于待匹配模式集,預(yù)處理過程只需進(jìn)行一次,就可以 經(jīng)過一次掃描從文本串中查找出所有與給定模式串集合中任 何

9、模式串相同的子字符串。2.1 預(yù)處理階段讀取模式串集合 (各模式一般不是按字典序排列的 中的基金項(xiàng)目:安徽省自然科學(xué)基金資助項(xiàng)目 (090412051;廣東省教育 部產(chǎn)學(xué)研結(jié)合基金資助項(xiàng)目 (2008B090500240 43所有模式,利用 SMA 算法中建立有序二叉樹的子算法構(gòu)造 一棵有序二叉樹,將樹的節(jié)點(diǎn)作為自動機(jī)的狀態(tài),樹的分支 作為自動機(jī)的狀態(tài)轉(zhuǎn)移函數(shù), 得到狀態(tài)轉(zhuǎn)移函數(shù) GOTO(state, character 。例如,若給定模式串集合 adds, mini, admin, sad, hads,其對應(yīng)的有序二叉樹如圖 1所示。 圖 1 有限自動機(jī)的有序二叉樹結(jié)構(gòu)計(jì)算失配后文本指針的

10、跳躍和新狀態(tài),結(jié)果用一個表 move 保存, movesc=(skip, newstate,表示在狀態(tài) s 失配 且向前看的文本字符為 c 時(shí),文本掃描指針向前跳躍 skip 個 位置,并從狀態(tài) newstate 開始繼續(xù)比較。計(jì)算失配后的文本 指針跳躍和新狀態(tài)算法描述見算法 1,其中, skip 的計(jì)算方 法如下:minlen -k +1 if cPatternskip =minlen lastck+1 if c Pattern 其中, k 為狀態(tài) s 的深度; minlen 為最短模式的長度; lastc為 c 在 p i 中最末出現(xiàn)的位置。算法 1 計(jì)算失配后文本指針跳躍和新狀態(tài) 輸入

11、根節(jié)點(diǎn)為 root 的有序二叉樹輸出 保存失配后文本指針的跳躍和新狀態(tài)的 move 表 (1minlen最短模式的長度。(2對每個 c , lastc初始化為 0。 (3建立隊(duì)列 queue ,并置空。(4對每個滿足 GOTO(root,c fail 的字符 c(即位于有序 二叉樹的深度為 1的字符 ,進(jìn)行以下操作:1lastc 1;2s GOTO(root,c; 3s.failstate root ; 4s 進(jìn)入隊(duì)列 queue 。 (5當(dāng)隊(duì)列 queue 不為空, 進(jìn)行以下循環(huán) (計(jì)算每個狀態(tài)的 failstate 和每個字符的 lastc:1s 隊(duì)列 queue 的隊(duì)頭元素出隊(duì)。2 對每

12、個滿足 GOTO(s,c fail 的字符進(jìn)行以下操作: s1 GOTO(s,c; fail_s s.failstate ;若 GOTO(fail_s, c=fail ,則 s1.failstate=root;否則, s1.failstate GOTO(fail_s,c; s1進(jìn)入隊(duì)列 queue ;若 s1在有序二叉樹中的深度小于等于 minlen ,則 lastc s1在有序二叉樹中的深度;否則, lastc 0;(6對自動機(jī)中的每個狀態(tài) s 和每個 c 進(jìn)行以下操作 (計(jì)算 movesc:1k 狀態(tài) s 在有序二叉樹中的深度;2 若 c ,則 movesc.skip minlen-las

13、tc-k+1; 3 若 movesc.skip 0,則 movesc.newstate root ; 否則, movesc.newstate s.failstate , movesc.skip 0。例如,對于圖 1所示的例子,用算法 1建立的 move表如表 1所示,其中,表格的第 1列表示狀態(tài);第 1行表示 向前看的字符;二元組表示 (skip, newstate。表 1 move表狀態(tài)h a d,m else0 (3,0 (2,0 (1,0 (4,0 1 (2,0 (1,0 (0,0 (3,0 2 (1,0 (0,0 (0,0 (2,0 3 (0,0 (0,0 (0,0 (1,0 4 (0

14、,16 (0,16 (0,16 (0,0 5 (0,12 (0,12 (0,12 (1,0 6 (0,13 (0,13 (0,13 (0,0 2.2 模式匹配階段在匹配過程中,利用預(yù)處理階段構(gòu)造的有序二叉樹和失 配轉(zhuǎn)移表 move 對文本串進(jìn)行一次性的搜索,查找文本是否 包含模式集中的模式。例如,根據(jù)圖 1的有序二叉樹對文本 進(jìn)行搜索,從狀態(tài) 0開始,根據(jù)當(dāng)前的狀態(tài)和從文本中讀入 的字符決定下一個狀態(tài)。若進(jìn)入終止?fàn)顟B(tài),表示已找到一個 匹配的模式。若根據(jù)當(dāng)前狀態(tài)和讀入的字符找不到下一個狀 態(tài),表示出現(xiàn)失配情況。出現(xiàn)失配后,本算法利用已匹配的信息,通過向右看文 本的一個字符實(shí)現(xiàn)跳躍式比較的方法,避

15、免了文本掃描指針 的回溯,減少了比較的次數(shù)。失配后,有序二叉樹至少要向 前移動一個位置,若要匹配成功,前方的字符必須在成功匹 配的模式中出現(xiàn),因此,以最短模式為標(biāo)準(zhǔn)向右看文本的一 個字符,并計(jì)算該字符在所有模式中最后出現(xiàn)的位置,然后 把整個有序二叉樹移動若干位,使該字符與其在模式中最后 出現(xiàn)的位置對齊,從而跳過一些不必要的比較。算法 2 模式匹配算法輸入 文本串 T1:n,根為 root 的有序二叉樹, move 表 輸出 匹配成功的模式串在文本中出現(xiàn)的位置(1minlen最短模式的長度,初始化文本掃描指針 i 1, 初始化當(dāng)前狀態(tài) s 0。(2當(dāng) i n ,進(jìn)行以下循環(huán): 1c Ti。2 若

16、 GOTO(s,c fail ,則: s GOTO(s,c;若 s.output 為 true ,則輸出 i ; i i+1。3 若 GOTO(s,c=fail(即出現(xiàn)失配情況 ,則:計(jì)算向前看的字符的位置 k minlen-s 所處的層次 +1; 向前看的字符為 ch Ti+k; 44 若 ch , 則 文 本 指 針 跳 躍 到 新 位 置 i i+ movesch.skip,新狀態(tài)為 s movesch.newstate;否則, 文本指針跳躍到新位置 i i+minlen-s所處的層次 +1,新狀態(tài) 為 s root 。2.3 示例選取含有 5個模式串的模式串集合 P=adds, min

17、i, admin, sad, hads,若文本串為 T=addsxyzxmini,用算法 2在文本串 T 中查找模式串 P 中的任一模式串。模式串集合轉(zhuǎn)換成的有 序二叉樹如圖 1所示,最短模式長度 minlen=3,匹配過程如 圖 2所示。字符比較 狀態(tài) s(skip,state輸出 addsxyzxmini addsxyzxmini addsxyzxmini addsxyzxmini addsxyzxmini addsxyzxmini addsxyzxmini addsxyzxmini addsxyzxmini addsxyzxmini 圖 2 模式串匹配過程3 算法分析設(shè)模式串集合的模式個

18、數(shù)為 k , 長度分別為 l 1, l 2, , l k , 所 有模式串的長度之和為 1ki i l =,其中,模式串的最短長度為minlen ;字符集的大小為 ;待搜索文本串的長度為 n 。算法分析分預(yù)處理和匹配 2個階段進(jìn)行。在預(yù)處理階段,構(gòu)造有序二叉樹的時(shí)間復(fù)雜度為 O (k , 算法 1中,計(jì)算 failstate 的時(shí)間復(fù)雜度主要由內(nèi)層循環(huán)決定, 為 O (1ki i l = ,計(jì)算 move 表的時(shí)間復(fù)雜度為 O (1ki i l = ,因此,算法 1的時(shí)間復(fù)雜度為 O (1k i i l =+1ki i l = 。 綜上所述, 預(yù)處理階段的時(shí)間復(fù)雜度為 O (k +1k i i

19、 l =+1ki i l = 。在匹配階段,算法 2中文本掃描指針 i 是無回溯且進(jìn)行 跳躍式比較的, 最壞情況下的比較次數(shù)不超過 2n 次, 設(shè)每次 比較后指針的平均跳躍距離為 len , 則匹配過程的時(shí)間復(fù)雜度 為 O (n /len ,最好情況下 len 可以達(dá)到 minlen+1,因此,匹配 階段最好時(shí)間復(fù)雜度可達(dá)到 O (n /(minlen+1,最壞情況下為 O (n 。 SMA 算法必須檢查文本中每個字符,而且文本掃描指 針不能跳躍,其匹配階段時(shí)間復(fù)雜度為 O (nh /27。4 實(shí)驗(yàn)結(jié)果及分析為測試本文算法的性能,并與 SMA 算法做比較,實(shí)驗(yàn) 中待匹配文本為從互聯(lián)網(wǎng)上下載的

20、17 Mb英語新聞,模式串集合由英文新聞常用人名、地址名以及一些計(jì)算機(jī)常用術(shù)語組成。實(shí)驗(yàn)在 Pentium4 2.4 GHz、 1 GB內(nèi)存、 Windows XP下進(jìn)行,測試在不同模式集和模式長度下算法的性能。實(shí)驗(yàn) 結(jié)果如表 2、表 3所示。從表 2可看出,本文算法與 SMA 算 法預(yù)處理的時(shí)間都隨著模式串?dāng)?shù)目的增加而增加,本文算法 預(yù)處理時(shí)間略多。由表 3可看出,本文算法的匹配時(shí)間明顯低于 SMA 算 法,因?yàn)楸疚乃惴ㄔ谄ヅ鋾r(shí)采用了加速處理,當(dāng)文本中模式 串出現(xiàn)的頻率較小時(shí),模式比較之前跳過的字符較多,最大 可以達(dá)到 minlen+1。特別是在最小模式串較長、模式串?dāng)?shù)目 較多時(shí),本文算法的

21、優(yōu)勢更加突出。表 2 預(yù)處理時(shí)間比較 ms模式數(shù)目SMA本文算法100 0 0 200 16 31 400 110 125 600 312 344表 3 不同 minlen 下匹配時(shí)間比較 msminlen =3 minlen=6 minlen =9 模式數(shù)目SMA本文算法SMA本文算法SMA本文算法100 531 422 578 281 766 329 200 750 516 813 312 1 078765 400 984 625 1 047 391 1 109813 6001 1887501 1724071 2488655 結(jié)束語模式串匹配是計(jì)算機(jī)研究領(lǐng)域的一個熱點(diǎn)問題。本文結(jié) 合 QS 算法思想,提出一種基于有序二叉樹的快速多模式字 符串匹配算法,利用已匹配信息,盡可能多地跳過待查文本 串字符,因此,在模式串較長和模式串?dāng)?shù)目較多時(shí),本文算 法相比其他算法具有更好的性能。參考文獻(xiàn)1 Knuth D E, Morris J H, Pratt V R. Fast Pattern Matching inStringsJ. SIAM Journal on Computing, 1977, 6(2: 323-350