一種改進(jìn)的BM算法性能分析

朱保鋒，宋 艷

(河南教育學(xué)院信息技術(shù)系，鄭州 450046)

隨著計(jì)算機(jī)應(yīng)用技術(shù)的快速發(fā)展，處理非數(shù)值數(shù)據(jù)的應(yīng)用增長迅速，使得字符匹配問題顯得尤為重要，在入侵檢測、信息檢索、搜索引擎等領(lǐng)域都有所涉及，字符匹配算法效率的高低對搜索引擎在數(shù)據(jù)查找方面的性能有著非常直接的影響。因此需要找到一種適合、高效的字符匹配算法。

1 BM算法概述

字符匹配是將搜集到的文本信息和數(shù)據(jù)庫中已經(jīng)存在的模式數(shù)據(jù)信息進(jìn)行比較，找出模式串在文本串中的出現(xiàn)位置。當(dāng)前的字符匹配算法有很多種，例如:蠻力算法、BM 算法、Horspool算法、Wu-Manber算法等?；谧址麙呙璨呗缘牟煌址ヅ渌惴梢苑譃槿?1)從左到右掃描模式和文本每一對相應(yīng)的字符，一旦不匹配，模式右移一格，進(jìn)行下一輪嘗試，蠻力字符匹配就是該類算法，其平均效率是屬于O(n*m)的。2)自右向左匹配文本串與模式串的最大后綴，BM算法、Horspool算法屬于此類，BM的最差效率是線性的，Horspool是BM的簡化版本。3)自右向左匹配文本串與模式串的最大子串。

1977年，Robert S.Boyer和 J Strother Moore提出了另一種在O(n)時間復(fù)雜度內(nèi)，完成字符串匹配的算法，其在絕大多數(shù)場合的性能表現(xiàn)，比KMP算法還要出色，這就是BM算法，一直被認(rèn)為是最有效的字符匹配算法，開源入侵檢測系統(tǒng)Snort就是采用BM算法［1］。但是在BM算法中，有些比較是多余的，降低了算法的執(zhí)行效率，因此提出一種改進(jìn)的BM算法，通過實(shí)驗(yàn)數(shù)據(jù)可以表明，改進(jìn)后的算法能夠提高傳統(tǒng)BM算法的效率。

2 BM算法的基本原理

BM算法被認(rèn)為是亞線性串匹配算法，它在最壞情況下找到模式所有出現(xiàn)的時間復(fù)雜度為O(mn)，在最好情況下執(zhí)行匹配找到模式所有出現(xiàn)的時間復(fù)雜度為O(n/m)。

2.1 定義

定義1:設(shè)Σ為字母表，T，P∈Σ+，其中文本串T=t0t1t2…tn-1，模式串 P=p0p1p2…pm-1，m ＜ n。

定義2:c∈Σ且c∈T，c是壞符號，導(dǎo)致模式串P和字符串T的相應(yīng)字符不匹配;d是模式串相對于文本串移動的距離;k∈N，是文本串與模式串匹配的最大后綴。

2.2 BM算法的工作原理

文本串T與模式串P左對齊，從pm-1開始自右向左，比較文本和模式的相應(yīng)字符對，如果p0p1p2…pm-1與T中的 titi+1ti+2…ti+m-1一一匹配，則找到了P在T中的出現(xiàn)，返回i，如果模式P超出了文本T，則P沒有在T中出現(xiàn)，返回 -1。

模式串P最右邊的字符pm-1和文本串T的相應(yīng)字符c初次比較失敗了，模式串P要盡量向右移動足夠長的距離［2］，以減少移動的次數(shù)和比較的次數(shù)，降低算法的復(fù)雜度。如果c不包含在P的前m-1個字符中，P移動的最長距離為len(P)=m;如果c出現(xiàn)在P的前m-1個字符中(出現(xiàn)的次數(shù)有可能＞1)，此時向右移動P，使P中最右邊的c和T中的c對齊，此時P的移動距離是和c相關(guān)的。將模式P向右移動的長度用t(c)表示為［3］:

模式串P與文本串T在遇到壞符號c之前，已經(jīng)有k(0＜k＜m)個字符成功匹配，模式串P向右移動的長度d參照兩個規(guī)則:壞符號移動規(guī)則和好后綴移動規(guī)則。

壞符號移動規(guī)則:該規(guī)則參照壞符號c，如果c不在P中，將P移動到正好跳過字符c，移動的長度表示為m-k;如果c存在于模式中，將P前m-k個字符最右邊的c和T中的c對齊，參照公式(1)，P移動的距離表示為t(c)-k。當(dāng)k相對于t(c)足夠大時會導(dǎo)致t(c)-k＜0，參照蠻力算法可以使P向右移動1個位置。針對字母集Σ中的每個字符計(jì)算壞符號移動表，壞符號移動的距離表示為:

好后綴移動規(guī)則:模式串P與文本串T已經(jīng)匹配的k個字符，稱為好后綴，記作suff(k)，如果模式P的前m-k個字符中可以找到一個最長字符組合v(len(v)＜k)是suff(k)的后綴，移動P使前m-k個字符的最右邊的v和suff(k)中的v對齊，此時v是和k相關(guān)的。好后綴移動的距離表示為:

取d=max(d1，d2)作為P向右移動的最大距離。

在算法的實(shí)現(xiàn)中，事先構(gòu)建壞符號移動表和好后綴移動表，以減少在不同的c、v和k作用下查找和計(jì)算d值的次數(shù)，提高效率［4］。

3 一種改進(jìn)的BM算法

3.1 BM算法的改進(jìn)

傳統(tǒng)的BM算法中存在不必要的比較，當(dāng)模式串在文本串中的初次匹配失敗后，可以根據(jù)文本串中當(dāng)前窗口的下一個字符(即模式串和文本串左對齊后的最右側(cè)字符的下一個字符)決定偏移量，此時只使用壞符號移動規(guī)則。如果該字符在模式串中沒有出現(xiàn)，最大可以移動的位置為m+1。算法改進(jìn)后模式向右移動的距離可以用公式4表示:

3.2 BM算法的改進(jìn)的舉例

假設(shè)有文本串T和模式串P分別為，P:algorithm，T:this_is_boyer_mbore_algorithms，分析在改進(jìn)的BM算法中，P匹配T的過程。生成的壞字符跳躍表如表1所示，對于模式P中出現(xiàn)過的字符“algorithm”，其對應(yīng)的偏移量skip(c)是該字符在模式最右邊的出現(xiàn)位置距離模式最右側(cè)字符的長度，其它沒有在模式中出現(xiàn)的字符，其偏移量為m+1=10。

表1 壞字符跳躍表

T:this_is_boyer_mbore_algorithms

P:algorithm

第一次匹配:模式串的最右邊的字符“m”和文本串中的字符“b”比較，第一次字符比較失敗，此時當(dāng)前窗口的下一個字符為“o”，根據(jù)表1知模式串P向右移動的距離為skip(o)=6。

T:this_is_boyer_mbore_algorithms

P:algorithm

第二次匹配:第一次比較模式串中的字符“m”和文本串中的字符“m”，匹配成功，繼續(xù)比較文本串中的字符“_”和模式串中的字符“h”，匹配失敗，此時當(dāng)前窗口的下一個字符為“b”，根據(jù)表1知移動的距離為skip(b)=m+1=10，模式向右移動10個字符的位置。

T:this_is_boyer_mbore_algorithms

P:algorithm

第三次匹配:文本串中的字符“r”和模式串中的字符“m”比較，不匹配，當(dāng)前窗口的下一個字符是“i”，根據(jù)表1，skip(i)=4，模式串 P向右移動4個字符位置。

T:this_is_boyer_mbore_algorithms

P:algorithm

第四次匹配:從模式串的尾字符“m”開始自右向左和文本串的相應(yīng)字符依次比較，直到k=m，最終找到了模式串在文本串中的出現(xiàn)。

3.3 BM算法的改進(jìn)前后的比較

根據(jù)改進(jìn)的BM算法思想，抽取數(shù)據(jù)進(jìn)行實(shí)驗(yàn)驗(yàn)證。在實(shí)驗(yàn)中，隨機(jī)選取了4組樣本，模式串的長度基本不變?nèi)?個字符，文本串的字符長度分別選取為500、1000、1500、2000，對于每組樣本，分別采用傳統(tǒng)的BM算法和改進(jìn)后的BM算法，得到的字符比較次數(shù)和模式串的移動次數(shù)的情況如表2所示，每組樣本下模式移動次數(shù)的情況對比如圖1所示。

表2 BM算法改進(jìn)前后字符匹配時比較次數(shù)和移動次數(shù)

在實(shí)際的字符查找應(yīng)用中，初次比較不匹配、當(dāng)前窗口的最后一個字符和下一字符不屬于模式串的情況是多數(shù)的。在這種情況下，采用改進(jìn)的BM算法在每次的匹配中可以增加模式串的移動距離，從而減少比較的次數(shù)。

圖1 BM算法和改進(jìn)BM算法比較次數(shù)和移動次數(shù)對比

4 結(jié)論

在傳統(tǒng)的BM算法中存在一些不必要的比較，增加了字符匹配時的比較次數(shù)，從而在實(shí)際的應(yīng)用系統(tǒng)中導(dǎo)致系統(tǒng)效率不高。在改進(jìn)的BM算法中，通過結(jié)合當(dāng)前窗口的下一個字符的情況更改模式串的移動距離的長度，可以讓移動的距離增加1，最大能夠達(dá)到m+1。實(shí)驗(yàn)數(shù)據(jù)表明，當(dāng)文本串相對于模式串足夠長，模式串在文本串中的出現(xiàn)次數(shù)增加時，可以很大的提高算法的查找效率.

［1］韓光輝，曾誠.BM算法中函數(shù)shift的研究［J］.計(jì)算機(jī)應(yīng)用，2013，33(8):2379-2382.

［2］孫文靜，錢華.改進(jìn)BM算法及其在網(wǎng)絡(luò)入侵檢測中的應(yīng)用［J］.計(jì)算機(jī)科學(xué)，2013，40(12):174-176.

［3］Anany Levitin.算法設(shè)計(jì)與分析基礎(chǔ)［M］.北京:清華大學(xué)出版社，2007.

［4］李韋男，虞慧群.一種改進(jìn)的BM字符串匹配算法［J］.計(jì)算機(jī)工程與應(yīng)用，2014，50(16):104-108.