基于BM的模式匹配改进算法

王天聪， 侯整风， 何 玲

(1.合肥工业大学计算机与信息学院，安徽合肥 230009;2.深圳金山信息安全技术有限公司，广东深圳 518057)

0 引 言

模式匹配是计算机领域的一个重要研究方向，在WWW搜索引擎、内容过滤防火墙、入侵检测系统、信息压缩乃至计算机理论等领域都有很重要的理论研究和应用价值。

经典的模式匹配算法有BF算法、KM P算法、BM算法、Tuned BM算法、BMH算法及BMHS算法[1-6]。在实际应用中，BMHS算法的效率比BM算法要高。BM采用从右到左的比较方式，并利用当前已匹配后缀和匹配失败的字符，查找预处理过的好后缀跳跃表和坏字符跳跃表，使匹配跳跃式进行，最大的可能跳跃距离为模式串长度。BMHS算法只使用文本串中位于当前窗口的下一个字符查找坏字符跳跃表，有效减少了字符比较次数。文献[7]提出了BMG算法，该算法结合了BMH算法和BMHS算法的优点，同时考虑了字符串后一位字母的唯一性，有效加快了匹配速度;文献[8]提出的BMH2C算法在BM算法及其改进算法的基础上，利用当前窗口的末字符和下一个字符组成字符串来计算右移量并保存在二维数组里，使得算法的效率得到很大提高;文献[9]提出的BMN算法通过利用2个连续字符计算模式串移动距离，提高了模式串移动最大距离的概率。

本文在对BM和BMHS算法进行简要介绍和分析的基础上综合两者之长，提出了一种更加快速的单模式匹配算法(FSBM)。该算法充分利用已匹配的后缀和字符串后一位字符的信息，以期在每一次跳跃中跳跃尽量大的距离。

1 BM和BMHS算法

本文中，使用t[1，2，…，n]表示正文文本，长度为n;使用p[1，2，…，m]表示要匹配的模式串，长度为m。字母表用∑表示，大小为σ。模式匹配是指在文本t中检索子串p，匹配过程中t与p中长度为m的子串的一次比较称为一次尝试，当前尝试中与p对齐的t的子串称为当前窗口。

1.1 BM算法

文献[3]提出了著名的BM算法，该算法在匹配过程中，模式串 p[1，2，…，m]从左向右移动，字符的比较从右向左进行，即按p[m]，p[m-1]，…，p[1]次序进行比较，当匹配失败时，使用坏字符跳跃表和好后缀跳跃表，并取两者最大值来决定模式串的右移量，移动尽可能远的距离。BM算法模式串右移算法如下:

(1)好后缀跳跃规则。具体分以下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的最小值为最佳右移距离。

好后缀跳跃规则定义如下:

(2)坏字符跳跃规则。假设匹配在文本串t[i]处失败，此时对应的模式串字符为p[j]，利用t[i]在模式串中出现的位置来决定右移量。坏字符跳跃规则定义如下:

根据BM算法，以文本串“decbedadeabadcdcdeadbad”，模式串“cdeadbad”为例，开始匹配时，把模式串和文本串自左边对齐，匹配过程见表1所列。

表1 BM算法匹配过程

1.2 BMHS算法

文献[6]提出了改进与简化的BM算法，即BMHS算法。BMHS算法将失配与计算右移量独立，计算右移量时并不关心文本串中哪个字符造成了失配，而是简单地使用文本串与模式串最右端字符对齐的下一个字符t[k+1]来决定右移量，即只使用坏字符跳跃规则。BMHS算法的匹配过程见表2所列，坏字符跳跃规则定义如下:

表2 BM HS算法匹配过程

2 FSBM算法

2.1 算法思想

根据上述算法的分析，本文结合BM算法和BMHS算法的优点，同时利用已匹配的后缀和字符串后一位字符t[k+1]的信息，提出了FSBM算法。该算法采用了BMHS算法的坏字符跳跃策略，同时把部分匹配的后缀和字符t[k+1]作为一个整体考虑。

设已成功匹配的后缀为u，v为u的后缀子串，当前窗口的下一个字符为x。在当前尝试结束后，FSBM算法在p中自右向左地寻找最右的子串ux，并将该子串和t中的子串ux对齐;如果在p中不存在这样的子串，则在p中寻找最长的前缀，使之与ux的后缀vx相同，并使之对齐。

2.2 预处理阶段

(1)生成坏字符跳跃表。对于字符表∑中的任意字符c:

(2)生成好后缀跳跃表。BM算法的好后缀转移表为一维数组，大小与模式串长度相同。FSBM算法的好后缀转移表fsbmGs也是一维数组，由于其生成比BM算法多使用了一个字符的信息，匹配的时候该字符出现在当前尝试窗口的下一个位置，可假设模式串p的长度为m，模式串p的最后一个字符p[m]可取值为字符表∑中的任意字符，设字符表的大小为σ，因为匹配失败的可能位置个数为m(从0～m-1)，从而fsbmGs大小为mσ。在匹配过程中由文本串与模式串最右端字符对齐的下一个字符t[k+1]决定并与之相同，每次的右移距离由p[m]的取值和匹配失败的位置共同决定。

借助 BM算法的预处理函数 preBmGs，FSBM算法使用如下C代码完成fsbmGs的预处理:

其中，SIZE等于字符表的大小σ;preBmGs为BM算法中初始化好后缀跳跃表的函数，该函数有3个参数:即模式串、模式串长度和好后缀表地址。

2.3 匹配过程

在匹配阶段，对于当前尝试，如果匹配成功，当前窗口右移一个字符。如果当前尝试失败，FSBM算法根据匹配失败的位置和当前窗口的紧邻下一个字符一起从fsbmGs表中取得好后缀跳跃距离，根据当前窗口的紧邻下一个字符从fsbm Bc表中取坏字符跳跃距离，并取这2个跳跃距离的较大者作为实际的跳跃距离，匹配过程见表3所列。

表3 FSBM算法匹配过程

在表3中，当第1次匹配时，在t[5]处失配，已成功匹配后缀ad和当前窗口的紧邻下一个字符e组成字符串ade，在模式串p中寻找最右端的相同字符串或子串，跳跃距离为9;根据当前窗口的下一个字符e，在模式串中需找最右端的字符e，跳跃距离为6。取两者最大值为9，模式串右移9位。第2次匹配时，在t[15]处失配，已成功匹配后缀d和当前窗口的紧邻下一个字符e组成字符串de，在模式串p中寻找最右端的相同字符串或子串，跳跃距离为6;根据当前窗口的下一个字符e，在模式串中需找最右端的字符e，跳跃距离为6。取两者最大值为6，模式串右移6位。在第3次匹配成功。

FSBM算法程序如下:

FSBM算法流程如图1所示。

图1 FSBM算法流程图

在上例文本串“decbedadeabadcdcdeadbad”和模式串“cdeadbad”，用BM、BMHS、FSBM算法匹配次数分别是5次、4次和3次。BM、BMHS、FSBM算法的时间复杂度分别为O(n/m)、O(n/m+1)和O(n/m+1)。在BMHS算法中，产生最大位移量的情况为当前匹配窗口下一个字符不在模式串中，模式串跳跃距离为m+1;在FSBM算法中产生最大位移量的情况为好后缀和当前匹配窗口的下一个字符组成的字符串在模式串没有相同的字符串或子串，以及当前匹配窗口下一个字符不在模式串中，模式串跳跃距离为m+1。所以，FSBM算法产生最大跳跃距离的概率比BM和BMHS算法要大。

3 实验结果

为了测试算法的性能，从网上随机选取英文网页，组成大小为1 M的纯英文文本，分别用长度为2、5、8、10、20的5种不同模式对BM、BMHS、FSBM算法进行测试，测试结果如图2所示。

从图2可以看出，对于匹配次数，FSBM算法少于BM算法。在纯英文语料上FSBM算法的匹配次数平均为BM算法的70.4%，为BMHS算法的90.4%，FSBM算法对效率的提高较为明显。

图2 匹配次数

4 结束语

FSBM算法综合了BM和BMHS算法的优点，在模式匹配过程中，有效地结合了好后缀与当前匹配窗口的下一个字符信息。实验结果表明，FSBM算法显著提高了匹配效率，减少了模式串右移次数，快速提高了匹配速度，具有广阔的应用前景。

[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] 钱 屹，侯义斌.一种快速的字符串匹配算法[J].小型微型计算机系统，2004，25(3):400-413.

[8] 张 娜，侯整风.一种快速的BM模式匹配改进算法[J].合肥工业大学学报:自然科学版，2006，29(7):834-838.

[9] 何 畏，汪荣贵，查全民.一种新的快速移动单模式匹配算法[J].合肥工业大学学报:自然科学版，2010，33(5): 665-669.