對(duì)Horspool算法的改進(jìn)

曹海鋒 張維琪

摘 ?要：文章分析BM及其改進(jìn)的Horspool和Sunday算法，在此基礎(chǔ)上提出了Horspool的改進(jìn)算法。該算法利用當(dāng)前窗口的下一個(gè)字符信息以及當(dāng)前窗口最后一個(gè)字符和文本字符不匹配這個(gè)事實(shí)，增大右移量，減少了匹配次數(shù)。實(shí)驗(yàn)結(jié)果表明，該算法比原有算法具有更高的效率。

關(guān)鍵詞：串匹配;BM算法;Horspool算法;改進(jìn)的Horspool算法

中圖分類(lèi)號(hào)：TP301 ? ? 文獻(xiàn)標(biāo)識(shí)碼：A ? ? ?文章編號(hào)：1006-8937（2015）05-0046-03

目前，計(jì)算機(jī)通信網(wǎng)絡(luò)在社會(huì)生活各方面的作用日益增大。社會(huì)對(duì)計(jì)算機(jī)網(wǎng)絡(luò)的依賴(lài)也日益增強(qiáng)。隨著網(wǎng)絡(luò)技術(shù)在各行業(yè)中的廣泛應(yīng)用以及Internet的飛速發(fā)展，日益嚴(yán)重的網(wǎng)絡(luò)安全問(wèn)題已經(jīng)引起了人們的高度重視。黑客、網(wǎng)絡(luò)間諜、網(wǎng)絡(luò)病毒等嚴(yán)重威脅著計(jì)算機(jī)網(wǎng)絡(luò)的安全。為了抵御網(wǎng)絡(luò)攻擊，人們采用網(wǎng)絡(luò)安全技術(shù)來(lái)保護(hù)其內(nèi)部網(wǎng)絡(luò)的數(shù)據(jù)資料，其中應(yīng)用最廣泛的是入侵檢測(cè)系統(tǒng)（Intrusion Detection Systems：IDS）。

作為網(wǎng)絡(luò)內(nèi)容安全檢查的重要技術(shù)，字符串匹配算法被廣泛的應(yīng)用在入侵檢測(cè)、入侵保護(hù)、網(wǎng)絡(luò)防病毒和網(wǎng)絡(luò)內(nèi)容監(jiān)控等網(wǎng)絡(luò)安全系統(tǒng)中。字符串匹配是網(wǎng)絡(luò)安全系統(tǒng)中對(duì)計(jì)算資源要求最高的部分，據(jù)統(tǒng)計(jì)，在常用的入侵檢測(cè)系統(tǒng)（IDS）SNORT中，70%的執(zhí)行時(shí)間和80%程序的指令都用在特征串的匹配上：大約有30%的網(wǎng)絡(luò)問(wèn)題是由于安全系統(tǒng)中數(shù)據(jù)包過(guò)濾效率低下造成的。隨著網(wǎng)絡(luò)帶寬的不斷增加，入侵檢測(cè)規(guī)則的持續(xù)增長(zhǎng)，包過(guò)濾的效率已無(wú)法滿(mǎn)足網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)男枨螅Ｊ狡ヅ湔诔蔀榫W(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)的性能瓶頸。因此提高串匹配效率對(duì)提高IDS的過(guò)濾能力至關(guān)重要。

1 ?現(xiàn)有串匹配算法的分析

串匹配就是在已知文本集合T中找出一個(gè)或者多個(gè)模式串P的所有出現(xiàn)。目前針對(duì)精確模式匹配算法已有40多年的研究，產(chǎn)生出了上百種模式匹配算法，其中最基本也最經(jīng)典的是KMP算法和BM算法，這兩種算法奠定了以后許多算法的基礎(chǔ)，通常情況下BM算法的搜索速度是KMP算法的3-5倍。隨后產(chǎn)生出對(duì)BM算法改進(jìn)的Horspool算法和Sunday算法，這兩種算法在大多數(shù)情況下都比BM算法具有更好的性能。

1.1 ?BM算法

Boyer和Moore兩人在KMP算法的基礎(chǔ)上，設(shè)計(jì)出的一種快速單模式匹配算法BM（Boyer-Moore）算法。BM算法進(jìn)行模式匹配時(shí)，模式P沿著文本T從左到右移動(dòng)，字符比較卻從右至左進(jìn)行，在每次比較失敗后通過(guò)兩種方式來(lái)決定下一次匹配動(dòng)作匹配窗口的開(kāi)始位置：好后綴轉(zhuǎn)移機(jī)制和不良字符轉(zhuǎn)移機(jī)制。

BM算法在當(dāng)前窗口從右向左匹配過(guò)程中，設(shè)已讀入字符串U，且已經(jīng)匹配，即U是模式的后綴，也是文本在搜索窗口的后綴，此時(shí)再讀入一個(gè)字符n后發(fā)生失配，此時(shí)用下面兩種機(jī)制中滑動(dòng)距離最遠(yuǎn)者來(lái)決定搜索窗口的右移距離。

1.1.1 ?好后綴轉(zhuǎn)移機(jī)制

好后綴轉(zhuǎn)移表的計(jì)算公式如下：

gs_shift[j]=

若已經(jīng)匹配的后綴U在模式P中出現(xiàn)不止一次，則將搜索窗口向右滑動(dòng)使將模式串U在其左邊的第二次出現(xiàn)位置與文本串的U對(duì)齊，繼續(xù)進(jìn)行匹配。如圖1所示。

若U在模式串中沒(méi)有出現(xiàn)，但U的某個(gè)后綴恰好是模式P的前綴，設(shè)v為滿(mǎn)足此條件的最長(zhǎng)后綴，則滑動(dòng)搜索窗口時(shí)文本串中U的最長(zhǎng)后綴v與模式串的前綴對(duì)齊，繼續(xù)進(jìn)行匹配，如圖2所示。

1.1.2 ?壞字符轉(zhuǎn)移機(jī)制

壞字符轉(zhuǎn)移表的計(jì)算公式如下：

bc_skip[x]=

如果從右向左匹配過(guò)程中，匹配到模式串的字符n時(shí)發(fā)現(xiàn)不匹配，假設(shè)字符n對(duì)應(yīng)的文本中的字符是m，若m在P中出現(xiàn)，則將模式串向右移動(dòng)使之與文本串中的m對(duì)齊，繼續(xù)進(jìn)行匹配，如圖3所示。

如果m在P中未出現(xiàn)，則直接將模式串滑動(dòng)到文本串中字符m的后面，繼續(xù)進(jìn)行匹配，如圖4所示。

該算法由于存在比較壞字符和好后綴的環(huán)節(jié)，而在大多數(shù)情況下好后綴出現(xiàn)的情況很小，故影響了匹配效率。

1.2 ?Horspool算法

Horspool算法是對(duì)BM算法的一個(gè)簡(jiǎn)化，該算法在移動(dòng)模式時(shí)僅使用壞字符啟發(fā)規(guī)則。計(jì)算指針移動(dòng)距離時(shí)首先判斷窗口的最右字符與對(duì)應(yīng)文本字符是否相等，將最右的字符t[i+m-1]與P[0…m-2]與最右面的相應(yīng)出現(xiàn)對(duì)齊，如果P[0…m-2]中不存在t[i+m-1]字符，則滑動(dòng)整個(gè)窗口。

和BM算法相比，Horspool只使用了一個(gè)數(shù)組，簡(jiǎn)化了初始化的過(guò)程，省去了比較壞字符和好后綴的步驟，在一般情況下比BM算法具有更好的性能。但由于該算法只是利用窗口的最后一個(gè)字符進(jìn)行壞字符跳躍，故跳躍距離最大只能是窗口的長(zhǎng)度m。

1.3 ?Sunday算法

Sunday算法也叫Quick Search算法，是BM算法的一個(gè)簡(jiǎn)化，同樣只使用壞字符策略。在搜索階段模式和文本字符的比較可以以任意的順序進(jìn)行，當(dāng)發(fā)現(xiàn)不匹配時(shí)，通過(guò)緊跟在當(dāng)前窗口之后的第一個(gè)字符t[s+m]來(lái)計(jì)算移動(dòng)距離。雖然該算法具有最壞的平方級(jí)的時(shí)間復(fù)雜度，但在實(shí)際應(yīng)用中對(duì)于短的模式串和大字母表的情況下非?？?。

目前，針對(duì)上面三種經(jīng)典的算法已有很多改進(jìn)的算法，以適應(yīng)不同的應(yīng)用，如FJS算法、BMG算法EPSM算法等，但由于其實(shí)現(xiàn)都比較復(fù)雜，并不能顯著的提高串匹配的效率。

2 ?改進(jìn)的Horspool算法

通過(guò)對(duì)Horspool的分析與應(yīng)用，受到Sunday算法的啟發(fā)，本文提出了Horspool算法的改進(jìn)思路：對(duì)于每次嘗試，模式與當(dāng)前窗口從右向左進(jìn)行比較，當(dāng)且僅當(dāng)?shù)谝粋€(gè)字符不匹配時(shí)，即

p[m-1]t[s+m-1]，

使用壞字符規(guī)則計(jì)算移動(dòng)增量，此時(shí)壞字符是模式串最后一個(gè)字符對(duì)應(yīng)的文本字符;當(dāng)?shù)谝粋€(gè)字符匹配并且該窗口匹配失敗時(shí)，同樣使用壞字符計(jì)算移動(dòng)增量，改進(jìn)在于此時(shí)的壞字符是模式串最后一個(gè)字符對(duì)應(yīng)的文本字符的下一個(gè)字符。算法的具體描述如下：該算法的預(yù)處理階段主要是初始化位置移動(dòng)表——ihBc1表和ihBc2表。

設(shè)待匹配文本所在字符集的大小為ASIZE，該初始化程序的代碼如下，該代碼給出了ihBc1表的初始化方法，ihBc2表的初始化與其類(lèi)似，差別在于表中的每一項(xiàng)均比ihBc1少1。

void preih1（char *x， int m， int ihBc1[]） {

int i;

for （i = 0; i < ASIZE; ++i）

ihBc1[i] = m + 1;

for （i = 0; i < m; ++i）

ihBc1[x[i]] = m- i;}

全文掃描階段開(kāi)始時(shí)，將文本串T與模式串P左對(duì)齊，從右向左逐個(gè)字符進(jìn)行比較，當(dāng)匹配失敗的字符是窗口最右邊的字符時(shí)，查詢(xún)表ihBc2進(jìn)行跳轉(zhuǎn)，當(dāng)匹配失敗的字符不是窗口最右邊的那個(gè)字符時(shí)，查詢(xún)表ihBc1進(jìn)行跳轉(zhuǎn)。匹配流程如圖5所示。

該改進(jìn)算法的一個(gè)匹配實(shí)例見(jiàn)表1。

3 ?實(shí)驗(yàn)結(jié)果及分析

Horspool算法與改進(jìn)后的Horspool算法的程序結(jié)構(gòu)基本相同，時(shí)間復(fù)雜度和空間復(fù)雜度也基本一樣，但由于其考慮的Horspool算法在失配時(shí)的位置，因此在實(shí)際中具有更高的效率。為了測(cè)試算法的性能，作者通過(guò)程序生成了128 M隨機(jī)文本，并且將1 000個(gè)不同長(zhǎng)度的模式分別播撒在該文本中，對(duì)BM、Horspool、Sunday、改進(jìn)的Horspool算法進(jìn)行測(cè)試，測(cè)試結(jié)果見(jiàn)表2。在windows環(huán)境下，可以通過(guò)QueryPerformanceCounter函數(shù)獲得高精度的性能計(jì)數(shù)器，QueryPerformanceCounter可以獲得CPU內(nèi)部的計(jì)數(shù)器的值，這個(gè)計(jì)數(shù)器的值的精度非常高，能夠達(dá)到一秒鐘增加幾百萬(wàn)的計(jì)數(shù)。

從表2中以看出，在隨機(jī)純英文文本上改進(jìn)的Horspool算法的匹配時(shí)間平均比未改進(jìn)的Horspool算法減少了15%，在匹配時(shí)間上較原來(lái)的Horspool算法有了明顯提高。

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

改進(jìn)的Horspool算法結(jié)合了Horspool算法與Sunday算法的優(yōu)點(diǎn)，在匹配過(guò)程中，充分利用當(dāng)前窗口的最后一個(gè)字符與文本不匹配和在匹配失敗時(shí)窗口至少要移動(dòng)一個(gè)字符這兩條信息，使得該算法在實(shí)際應(yīng)用中具有很好的性能。實(shí)驗(yàn)結(jié)果表明，Horspool算法顯著提高了字符串匹配的效率，縮短了匹配時(shí)間，具有廣闊的應(yīng)用前景。

參考文獻(xiàn)：

[1] Knuth D E，Morris J H，Pratt V R.Fast pattern matching in strings[J]. SIAM journal on computing，1977，（2）.

[2] Boyer R S，Moore J S.A fast string searching algorithm[J].Communica-

tions of the ACM，1977，（10）.

[3] Horspool R N.Practical fast searching in strings[J].Software：Practice and Experience，1980，（6）.

[4] Sunday D M.A very fast substring search algorithm[J].Communications of the ACM，1990，（8）.

[5] Franek F，Jennings C G，Smyth W F.A simple fast hybrid pattern-

matching algoritm[J].Journal of Discrete Algorithms，2007，（5）.

[6] 張娜，侯整風(fēng).一種快速的BM模式匹配改進(jìn)算法[J].合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2006，（7）.

[7] Faro S and Kulekci M O.Fast Packed String Matching for Short Patterns.Meeting on Algorithm Engineering and Experiments[J]，ALE-

NEX，2013，（2013）.