一種改進的BMHS模式匹配算法

張歡 胡勇

摘 ?要： 模式匹配在計算機應用中扮演著很重要的角色。通過分析BM，BMH和BMHS算法及相關改進算法，提出BMHS算法的改進算法（DBMHS）。該算法（DBMHS）充分利用模式串兩端字符，通過比較模式串兩端字符的跳轉距離來實現更大距離的跳轉。實驗證明，改進后的算法顯著增加了匹配窗口的跳轉距離，有效地提高了匹配效率。

關鍵詞： 模式匹配; 跳轉距離; BM算法; BMH算法; BMHS算法; DBMHS算法

中圖分類號：TP393 ? ? ? ? ?文獻標志碼：A ? ? 文章編號：1006-8228（2015）01-08-04

An improved pattern matching algorithm of BMHS

Zhang Huan， Hu Yong

（School of Electronic and Information Engineering， Sichuan University， Chengdu， Sichuan 610065， China）

Abstract： Pattern matching plays an important role in computer application. By analyzing BM， BMH， BMHS algorithm and their corresponding improved algorithms， a new improved algorithm（called DBMHS） based on BMHS is proposed. DBMHS takes full advantages of two ends string characters of pattern string， through comparing two ends character jump distance of pattern matching， jump distance is increased. The experiment results show that the improved algorithm significantly increases the jump distance of matching window， effectively improving the matching efficiency.

Key words： pattern matching; jump distance; BM algorithm; BMH algorithms; BMHS algorithm; DBMHS algorithm

0 引言

隨著網絡技術的高速發展，網絡資源呈爆炸式增長。如何在網絡數據中找到需要的信息，已經成為人們研究的熱點問題。模式匹配算法在很多領域得到了較為廣泛的應用，如入侵檢測、計算機病毒特征匹配[1]、搜索引擎、文本挖掘等。目前關于模式匹配的算法有很多，其中最著名的是BM算法[2]。BM算法發展的過程中，1980年Horspol發表了改進與簡化BM算法的論文，即Boyer Moore Horspoo（BMH）算法[3]，隨后Sunday在1990年在BMH算法的基礎上又進行了改進，提出了BMHS算法[4]。本文對現有幾種典型模式算法進行分析，在BMHS算法的基礎上進行改進，并進行試驗和結果分析。

1 典型算法

1.1 BM算法

BM算法是由Boyer和Moore在1977提出的單模式匹配算法。它是目前實際應用中效率較高的單模式匹配算法之一。BM算法采用從右向左比較的方法，同時應用到了兩種啟發式規則，即壞字符規則和好后綴規則，來決定向右跳躍的距離。BM 算法中壞字符跳躍表和好后綴跳躍表的設計對提高BM算法效率有至關重要的作用。設文本T（長度為n），模式串P（長度為m）。

⑴ 壞字符跳躍表：當Pk≠Ti，即不匹配情況發生時，若此時Pk是P的末字符且Ti在模式串P中不出現，則下一次比較可以將匹配窗口直接移動m個位置后繼續匹配;若Ti在模式串P中出現，則找到Ti在模式串P中出現的最右邊的位置j（1≤j≤m-1），匹配窗口移動的距離為m-j（如圖1所示）。

圖1 ?壞字符規則

⑵ 好后綴跳躍表： 當Pk≠Ti（k

圖2 ?好后綴規則

在匹配過程中，模式串P與文本T從右向左開始匹配，一旦發現不匹配，取好字符跳轉和壞字符跳轉之間較大的值作為模式串P的向右跳轉距離。最理想的情況是每次匹配時文本T中第一個匹配的字符不存在于模式串P中，此時BM的算法的時間復雜度為O（n/m）;最壞的情況是文本T中有多個重復的字符，并且模式串P由m-1個相同的字符前加一個不同的字符組成，在這種情況下，BM算法的時間復雜度為O（mn）。

1.2 BMH算法

Horspool提出的BMH算法相對于BM算法更容易實現。BMH算法在預處理階段只使用了壞字符跳躍表，無論文本中哪個字符造成了匹配失敗，都將依據壞字符跳轉表向右移動。BMH算法的基本思想是：①搜索文本時，從頭到尾搜索，匹配時從右向左匹配。首先比較文本指針所指字符和模式串的最后一個字符，如果相等，再比較其余m-1個字符，無論文本中哪個字符造成了匹配失敗，都將由文本中和模式串最后一個位置對應的字符來啟發模式串向右移動，即當匹配開始比較TiTi+1…Ti+m-1和P0P1…Pm-1時，一旦發生不匹配，計算跳轉距離skip（Ti+m-1），跳轉后將模式串和文本對齊后重新匹配。②如果與P完全匹配，返回在T中對應的位置;③如果搜索完T仍然找不到完全匹配的位置，則查找失敗[3]（如圖3所示）。壞字符跳轉計算公式：

圖3 ?BMH算法

如圖3所示，當文本中的與T2（‘d）與模式串P中的P2（‘c）發生不匹配時，計算跳轉距離skip（T4），可以看出P1與T4相等，模式串P向右移動3個字符，即skip（T4）等于3，然后將P1與T4對齊后重新匹配。

BMH算法簡化了初始化過程，匹配過程中的判斷過程也作了簡化，因為BMH算法只采用了BM算法的壞字符移動規則，并且將失配情況與偏移量的計算獨立，不關心文本串中哪個字符造成了失配，只考慮用于模式串最右端對齊的文本字符來決定偏移量。該算法的理論時間復雜度與BM算法一致，但實際使用情況下較BM算法效率高。

1.3 BMHS算法

BMHS算法在BMH算法的基礎上作了進一步改進，該算法的主要思想是：當開始匹配TiTi+1…Ti+m-1和P0P1…Pm-1時，若發生不匹配，考慮下一個字節的情況，即利用下一個字符Ti+m決定右移量。當下一個字符Ti+m不在模式串P中出現時，它的右移量比BMH算法的右移量大，跳過m+1個字符。通常情況下，BMHS算法比BMH算法快，但當Ti+m-1不在模式中出現，而Ti+m出現在模式串中時， BMHS算法[4]的效果就不如BMH算法[3]。匹配過程如圖4。BMHS算法的跳轉距離計算公式為：

圖4 ?BMHS算法

如圖4所示，當Ti+m出現在模式串P中時，如圖4（a），將模式串P中的字符‘e與Ti+m對齊;當Ti+m不存在于模式串P中時，如圖4（b）所示，模式串P向右移動m+1個字符;而圖4（c）中當Ti+m存在于模式串P中，而Ti+m-1不存在于模式串P中時，skip（Ti+m-1）等于5，而skip（Ti+m）等于1，Ti+m-1的跳轉距離大于Ti+m的跳轉距離，若還使用Ti+m為標準，則會降低匹配效率。在BMHS算法中最理想的時間復雜度為O（n/m+1）。

1.4 對各算法的已有改進

在模式匹配中存在兩個基本定理：任何字符串匹配算法的最壞情況下必須檢查至少n-m+1個文本中的字符;任何字符串匹配算法至少檢查n/m個字符[5]。因此，沒有一個算法比BM算法有更好的計算復雜度，但是我們可以通過改進來減少比較次數，提高匹配的平均性能。

基于以上三種模式匹配算法，近些年已經有多種改進算法。例如，利用統計字符在模式串中出現的頻率來實現跳轉[6];利用雙字節計算偏移量[7-9];通過模式串P和文本T之間的關系來實現跳轉[10];利用已匹配成功的字符串來進行跳轉[11]，以及從模式串兩端向中間匹配的方式[12]來改進模式匹配算法等。以上算法雖然減小了匹配次數，但相應增加了匹配的時間。接下來詳細介紹一種通過雙字節來計算偏移量的模式匹配改進算法。

2012年袁靜波提出了一種改進的BMHS模式匹配算法[8]。該算法在BMHS算法的基礎上利用文本T中與模式串P最后一個字符對應的字符Ti+m-1，以及Ti+m和Ti+m+1來實現跳轉，模式串P和文本T從右向左匹配。以下是具體匹配過程。

第一步：當文本T和模式串P發生失配時，首先判斷Ti+m是否在模式串中，若不存在直接跳過m+1的距離，如圖5所示，文本T中的T4（‘d）不在模式串P中，則模式串P向右移動m+1個字符。

圖5 ?Ti+m不在模式串P中

第二步：當Ti+m在模式串中時，判斷子串Ti+m Ti+m+1是否在模式串P中，若不存在，則跳過m+2的距離，如圖6，子串“be”不在模式串P中，則模式串向右跳轉m+2個字符。

圖6 ?Ti+m Ti+m+1不在模式串P中

第三步：若模式串包含Ti+m Ti+m+1，則比較子串Ti+m-1Ti+m是否存在于模式串P中，不存在的話跳轉m+1個字符，如圖7，子串Ti+m Ti+m+1（“be”）存在與模式串P中，而子串Ti+m-1 Ti+m（“gb”）不存在與模式串P中，則模式串P向右跳轉m+1個字符。

圖7 ?Ti+m-1 Ti+m不在模式串P中

第四步：若Ti+m Ti+m+1和Ti+m-1 Ti+m都存在于模式串中，則取兩者之間匹配的最大值進行跳轉，如圖8，可以看出，子串Ti+m Ti+m+1（“ea”）的跳轉距離為2，子串Ti+m-1 Ti+m（“ae”）的跳轉距離為3，取跳轉距離較大的值，則模式串P應向右跳轉3個字符。

圖8 ?比較得到較大值進行跳轉

在該改進算法中，模式串P最大的跳轉距離為m+2，在理想的情況下該算法的時間復雜度為O（n/m+2）。

2 DBMHS算法

2.1 基本思想

通過觀察BM，BMH和BMHS算法的匹配過程可以發現，這些算法在匹配窗口的首字符匹配均失敗時效率最優。本文提出的DBMHS算法通過比較模式串P的第一個字符P0的跳轉距離jump（P1）和在T中與模式串P最后一個字符對應的后一個字符Ti+m的跳轉距離jump（Ti+m）來移動模式串P。跳轉距離公式如下：

jump（P1）={k|Ti+k=P1，1≤k≤m}

jump（Ti+m+1）=m-k+1 k=Max{k|Pk=Ti+m+1，1≤k≤m}

2.2 匹配算法

顯然，提高首字符匹配失敗的概率是提高算法效率的關鍵之一。改進的DBMHS算法結合了BMHS算法特點，首先模式串P與文本T左端對齊，從右向左開始匹配，先檢測T中與模式串最后一個字符相對應的字符Ti+m-1是否在模式串P中，若Ti+m-1不在模式串P中出現，則檢測后一個字節Ti+m是否存在于模式串P中，若Ti+m不在模式串P中出現，則模式串P可以向右移動最大的距離m+1，否則移動距離為m。如圖9、圖10所示。

圖9 ?Ti+m不存在于模式串P中

圖10 ?Ti+m存在于模式串P中

若Ti+m-1與模式串P中對應的字符相匹配，則接著匹配余下的字符，一旦發生不匹配的情況，則檢測Ti+m是否存在于模式串P中，若不存在，則模式串P直接向右移動m+1的距離，若存在則計算Ti+m的跳轉距離，然后計算模式串P中第一個字符P0的跳轉距離，比較這兩個跳轉距離，選擇較大的跳轉距離作為模式串P的實際跳轉距離。從圖11可以看出，若使用Ti+m進行跳轉，則模式串P的跳轉距離為1，若使用模式串P的第一個字符P0進行跳轉，則模式串的跳轉距離為2，通過比較，使用P0的跳轉距離可以使模式串P盡量的向右移動。需要注意的是，若模式串P或文本T中同一個字符出現多次，在計算跳轉距離時，需分情況處理，例如，若匹配Ti+m時，P中出現多個與Ti+m相同的字符，則選擇最右端的字符與Ti+m對齊;若是在匹配P0時出現這種情況，則選擇T中靠左的字符進行對齊。

圖11 ?P1跳轉距離大于Ti+m

若算法在匹配時自右向左均匹配成功，則此時找到一次完全匹配，算法結束。DBMHS匹配算法偽代碼描述如表1。

表1 ?DBMHS匹配算法偽代碼

[輸入：文本串T，模式串P

輸出：文本串T中是否存在子串P＼&While i≤T

Do If Ti+m-1 Pm

If Ti+m-1P

If Ti+mP Then MOVE ← m;

Else MOVE ← m+1;

Else

If Ti+mP Then MOVE ← m+1;

Else MOVE ← max（jump（P0），jump（Ti+m））;

Else If Ti+kPk

If Ti+mP Then MOVE ← m+1;

Else MOVE ← max（jump（P0），jump（Ti+m））;

Else If Ti。。。i+m-1= P0。。。m-1 ?Then Return true;

Return false;＼&]

2.3 算法分析

從BMHS算法的匹配算法可以看出，BMHS算法在比較時利用下一個字符Ti+m決定右移量，當Ti+m不在模式串P中出現時會跳轉最大的距離m+1，但當Ti+m出現在模式串P中時，由于多進行了一次匹配，BMHS匹配算法的效果就不如BMH算法。因此，DBMHS匹配算法通過模式串兩端的字符來充分利用Ti+m。當Ti+m出現在模式串P中時，計算Ti+m的跳轉距離，并計算第一個字符P0的跳轉距離，通過比較這兩個字符的跳轉距離來實現更大的跳轉，這樣不僅提高了Ti+m的利用率，而且獲得了更高的匹配效率。

3 算法性能測試

本實驗使用的計算機硬件平臺為IntelPentium G2020處理器，4G內存，軟件平臺為Windows 7操作系統，Microsoft Visual Studio 2010集成開發環境。在此環境下分別對BMHS算法、IBMHS算法和DBMHS算法進行測試，IBMHS匹配算法為文獻[8]中提出的對BMHS匹配算法的改進算法。

實驗隨機選取4個不同長度的文本串，實驗文本字符集由大小寫字母，數字和空格組成。模式串從文本串中隨機提取。分別執行BMHS算法、IBMHS算法和DBMHS算法程序，統計不同長度文本串，不同模式串的情況下，算法的執行時間和匹配窗口的移動次數。每個算法分別執行10000次，運行時間取平均值。得到的數據如表2和表3。

表2 ?匹配窗口移動次數

[文本長度＼&模式串長度＼&BMHS＼&IBMHS＼&DBMHS＼&匹配次數＼&匹配次數＼&匹配次數＼&2481＼&12＼&259＼&183＼&202＼&1138＼&10＼&114＼&90＼&95＼&555＼&14＼&44＼&32＼&35＼&225＼&12＼&16＼&13＼&14＼&]

表3 ?匹配時間

[文本長度＼&模式串長度＼&BMHS＼&IBMHS＼&DBMHS＼&匹配時間＼&匹配時間＼&匹配時間＼&2481＼&12＼&0.218＼&1.482＼&0.218＼&1138＼&10＼&0.094＼&0.671＼&0.094＼&555＼&14＼&0.031＼&0.218＼&0.031＼&225＼&12＼&0.016＼&0.094＼&0.016＼&]

由表2和表3可以看出，本文提出的算法相比傳統的BMHS算法有較大的改進。例如第一次匹配，DBMHS匹配次數較BMHS減少了約28%，并且文本長度越長，減少的匹配次數就會越多。此外，DBMHS在匹配用時上與傳統的BMHS算法比較接近。雖然IBMHS算法的匹配次數少于DBMHS算法，但是匹配時間幾乎是DBMHS算法的7倍。從效率上來說，DBMHS算法要優于其他算法。

4 結束語

本文通過分析BM，BMH和BMHS模式匹配算法，提出了一種改進的算法DBMHS。由于DBMHS算法充分利用了模式串兩端字符，通過實驗可以證明，該算法的匹配效率得到了顯著提升。下一步的研究將考慮該算法應用在多模式匹配中，并利用語言學中的知識，如模式串與文本結構，使其性能更加優越。

參考文獻：

[1] Yang Wang and Hidetsune Kobayashi. High Performance Pattern

Matching Algorithm for Network Security. IJCSNS International Journal of Computer Science and Network Security，2006.6（10）：83-87

[2] Boyer R S，Moore J S.A Fast String Searching Algorithm[J].

Communications of the ACM，1977.20：762-772

[3] Horspool N R. Practical Fast Searching in Strings[J]. Software

Practice and Experience，1980.10（6）：5012506

[4] Sunday D M. A very fast substring search algorithm[J].

Communication of the ACM，1990.33（8）：132-142

[5] 李雪瑩，劉寶旭等.字符串匹配技術研究[J].計算機工程，2004.30

（22）：24226

[6] 劉勝飛，張云泉.一種改進的BMH模式匹配算法[J].計算機科學，

2008.35（11）：164-165

[7] 姚保峰，王磊.一種改進的BMH模式匹配算法[J].湖南工程學院學報：

自然科學版，2011.3：40-42

[8] Yuan J， Yang J， Ding S. An Improved Pattern Matching Algorithm

Based on BMHS[C]//Distributed Computing and Applications to Business， Engineering & Science （DCABES）， 2012 11th International Symposium on. IEEE，2012：441-445

[9] 王浩，張霖.基于壞字符序檢測的快速模式匹配算法[J].計算機應用

與軟件，2012.29（5）：114-116

[10] Shrivastava G， Jain A. A Review of Intrusion Detection Method

Based On Automatic Pattern Matching[J]. Computer Engineering，2012.1（1）：88-90

[11] Chen Q， Niu Y， Wang Z， et al. Improved BM Pattern Matching

Algorithm for Intrusion Detection[C]//Computational Science and Optimization （CSO）， 2010 Third International Joint Conference on. IEEE，2010.1：440-444

[12] Chao Y. A deterministic finite automata based on improved BM

algorithm[C]//Computer Design and Applications （ICCDA），2010 International Conference on.IEEE，2010.2：V2-389-V2-391