周志平，莊金蓮，陳佳麗

（龍巖學(xué)院數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，福建龍巖364000）

QS快速單模式匹配的兩種改進(jìn)算法

周志平，莊金蓮，陳佳麗

（龍巖學(xué)院數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，福建龍巖364000）

模式匹配算法已廣泛應(yīng)用于各個領(lǐng)域，針對如何減少匹配次數(shù)，提高算法效率，提出兩種改進(jìn)的QS快速匹配算法。第一種算法通過檢測匹配窗口的末字符是否出現(xiàn)于模式串中，并依據(jù)情況滑動模式串。第二種算法通過構(gòu)造BM及QS算法兩個壞字符滑動表，經(jīng)查表比較后確定每一次的滑動距離，使得模式串的滑動距離達(dá)到最大，從而大大減少了嘗試的次數(shù)。實(shí)驗結(jié)果表明，UCD與MSD算法的嘗試匹配次數(shù)明顯優(yōu)于QS及其他算法，具有更高的效率。

QS算法；模式匹配；串搜索；字符串匹配

模式匹配算法廣泛應(yīng)用于入侵檢測、病毒檢測和生物序列檢測等領(lǐng)域。在入侵檢測中[1-2]，需要快速模式匹配算法對各種入侵事件進(jìn)行匹配和檢測。隨著網(wǎng)絡(luò)傳輸速度的不斷提高，計算機(jī)需要處理的數(shù)據(jù)量也越來越大，如果模式匹配算法來不及處理這些大量的數(shù)據(jù)包，必然會造成漏報。因此，模式匹配算法的性能成為制約入侵檢測系統(tǒng)效率的瓶頸。模式匹配問題可以描述為大小為C的字符集合Σ，在長度為n的文本串（T=T0T1T2…Tn-1）中查找長度為m的模式串（P=P0P1P2…Pm-1）出現(xiàn)的位置。在匹配過程中，T與P中正在比較的子串稱為匹配窗口，一次比較稱為一次嘗試。模式匹配算法優(yōu)化的目的是使嘗試的次數(shù)最少而滑動距離最大。在實(shí)際應(yīng)用中，常用的單模式匹配算法有BM[3]，QS[4]，BMH[5]等。QS算法以其簡單快速且易于實(shí)現(xiàn)的特點(diǎn)被廣泛應(yīng)用。本文提出失配字符檢測算法和最大滑動距離算法，具有比QS算法更大的移動距離以及更快的查找速度。

1 相關(guān)算法

1.1 QS算法

在QS算法中，只建立一個壞字符滑動表qsBc[][6]。在匹配的過程中，滑動的距離與失配字符的位置無關(guān)。若發(fā)生失配，則使用T[j+m]字符查找qsBc[T[j+m]]，以確定滑動的距離，其中j為文本串中當(dāng)前匹配窗口指針。由于模式串P中出現(xiàn)的字符的數(shù)量通常要小于字符集合Σ的大小，當(dāng)字符不出現(xiàn)在模式串P中時，QS算法的最大的滑動距離可達(dá)到m+1，從而有效提高了算法的匹配效率。然而，當(dāng)T[j+m]與P[m-1]匹配，且字符T[j+m-1]不出現(xiàn)在模式串時，滑動距離僅為1，導(dǎo)致嘗試匹配次數(shù)大大增加，算法效率大打折扣。

1.2 基于QS的改進(jìn)算法

文獻(xiàn)[7]中提出了一種基于QS的改進(jìn)算法（improved quick search，IQS）。根據(jù)各字符在文章中出現(xiàn)概率的統(tǒng)計結(jié)果，生成數(shù)組pro[]，之后將模式串進(jìn)行預(yù)處理，記錄特征字符chk及其出現(xiàn)的位置pos。匹配過程對文本串T中第i位的字符text[i]與模式串P中的pos位進(jìn)行比較，并將模式串的尾字符text[i+p_len-pos-1]與主串進(jìn)行比較，其中i為文本串中當(dāng)前的匹配窗口指針。若兩者均匹配成功，則進(jìn)行精確匹配；否則，判斷文本串中的第i＋p_len-pos個字符是否出現(xiàn)在模式串中：若沒有出現(xiàn)，移動p_len+1；否則，移動p_len-pat[text[i+p_len-pos]]+1。循環(huán)執(zhí)行，直到整個主串匹配完成。

該算法增加了一個按字符概率排序的字符串，在一定程度上減小了字符匹配的概率，由于查找滑動距離表與QS算法相同，僅用i＋p_len-pos移動模式串，無法克服QS算法存在的問題，在實(shí)際文本匹配過程中，效果不是很理想。

2 改進(jìn)算法

2.1 UCD算法描述

針對QS算法存在的問題，本文提出一種失配字符檢測算法（un-occurrence character detect，UCD）。該算法采用一個與QS算法相同的壞字符滑動表qsBc[]，檢測匹配窗口中字符T[j+m-1]的滑動距離，查找qsBc[T[j+m-1]]，若滑動距離為m+1，則表示字符T[j+m-1]不出現(xiàn)于模式串P中。查找qsBc[T[j+m]]，若滑動距離為m+1，則模式串滑動距離為m+1，否則模式串滑動距離為m。其中qsBc[]表的構(gòu)造方法如下：

假設(shè)模式串P=“ababc”，長度m=5；文本串T=“ababdababc”，長度n=10。表1所示為UCD算法建立的滑動表，圖1所示為匹配過程。將兩字符串左對齊，查找滑動距離表，qsBc[d]=6，說明字符d不在模式串中。qsBc[a]=3，則移動5位。

2.2 MSD算法描述

針對QS算法存在的問題，提出另一種最大滑動距離算法（maximum shifting distance，MSD），該算法采用兩個壞字符滑動表qsBc[]和bmBc[]，兩張表分別針對字符T[j+m]與T[j+m-1]建立的滑動距離表，通過查找qsBc[T[j+m]]與bmBc[T[j+m-1]]，取較其較大值來滑動模式串，可使模式串的滑動距離達(dá)到最大值。其中qsBc[]表的構(gòu)造與QS算法相同，bmBc[]表的構(gòu)造與BM算法所提出的壞字符表相同，具體構(gòu)造方法如下：

表1 UCD算法滑動距離表

圖1 UCD算法匹配過程

假設(shè)模式串P=“ababc”，長度m=5；文本串T=“ababdababc”，長度n=10。表2所示為MSD算法建立的滑動表，圖2所示為匹配過程。

表2 MSD算法滑動距離表

圖2 MSD算法匹配過程

將兩字符串左對齊，查找滑動距離表，qsBc[a]=3，bmBc[d]=5，取其較大值，則移動5位。

2.3 算法分析

設(shè)字符集合Σ，大小為c。文本串T長度為n。模式串P長度為m，所含字符集合為Π，大小為k，其中Π為Σ的子集。qsBc[]、bmBc[]分別為QS、BM算法的滑動距離表。

在模式串匹配過程中，QS、BMH和MSD算法嘗試匹配次數(shù)表示為：

其中shift表示模式串的滑動距離，各算法的滑動距離計算如下：

（1）QS算法平均滑動距離：

（2）BMH算法平均滑動距離：

由（1）可得tMSD≤tQS≤tBM，并且當(dāng)k□c效果好。

UCD算法使用了一張壞字符滑動表，MSD算法使用了兩張壞字符滑動表，空間復(fù)雜度都為O(c)。預(yù)處理的時間復(fù)雜度為O(m+c)。若文本串所出現(xiàn)的字符不出現(xiàn)在匹配串中，則模式串可滑動m+1。在極端的情況下，每一次嘗試匹配后的滑動距離都是m+1，因此在最好的情況下時間復(fù)雜度是O(n/m+1)。由于文本串中的每一個字符的匹配次數(shù)不超過m次，那么文本串中的所有字符的匹配次數(shù)不超過m·(n-m+1)次。在極端的情況下，每一次嘗試匹配后的滑動距離都是1，因此時間復(fù)雜度是O(m·(n-m+1))。

綜上所述，UCD算法及MSD算法復(fù)雜度與QS算法相同,并且優(yōu)于BMH算法。

3 實(shí)驗結(jié)果

在實(shí)驗中，測試環(huán)境為Intel Core 2 Duo CPU 2.10GHz、2G內(nèi)存、Windows 7；編譯環(huán)境為Microsoft Visual Studio2005。對QS，BM，BMH，IQS，UCD與MSD算法進(jìn)行比較，文本串來自于Reuters[8]中的feldmancia-worldfactbook-data.txt，刪除換行及空格符后文件大小為256 kB。嘗試次數(shù)比較結(jié)果如表3所示。

由表3可看出，當(dāng)模式串較短時，QS算法、IQS、UCD及MSD相比BM及BMH算法大大降低了嘗試次數(shù)。隨著模式串的增長，UCD與MSD算法較其他算法提升效果越明顯。由于MSD算法采用兩張滑動距離表并取最大值，算法嘗試的次數(shù)最少。4種算法的嘗試次數(shù)比較如圖3所示。

表3 6種算法嘗試次數(shù)的比較

圖3 算法嘗試次數(shù)比較

4 結(jié)束語

為了提高字符串模式匹配速度，本文提出了針對QS算法改進(jìn)的兩種思路，兩種算法各有優(yōu)缺點(diǎn)：失配字符檢測算法UCD只需要通過檢測匹配窗口的末字符是否出現(xiàn)來滑動模式串，就能有效地避免失配字符對算法效率的影響，是最直接避免QS存在問題的方法，該算法簡單快捷且開銷??；最大滑動距離的QS快速匹配算法MSD，它結(jié)合了BM和QS算法的思想，通過查找兩張表使滑動的距離達(dá)到最大，該算法滑動快并且簡單高效，但需要更大的存儲空間。實(shí)驗結(jié)果表明，改進(jìn)的算法與其他算法進(jìn)行比較，嘗試次數(shù)少，具有較高的效率。且當(dāng)模式串較長且字符較少時，效果更好。

[1]CHEN T，F(xiàn)U Z，HE L，et al.Recent developments in Nnetwork intrusion detection[J].IEEE Network,2009：4-5.

[2]張曉惠.基于數(shù)據(jù)融合的入侵檢測研究[J].三明學(xué)院學(xué)報,2012,29(4)：56-60.

[3]BOYER R S，MOORE J S.A fast string searching algorithm[J].Communications of ACM,1977,20(10)：762-772.

[4]SUNDAY D M.A very fast substring search algorithm[J].Communication of the ACM,1990,33(1)：132-142.

[5]HORSPOOL N R.Practical fast searching in strings[J].Software Practice and Experience,1980,10(6)：501-506.

[6]CHARRAS C，LECROQ T T.Handbook of exact string matching algorithm[M].London：London King’s College London Publications,2004.

[7]萬曉榆，楊波，樊自甫.改進(jìn)的Sunday模式匹配算法[J].計算機(jī)工程,2009,35(7)：125-129.

[8]DAVID D.Lewis,Reuters-21578 test collection[EB/OL].http：//www.daviddlewis.com/resources/testcollections/ reuters21578/，2004.

Two Improved Fast Single Pattern Matching Algorithms of QS

ZHOU Zhi-ping,ZHUANG Jin-lian,CHEN Jia-li
(School of Mathematics and Computer Science，Longyan University，Longyan 364000,China)

Pattern matching algorithms has been widely used in various fields.Aiming at how to reduce the number of attempts as well as improve the efficiency of the algorithm,two pattern matching algorithms are presented to improve the algorithm of quick search.The first algorithm matches the text window by checking whether the last character occurs in the pattern string,and then shiftsthe pattern stringdependingon the situation.The second algorithm constructs two bad character shift tables ofBMand QSalgorithms',then look up these two tablesto determine the shift distance each time,making the pattern string reach the maximum shift distance.This greatly reduces the number of attempts and increases the shift distance.The experimental resultsshow thatUCD and MSD algorithms'matchingspeed issignificantlyfasterthan QSand otheralgorithms'.

QS algorithm;pattern matching;string searching;string matching

TP301.6

A

1673-4343（2013）04-0030-04

2013-04-10

周志平，男，福建順昌人，助教。研究方向:計算機(jī)網(wǎng)絡(luò)，網(wǎng)絡(luò)安全。