基于BM的模式匹配改進(jìn)算法

王天聰， 侯整風(fēng)， 何 玲

(1.合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院，安徽合肥 230009;2.深圳金山信息安全技術(shù)有限公司，廣東深圳 518057)

0 引 言

模式匹配是計(jì)算機(jī)領(lǐng)域的一個(gè)重要研究方向，在WWW搜索引擎、內(nèi)容過(guò)濾防火墻、入侵檢測(cè)系統(tǒng)、信息壓縮乃至計(jì)算機(jī)理論等領(lǐng)域都有很重要的理論研究和應(yīng)用價(jià)值。

經(jīng)典的模式匹配算法有BF算法、KM P算法、BM算法、Tuned BM算法、BMH算法及BMHS算法[1-6]。在實(shí)際應(yīng)用中，BMHS算法的效率比BM算法要高。BM采用從右到左的比較方式，并利用當(dāng)前已匹配后綴和匹配失敗的字符，查找預(yù)處理過(guò)的好后綴跳躍表和壞字符跳躍表，使匹配跳躍式進(jìn)行，最大的可能跳躍距離為模式串長(zhǎng)度。BMHS算法只使用文本串中位于當(dāng)前窗口的下一個(gè)字符查找壞字符跳躍表，有效減少了字符比較次數(shù)。文獻(xiàn)[7]提出了BMG算法，該算法結(jié)合了BMH算法和BMHS算法的優(yōu)點(diǎn)，同時(shí)考慮了字符串后一位字母的唯一性，有效加快了匹配速度;文獻(xiàn)[8]提出的BMH2C算法在BM算法及其改進(jìn)算法的基礎(chǔ)上，利用當(dāng)前窗口的末字符和下一個(gè)字符組成字符串來(lái)計(jì)算右移量并保存在二維數(shù)組里，使得算法的效率得到很大提高;文獻(xiàn)[9]提出的BMN算法通過(guò)利用2個(gè)連續(xù)字符計(jì)算模式串移動(dòng)距離，提高了模式串移動(dòng)最大距離的概率。

本文在對(duì)BM和BMHS算法進(jìn)行簡(jiǎn)要介紹和分析的基礎(chǔ)上綜合兩者之長(zhǎng)，提出了一種更加快速的單模式匹配算法(FSBM)。該算法充分利用已匹配的后綴和字符串后一位字符的信息，以期在每一次跳躍中跳躍盡量大的距離。

1 BM和BMHS算法

本文中，使用t[1，2，…，n]表示正文文本，長(zhǎng)度為n;使用p[1，2，…，m]表示要匹配的模式串，長(zhǎng)度為m。字母表用∑表示，大小為σ。模式匹配是指在文本t中檢索子串p，匹配過(guò)程中t與p中長(zhǎng)度為m的子串的一次比較稱(chēng)為一次嘗試，當(dāng)前嘗試中與p對(duì)齊的t的子串稱(chēng)為當(dāng)前窗口。

1.1 BM算法

文獻(xiàn)[3]提出了著名的BM算法，該算法在匹配過(guò)程中，模式串 p[1，2，…，m]從左向右移動(dòng)，字符的比較從右向左進(jìn)行，即按p[m]，p[m-1]，…，p[1]次序進(jìn)行比較，當(dāng)匹配失敗時(shí)，使用壞字符跳躍表和好后綴跳躍表，并取兩者最大值來(lái)決定模式串的右移量，移動(dòng)盡可能遠(yuǎn)的距離。BM算法模式串右移算法如下:

(1)好后綴跳躍規(guī)則。具體分以下2種情況:①模式串 p中間的某一子串p[j-s+ 1，…，m-s]與已比較部分p[j+1，…，m]相同，可讓p右移s位;②p已比較部分p[j+1，…，m]的后綴 p[s+1，…，m]與 p的前綴p[1，…，m-s]相同，可讓p右移s位。滿足上述情況s的最小值為最佳右移距離。

好后綴跳躍規(guī)則定義如下:

(2)壞字符跳躍規(guī)則。假設(shè)匹配在文本串t[i]處失敗，此時(shí)對(duì)應(yīng)的模式串字符為p[j]，利用t[i]在模式串中出現(xiàn)的位置來(lái)決定右移量。壞字符跳躍規(guī)則定義如下:

根據(jù)BM算法，以文本串“decbedadeabadcdcdeadbad”，模式串“cdeadbad”為例，開(kāi)始匹配時(shí)，把模式串和文本串自左邊對(duì)齊，匹配過(guò)程見(jiàn)表1所列。

表1 BM算法匹配過(guò)程

1.2 BMHS算法

文獻(xiàn)[6]提出了改進(jìn)與簡(jiǎn)化的BM算法，即BMHS算法。BMHS算法將失配與計(jì)算右移量獨(dú)立，計(jì)算右移量時(shí)并不關(guān)心文本串中哪個(gè)字符造成了失配，而是簡(jiǎn)單地使用文本串與模式串最右端字符對(duì)齊的下一個(gè)字符t[k+1]來(lái)決定右移量，即只使用壞字符跳躍規(guī)則。BMHS算法的匹配過(guò)程見(jiàn)表2所列，壞字符跳躍規(guī)則定義如下:

表2 BM HS算法匹配過(guò)程

2 FSBM算法

2.1 算法思想

根據(jù)上述算法的分析，本文結(jié)合BM算法和BMHS算法的優(yōu)點(diǎn)，同時(shí)利用已匹配的后綴和字符串后一位字符t[k+1]的信息，提出了FSBM算法。該算法采用了BMHS算法的壞字符跳躍策略，同時(shí)把部分匹配的后綴和字符t[k+1]作為一個(gè)整體考慮。

設(shè)已成功匹配的后綴為u，v為u的后綴子串，當(dāng)前窗口的下一個(gè)字符為x。在當(dāng)前嘗試結(jié)束后，F(xiàn)SBM算法在p中自右向左地尋找最右的子串ux，并將該子串和t中的子串ux對(duì)齊;如果在p中不存在這樣的子串，則在p中尋找最長(zhǎng)的前綴，使之與ux的后綴vx相同，并使之對(duì)齊。

2.2 預(yù)處理階段

(1)生成壞字符跳躍表。對(duì)于字符表∑中的任意字符c:

(2)生成好后綴跳躍表。BM算法的好后綴轉(zhuǎn)移表為一維數(shù)組，大小與模式串長(zhǎng)度相同。FSBM算法的好后綴轉(zhuǎn)移表fsbmGs也是一維數(shù)組，由于其生成比BM算法多使用了一個(gè)字符的信息，匹配的時(shí)候該字符出現(xiàn)在當(dāng)前嘗試窗口的下一個(gè)位置，可假設(shè)模式串p的長(zhǎng)度為m，模式串p的最后一個(gè)字符p[m]可取值為字符表∑中的任意字符，設(shè)字符表的大小為σ，因?yàn)槠ヅ涫〉目赡芪恢脗€(gè)數(shù)為m(從0～m-1)，從而fsbmGs大小為mσ。在匹配過(guò)程中由文本串與模式串最右端字符對(duì)齊的下一個(gè)字符t[k+1]決定并與之相同，每次的右移距離由p[m]的取值和匹配失敗的位置共同決定。

借助 BM算法的預(yù)處理函數(shù) preBmGs，F(xiàn)SBM算法使用如下C代碼完成fsbmGs的預(yù)處理:

其中，SIZE等于字符表的大小σ;preBmGs為BM算法中初始化好后綴跳躍表的函數(shù)，該函數(shù)有3個(gè)參數(shù):即模式串、模式串長(zhǎng)度和好后綴表地址。

2.3 匹配過(guò)程

在匹配階段，對(duì)于當(dāng)前嘗試，如果匹配成功，當(dāng)前窗口右移一個(gè)字符。如果當(dāng)前嘗試失敗，F(xiàn)SBM算法根據(jù)匹配失敗的位置和當(dāng)前窗口的緊鄰下一個(gè)字符一起從fsbmGs表中取得好后綴跳躍距離，根據(jù)當(dāng)前窗口的緊鄰下一個(gè)字符從fsbm Bc表中取壞字符跳躍距離，并取這2個(gè)跳躍距離的較大者作為實(shí)際的跳躍距離，匹配過(guò)程見(jiàn)表3所列。

表3 FSBM算法匹配過(guò)程

在表3中，當(dāng)?shù)?次匹配時(shí)，在t[5]處失配，已成功匹配后綴ad和當(dāng)前窗口的緊鄰下一個(gè)字符e組成字符串a(chǎn)de，在模式串p中尋找最右端的相同字符串或子串，跳躍距離為9;根據(jù)當(dāng)前窗口的下一個(gè)字符e，在模式串中需找最右端的字符e，跳躍距離為6。取兩者最大值為9，模式串右移9位。第2次匹配時(shí)，在t[15]處失配，已成功匹配后綴d和當(dāng)前窗口的緊鄰下一個(gè)字符e組成字符串de，在模式串p中尋找最右端的相同字符串或子串，跳躍距離為6;根據(jù)當(dāng)前窗口的下一個(gè)字符e，在模式串中需找最右端的字符e，跳躍距離為6。取兩者最大值為6，模式串右移6位。在第3次匹配成功。

FSBM算法程序如下:

FSBM算法流程如圖1所示。

圖1 FSBM算法流程圖

在上例文本串“decbedadeabadcdcdeadbad”和模式串“cdeadbad”，用BM、BMHS、FSBM算法匹配次數(shù)分別是5次、4次和3次。BM、BMHS、FSBM算法的時(shí)間復(fù)雜度分別為O(n/m)、O(n/m+1)和O(n/m+1)。在BMHS算法中，產(chǎn)生最大位移量的情況為當(dāng)前匹配窗口下一個(gè)字符不在模式串中，模式串跳躍距離為m+1;在FSBM算法中產(chǎn)生最大位移量的情況為好后綴和當(dāng)前匹配窗口的下一個(gè)字符組成的字符串在模式串沒(méi)有相同的字符串或子串，以及當(dāng)前匹配窗口下一個(gè)字符不在模式串中，模式串跳躍距離為m+1。所以，F(xiàn)SBM算法產(chǎn)生最大跳躍距離的概率比BM和BMHS算法要大。

3 實(shí)驗(yàn)結(jié)果

為了測(cè)試算法的性能，從網(wǎng)上隨機(jī)選取英文網(wǎng)頁(yè)，組成大小為1 M的純英文文本，分別用長(zhǎng)度為2、5、8、10、20的5種不同模式對(duì)BM、BMHS、FSBM算法進(jìn)行測(cè)試，測(cè)試結(jié)果如圖2所示。

從圖2可以看出，對(duì)于匹配次數(shù)，F(xiàn)SBM算法少于BM算法。在純英文語(yǔ)料上FSBM算法的匹配次數(shù)平均為BM算法的70.4%，為BMHS算法的90.4%，F(xiàn)SBM算法對(duì)效率的提高較為明顯。

圖2 匹配次數(shù)

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

FSBM算法綜合了BM和BMHS算法的優(yōu)點(diǎn)，在模式匹配過(guò)程中，有效地結(jié)合了好后綴與當(dāng)前匹配窗口的下一個(gè)字符信息。實(shí)驗(yàn)結(jié)果表明，F(xiàn)SBM算法顯著提高了匹配效率，減少了模式串右移次數(shù)，快速提高了匹配速度，具有廣闊的應(yīng)用前景。

[1] Charras C，Lecroq T.Exact stringmatching algorithm s[EB/ O L].[2010-04-16].http://ww r-igm.univ-m lv.fr/～ lecroq/String.

[2] Knuth D E，Mor ris JH，Pratt V R.Fast pattern in strings [J].SIAM Journal on Com puting，1977，6(2):323-350.

[3] Boyer RS，M oore JS.A fast string searching algorithm[J]. Communications of the ACM，1977，20(10):762-772.

[4] Hum e A，Sunday D M.Fast string searching[J].Software Practice and Experience，1991，21(11):1221-1248.

[5] H orspool R N.Practical fast searching in strings[J].Softw are Practice and Ex perience，1980，10(6):501-506.

[6] Sunday D M.A very fast substring search algorithm[J]. Communications of the ACM，1990，33(3):132-142.

[7] 錢(qián) 屹，侯義斌.一種快速的字符串匹配算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2004，25(3):400-413.

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

[9] 何 畏，汪榮貴，查全民.一種新的快速移動(dòng)單模式匹配算法[J].合肥工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版，2010，33(5): 665-669.