一種改進(jìn)的BMHS模式匹配算法

張歡 胡勇

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

關(guān)鍵詞： 模式匹配; 跳轉(zhuǎn)距離; BM算法; BMH算法; BMHS算法; DBMHS算法

中圖分類號(hào)：TP393 ? ? ? ? ?文獻(xiàn)標(biāo)志碼：A ? ? 文章編號(hào)：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 引言

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

1 典型算法

1.1 BM算法

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

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

圖1 ?壞字符規(guī)則

⑵ 好后綴跳躍表： 當(dāng)Pk≠Ti（k

圖2 ?好后綴規(guī)則

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

1.2 BMH算法

Horspool提出的BMH算法相對(duì)于BM算法更容易實(shí)現(xiàn)。BMH算法在預(yù)處理階段只使用了壞字符跳躍表，無論文本中哪個(gè)字符造成了匹配失敗，都將依據(jù)壞字符跳轉(zhuǎn)表向右移動(dòng)。BMH算法的基本思想是：①搜索文本時(shí)，從頭到尾搜索，匹配時(shí)從右向左匹配。首先比較文本指針?biāo)缸址湍Ｊ酱淖詈笠粋€(gè)字符，如果相等，再比較其余m-1個(gè)字符，無論文本中哪個(gè)字符造成了匹配失敗，都將由文本中和模式串最后一個(gè)位置對(duì)應(yīng)的字符來啟發(fā)模式串向右移動(dòng)，即當(dāng)匹配開始比較TiTi+1…Ti+m-1和P0P1…Pm-1時(shí)，一旦發(fā)生不匹配，計(jì)算跳轉(zhuǎn)距離skip（Ti+m-1），跳轉(zhuǎn)后將模式串和文本對(duì)齊后重新匹配。②如果與P完全匹配，返回在T中對(duì)應(yīng)的位置;③如果搜索完T仍然找不到完全匹配的位置，則查找失敗[3]（如圖3所示）。壞字符跳轉(zhuǎn)計(jì)算公式：

圖3 ?BMH算法

如圖3所示，當(dāng)文本中的與T2（‘d）與模式串P中的P2（‘c）發(fā)生不匹配時(shí)，計(jì)算跳轉(zhuǎn)距離skip（T4），可以看出P1與T4相等，模式串P向右移動(dòng)3個(gè)字符，即skip（T4）等于3，然后將P1與T4對(duì)齊后重新匹配。

BMH算法簡(jiǎn)化了初始化過程，匹配過程中的判斷過程也作了簡(jiǎn)化，因?yàn)锽MH算法只采用了BM算法的壞字符移動(dòng)規(guī)則，并且將失配情況與偏移量的計(jì)算獨(dú)立，不關(guān)心文本串中哪個(gè)字符造成了失配，只考慮用于模式串最右端對(duì)齊的文本字符來決定偏移量。該算法的理論時(shí)間復(fù)雜度與BM算法一致，但實(shí)際使用情況下較BM算法效率高。

1.3 BMHS算法

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

圖4 ?BMHS算法

如圖4所示，當(dāng)Ti+m出現(xiàn)在模式串P中時(shí)，如圖4（a），將模式串P中的字符‘e與Ti+m對(duì)齊;當(dāng)Ti+m不存在于模式串P中時(shí)，如圖4（b）所示，模式串P向右移動(dòng)m+1個(gè)字符;而圖4（c）中當(dāng)Ti+m存在于模式串P中，而Ti+m-1不存在于模式串P中時(shí)，skip（Ti+m-1）等于5，而skip（Ti+m）等于1，Ti+m-1的跳轉(zhuǎn)距離大于Ti+m的跳轉(zhuǎn)距離，若還使用Ti+m為標(biāo)準(zhǔn)，則會(huì)降低匹配效率。在BMHS算法中最理想的時(shí)間復(fù)雜度為O（n/m+1）。

1.4 對(duì)各算法的已有改進(jìn)

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

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

2012年袁靜波提出了一種改進(jìn)的BMHS模式匹配算法[8]。該算法在BMHS算法的基礎(chǔ)上利用文本T中與模式串P最后一個(gè)字符對(duì)應(yīng)的字符Ti+m-1，以及Ti+m和Ti+m+1來實(shí)現(xiàn)跳轉(zhuǎn)，模式串P和文本T從右向左匹配。以下是具體匹配過程。

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

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

第二步：當(dāng)Ti+m在模式串中時(shí)，判斷子串Ti+m Ti+m+1是否在模式串P中，若不存在，則跳過m+2的距離，如圖6，子串“be”不在模式串P中，則模式串向右跳轉(zhuǎn)m+2個(gè)字符。

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

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

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

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

圖8 ?比較得到較大值進(jìn)行跳轉(zhuǎn)

在該改進(jìn)算法中，模式串P最大的跳轉(zhuǎn)距離為m+2，在理想的情況下該算法的時(shí)間復(fù)雜度為O（n/m+2）。

2 DBMHS算法

2.1 基本思想

通過觀察BM，BMH和BMHS算法的匹配過程可以發(fā)現(xiàn)，這些算法在匹配窗口的首字符匹配均失敗時(shí)效率最優(yōu)。本文提出的DBMHS算法通過比較模式串P的第一個(gè)字符P0的跳轉(zhuǎn)距離jump（P1）和在T中與模式串P最后一個(gè)字符對(duì)應(yīng)的后一個(gè)字符Ti+m的跳轉(zhuǎn)距離jump（Ti+m）來移動(dòng)模式串P。跳轉(zhuǎn)距離公式如下：

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 匹配算法

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

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

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

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

圖11 ?P1跳轉(zhuǎn)距離大于Ti+m

若算法在匹配時(shí)自右向左均匹配成功，則此時(shí)找到一次完全匹配，算法結(jié)束。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算法在比較時(shí)利用下一個(gè)字符Ti+m決定右移量，當(dāng)Ti+m不在模式串P中出現(xiàn)時(shí)會(huì)跳轉(zhuǎn)最大的距離m+1，但當(dāng)Ti+m出現(xiàn)在模式串P中時(shí)，由于多進(jìn)行了一次匹配，BMHS匹配算法的效果就不如BMH算法。因此，DBMHS匹配算法通過模式串兩端的字符來充分利用Ti+m。當(dāng)Ti+m出現(xiàn)在模式串P中時(shí)，計(jì)算Ti+m的跳轉(zhuǎn)距離，并計(jì)算第一個(gè)字符P0的跳轉(zhuǎn)距離，通過比較這兩個(gè)字符的跳轉(zhuǎn)距離來實(shí)現(xiàn)更大的跳轉(zhuǎn)，這樣不僅提高了Ti+m的利用率，而且獲得了更高的匹配效率。

3 算法性能測(cè)試

本實(shí)驗(yàn)使用的計(jì)算機(jī)硬件平臺(tái)為IntelPentium G2020處理器，4G內(nèi)存，軟件平臺(tái)為Windows 7操作系統(tǒng)，Microsoft Visual Studio 2010集成開發(fā)環(huán)境。在此環(huán)境下分別對(duì)BMHS算法、IBMHS算法和DBMHS算法進(jìn)行測(cè)試，IBMHS匹配算法為文獻(xiàn)[8]中提出的對(duì)BMHS匹配算法的改進(jìn)算法。

實(shí)驗(yàn)隨機(jī)選取4個(gè)不同長(zhǎng)度的文本串，實(shí)驗(yàn)文本字符集由大小寫字母，數(shù)字和空格組成。模式串從文本串中隨機(jī)提取。分別執(zhí)行BMHS算法、IBMHS算法和DBMHS算法程序，統(tǒng)計(jì)不同長(zhǎng)度文本串，不同模式串的情況下，算法的執(zhí)行時(shí)間和匹配窗口的移動(dòng)次數(shù)。每個(gè)算法分別執(zhí)行10000次，運(yùn)行時(shí)間取平均值。得到的數(shù)據(jù)如表2和表3。

表2 ?匹配窗口移動(dòng)次數(shù)

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

表3 ?匹配時(shí)間

[文本長(zhǎng)度＼&模式串長(zhǎng)度＼&BMHS＼&IBMHS＼&DBMHS＼&匹配時(shí)間＼&匹配時(shí)間＼&匹配時(shí)間＼&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可以看出，本文提出的算法相比傳統(tǒng)的BMHS算法有較大的改進(jìn)。例如第一次匹配，DBMHS匹配次數(shù)較BMHS減少了約28%，并且文本長(zhǎng)度越長(zhǎng)，減少的匹配次數(shù)就會(huì)越多。此外，DBMHS在匹配用時(shí)上與傳統(tǒng)的BMHS算法比較接近。雖然IBMHS算法的匹配次數(shù)少于DBMHS算法，但是匹配時(shí)間幾乎是DBMHS算法的7倍。從效率上來說，DBMHS算法要優(yōu)于其他算法。

4 結(jié)束語

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

參考文獻(xiàn)：

[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] 李雪瑩，劉寶旭等.字符串匹配技術(shù)研究[J].計(jì)算機(jī)工程，2004.30

（22）：24226

[6] 劉勝飛，張?jiān)迫?一種改進(jìn)的BMH模式匹配算法[J].計(jì)算機(jī)科學(xué)，

2008.35（11）：164-165

[7] 姚保峰，王磊.一種改進(jìn)的BMH模式匹配算法[J].湖南工程學(xué)院學(xué)報(bào)：

自然科學(xué)版，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] 王浩，張霖.基于壞字符序檢測(cè)的快速模式匹配算法[J].計(jì)算機(jī)應(yīng)用

與軟件，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