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

1、 42基于有序二叉樹的快速多模式字符串匹配算法周 燕 1,侯整風(fēng) 1,何 玲 2(1. 合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院,合肥 230009; 2. 深圳金山信息安全技術(shù)有限公司,深圳 518057摘 要:將有序二叉樹和 QS 算法相結(jié)合,提出一種快速多模式字符串匹配算法,實(shí)現(xiàn)在多模式匹配過(guò)程中不匹配字符的連續(xù)跳躍。為提 高匹配速度,利用已匹配的字符串信息進(jìn)行跳躍式的比較,避免文本掃描指針的回溯。實(shí)驗(yàn)結(jié)果表明,與 SMA 算法相比,該算法在預(yù)處 理階段構(gòu)造速度和匹配速度更快,在模式串較長(zhǎng)的情況下,性能更優(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ù)庫(kù)· 文章編號(hào):1000 3428(201017 0042 03文獻(xiàn)標(biāo)識(shí)碼:A中圖分類號(hào):TP3931 概述模式匹配是指在文本序列 Text=t0t1t2 tn-1中檢索子串 Pattern=p0p1p2 pm-1的問(wèn)題。 模式匹配廣泛應(yīng) 用于入侵檢測(cè)系統(tǒng)、內(nèi)容過(guò)濾防火墻、計(jì)算機(jī)病毒特征碼匹 配以及 DNA 序列匹配等領(lǐng)域,研

6、究高效的模式匹配算法具 有非常重要的理論和現(xiàn)實(shí)意義。模式匹配可分為單模式匹配 和多模式匹配。單模式匹配算法一次只能對(duì)模式串進(jìn)行一個(gè) 模 式 匹 配 , 主 要 有 KMP(Knuth-Morris-Patt算 法 1、 BM (Boyer-Moore算法 2、 QS(Quick Search算法 3等。多模式匹 配算法一次可對(duì)模式串同時(shí)進(jìn)行多個(gè)模式匹配,包括 AC (Aho-Corasick算法 4、 WM(Wu-Manber算法 5、 AC-BM 算 法 6等。 AC 算法是一種基于自動(dòng)機(jī)的算法, 首先根據(jù)模式集 構(gòu)建一棵搜索樹,然后對(duì)待搜索文本從左至右進(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í)搜索匹配,能對(duì)目 標(biāo)串進(jìn)行跳躍式搜索。文獻(xiàn) 7提出的 SMA 算法采用有序二 叉樹結(jié)構(gòu)來(lái)組織有限狀態(tài)自動(dòng)機(jī),解決了 AC 算法中有限狀 態(tài)自動(dòng)機(jī)構(gòu)造速度慢、占用內(nèi)存大的問(wèn)題,但是該算法在查 找過(guò)程中必須檢查每一個(gè)字符,降低了算法的查找效率。本 文在 SMA 算法的基礎(chǔ)上,吸收 QS 算法的

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

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

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

11、根節(jié)點(diǎn)為 root 的有序二叉樹輸出 保存失配后文本指針的跳躍和新?tīng)顟B(tài)的 move 表 (1minlen最短模式的長(zhǎng)度。(2對(duì)每個(gè) c , lastc初始化為 0。 (3建立隊(duì)列 queue ,并置空。(4對(duì)每個(gè)滿足 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ì)算每個(gè)狀態(tài)的 failstate 和每個(gè)字符的 lastc:1s 隊(duì)列 queue 的隊(duì)頭元素出隊(duì)。2 對(duì)每

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

15、免了文本掃描指針 的回溯,減少了比較的次數(shù)。失配后,有序二叉樹至少要向 前移動(dòng)一個(gè)位置,若要匹配成功,前方的字符必須在成功匹 配的模式中出現(xiàn),因此,以最短模式為標(biāo)準(zhǔn)向右看文本的一 個(gè)字符,并計(jì)算該字符在所有模式中最后出現(xiàn)的位置,然后 把整個(gè)有序二叉樹移動(dòng)若干位,使該字符與其在模式中最后 出現(xiàn)的位置對(duì)齊,從而跳過(guò)一些不必要的比較。算法 2 模式匹配算法輸入 文本串 T1:n,根為 root 的有序二叉樹, move 表 輸出 匹配成功的模式串在文本中出現(xiàn)的位置(1minlen最短模式的長(zhǎng)度,初始化文本掃描指針 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īng)顟B(tài)為 s movesch.newstate;否則, 文本指針跳躍到新位置 i i+minlen-s所處的層次 +1,新?tīng)顟B(tài) 為 s root 。2.3 示例選取含有 5個(gè)模式串的模式串集合 P=adds, min

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

18、數(shù)為 k , 長(zhǎng)度分別為 l 1, l 2, , l k , 所 有模式串的長(zhǎng)度之和為 1ki i l =,其中,模式串的最短長(zhǎng)度為minlen ;字符集的大小為 ;待搜索文本串的長(zhǎng)度為 n 。算法分析分預(yù)處理和匹配 2個(gè)階段進(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 是無(wú)回溯且進(jìn)行 跳躍式比較的, 最壞情況下的比較次數(shù)不超過(guò) 2n 次, 設(shè)每次 比較后指針的平均跳躍距離為 len , 則匹配過(guò)程的時(shí)間復(fù)雜度 為 O (n /len ,最好情況下 len 可以達(dá)到 minlen+1,因此,匹配 階段最好時(shí)間復(fù)雜度可達(dá)到 O (n /(minlen+1,最壞情況下為 O (n 。 SMA 算法必須檢查文本中每個(gè)字符,而且文本掃描指 針不能跳躍,其匹配階段時(shí)間復(fù)雜度為 O (nh /27。4 實(shí)驗(yàn)結(jié)果及分析為測(cè)試本文算法的性能,并與 SMA 算法做比較,實(shí)驗(yàn) 中待匹配文本為從互聯(lián)網(wǎng)上下載的

20、17 Mb英語(yǔ)新聞,模式串集合由英文新聞常用人名、地址名以及一些計(jì)算機(jī)常用術(shù)語(yǔ)組成。實(shí)驗(yàn)在 Pentium4 2.4 GHz、 1 GB內(nèi)存、 Windows XP下進(jìn)行,測(cè)試在不同模式集和模式長(zhǎng)度下算法的性能。實(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í),模式比較之前跳過(guò)的字符較多,最大 可以達(dá)到 minlen+1。特別是在最小模式串較長(zhǎng)、模式串?dāng)?shù)目 較多時(shí),本文算法的

21、優(yōu)勢(shì)更加突出。表 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é)束語(yǔ)模式串匹配是計(jì)算機(jī)研究領(lǐng)域的一個(gè)熱點(diǎn)問(wèn)題。本文結(jié) 合 QS 算法思想,提出一種基于有序二叉樹的快速多模式字 符串匹配算法,利用已匹配信息,盡可能多地跳過(guò)待查文本 串字符,因此,在模式串較長(zhǎng)和模式串?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