對Horspool算法的改進

曹海鋒 張維琪

摘 ?要：文章分析BM及其改進的Horspool和Sunday算法，在此基礎上提出了Horspool的改進算法。該算法利用當前窗口的下一個字符信息以及當前窗口最后一個字符和文本字符不匹配這個事實，增大右移量，減少了匹配次數。實驗結果表明，該算法比原有算法具有更高的效率。

關鍵詞：串匹配;BM算法;Horspool算法;改進的Horspool算法

中圖分類號：TP301 ? ? 文獻標識碼：A ? ? ?文章編號：1006-8937（2015）05-0046-03

目前，計算機通信網絡在社會生活各方面的作用日益增大。社會對計算機網絡的依賴也日益增強。隨著網絡技術在各行業中的廣泛應用以及Internet的飛速發展，日益嚴重的網絡安全問題已經引起了人們的高度重視。黑客、網絡間諜、網絡病毒等嚴重威脅著計算機網絡的安全。為了抵御網絡攻擊，人們采用網絡安全技術來保護其內部網絡的數據資料，其中應用最廣泛的是入侵檢測系統（Intrusion Detection Systems：IDS）。

作為網絡內容安全檢查的重要技術，字符串匹配算法被廣泛的應用在入侵檢測、入侵保護、網絡防病毒和網絡內容監控等網絡安全系統中。字符串匹配是網絡安全系統中對計算資源要求最高的部分，據統計，在常用的入侵檢測系統（IDS）SNORT中，70%的執行時間和80%程序的指令都用在特征串的匹配上：大約有30%的網絡問題是由于安全系統中數據包過濾效率低下造成的。隨著網絡帶寬的不斷增加，入侵檢測規則的持續增長，包過濾的效率已無法滿足網絡數據傳輸的需求，模式匹配正在成為網絡入侵檢測系統的性能瓶頸。因此提高串匹配效率對提高IDS的過濾能力至關重要。

1 ?現有串匹配算法的分析

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

1.1 ?BM算法

Boyer和Moore兩人在KMP算法的基礎上，設計出的一種快速單模式匹配算法BM（Boyer-Moore）算法。BM算法進行模式匹配時，模式P沿著文本T從左到右移動，字符比較卻從右至左進行，在每次比較失敗后通過兩種方式來決定下一次匹配動作匹配窗口的開始位置：好后綴轉移機制和不良字符轉移機制。

BM算法在當前窗口從右向左匹配過程中，設已讀入字符串U，且已經匹配，即U是模式的后綴，也是文本在搜索窗口的后綴，此時再讀入一個字符n后發生失配，此時用下面兩種機制中滑動距離最遠者來決定搜索窗口的右移距離。

1.1.1 ?好后綴轉移機制

好后綴轉移表的計算公式如下：

gs_shift[j]=

若已經匹配的后綴U在模式P中出現不止一次，則將搜索窗口向右滑動使將模式串U在其左邊的第二次出現位置與文本串的U對齊，繼續進行匹配。如圖1所示。

若U在模式串中沒有出現，但U的某個后綴恰好是模式P的前綴，設v為滿足此條件的最長后綴，則滑動搜索窗口時文本串中U的最長后綴v與模式串的前綴對齊，繼續進行匹配，如圖2所示。

1.1.2 ?壞字符轉移機制

壞字符轉移表的計算公式如下：

bc_skip[x]=

如果從右向左匹配過程中，匹配到模式串的字符n時發現不匹配，假設字符n對應的文本中的字符是m，若m在P中出現，則將模式串向右移動使之與文本串中的m對齊，繼續進行匹配，如圖3所示。

如果m在P中未出現，則直接將模式串滑動到文本串中字符m的后面，繼續進行匹配，如圖4所示。

該算法由于存在比較壞字符和好后綴的環節，而在大多數情況下好后綴出現的情況很小，故影響了匹配效率。

1.2 ?Horspool算法

Horspool算法是對BM算法的一個簡化，該算法在移動模式時僅使用壞字符啟發規則。計算指針移動距離時首先判斷窗口的最右字符與對應文本字符是否相等，將最右的字符t[i+m-1]與P[0…m-2]與最右面的相應出現對齊，如果P[0…m-2]中不存在t[i+m-1]字符，則滑動整個窗口。

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

1.3 ?Sunday算法

Sunday算法也叫Quick Search算法，是BM算法的一個簡化，同樣只使用壞字符策略。在搜索階段模式和文本字符的比較可以以任意的順序進行，當發現不匹配時，通過緊跟在當前窗口之后的第一個字符t[s+m]來計算移動距離。雖然該算法具有最壞的平方級的時間復雜度，但在實際應用中對于短的模式串和大字母表的情況下非常快。

目前，針對上面三種經典的算法已有很多改進的算法，以適應不同的應用，如FJS算法、BMG算法EPSM算法等，但由于其實現都比較復雜，并不能顯著的提高串匹配的效率。

2 ?改進的Horspool算法

通過對Horspool的分析與應用，受到Sunday算法的啟發，本文提出了Horspool算法的改進思路：對于每次嘗試，模式與當前窗口從右向左進行比較，當且僅當第一個字符不匹配時，即

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

使用壞字符規則計算移動增量，此時壞字符是模式串最后一個字符對應的文本字符;當第一個字符匹配并且該窗口匹配失敗時，同樣使用壞字符計算移動增量，改進在于此時的壞字符是模式串最后一個字符對應的文本字符的下一個字符。算法的具體描述如下：該算法的預處理階段主要是初始化位置移動表——ihBc1表和ihBc2表。

設待匹配文本所在字符集的大小為ASIZE，該初始化程序的代碼如下，該代碼給出了ihBc1表的初始化方法，ihBc2表的初始化與其類似，差別在于表中的每一項均比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;}

全文掃描階段開始時，將文本串T與模式串P左對齊，從右向左逐個字符進行比較，當匹配失敗的字符是窗口最右邊的字符時，查詢表ihBc2進行跳轉，當匹配失敗的字符不是窗口最右邊的那個字符時，查詢表ihBc1進行跳轉。匹配流程如圖5所示。

該改進算法的一個匹配實例見表1。

3 ?實驗結果及分析

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

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

4 ?結 ?語

改進的Horspool算法結合了Horspool算法與Sunday算法的優點，在匹配過程中，充分利用當前窗口的最后一個字符與文本不匹配和在匹配失敗時窗口至少要移動一個字符這兩條信息，使得該算法在實際應用中具有很好的性能。實驗結果表明，Horspool算法顯著提高了字符串匹配的效率，縮短了匹配時間，具有廣闊的應用前景。

參考文獻：

[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] 張娜，侯整風.一種快速的BM模式匹配改進算法[J].合肥工業大學學報：自然科學版，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）.