朱保鋒，宋 艷

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

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

1 BM算法概述

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

1977年，Robert S.Boyer和 J Strother Moore提出了另一種在O(n)時(shí)間復(fù)雜度內(nèi)，完成字符串匹配的算法，其在絕大多數(shù)場(chǎng)合的性能表現(xiàn)，比KMP算法還要出色，這就是BM算法，一直被認(rèn)為是最有效的字符匹配算法，開源入侵檢測(cè)系統(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)的時(shí)間復(fù)雜度為O(mn)，在最好情況下執(zhí)行匹配找到模式所有出現(xiàn)的時(shí)間復(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是壞符號(hào)，導(dǎo)致模式串P和字符串T的相應(yīng)字符不匹配;d是模式串相對(duì)于文本串移動(dòng)的距離;k∈N，是文本串與模式串匹配的最大后綴。

2.2 BM算法的工作原理

文本串T與模式串P左對(duì)齊，從pm-1開始自右向左，比較文本和模式的相應(yīng)字符對(duì)，如果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要盡量向右移動(dòng)足夠長(zhǎng)的距離［2］，以減少移動(dòng)的次數(shù)和比較的次數(shù)，降低算法的復(fù)雜度。如果c不包含在P的前m-1個(gè)字符中，P移動(dòng)的最長(zhǎng)距離為len(P)=m;如果c出現(xiàn)在P的前m-1個(gè)字符中(出現(xiàn)的次數(shù)有可能＞1)，此時(shí)向右移動(dòng)P，使P中最右邊的c和T中的c對(duì)齊，此時(shí)P的移動(dòng)距離是和c相關(guān)的。將模式P向右移動(dòng)的長(zhǎng)度用t(c)表示為［3］:

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

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

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

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

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

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

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

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

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

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

表1 壞字符跳躍表

T:this_is_boyer_mbore_algorithms

P:algorithm

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

T:this_is_boyer_mbore_algorithms

P:algorithm

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

T:this_is_boyer_mbore_algorithms

P:algorithm

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

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組樣本，模式串的長(zhǎng)度基本不變?nèi)?個(gè)字符，文本串的字符長(zhǎng)度分別選取為500、1000、1500、2000，對(duì)于每組樣本，分別采用傳統(tǒng)的BM算法和改進(jìn)后的BM算法，得到的字符比較次數(shù)和模式串的移動(dòng)次數(shù)的情況如表2所示，每組樣本下模式移動(dòng)次數(shù)的情況對(duì)比如圖1所示。

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

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

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

4 結(jié)論

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

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

［2］孫文靜，錢華.改進(jìn)BM算法及其在網(wǎng)絡(luò)入侵檢測(cè)中的應(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.