一种改进的BMHS模式匹配算法

张欢 胡勇

摘  要： 模式匹配在计算机应用中扮演着很重要的角色。通过分析BM，BMH和BMHS算法及相关改进算法，提出BMHS算法的改进算法（DBMHS）。该算法（DBMHS）充分利用模式串两端字符，通过比较模式串两端字符的跳转距离来实现更大距离的跳转。实验证明，改进后的算法显著增加了匹配窗口的跳转距离，有效地提高了匹配效率。

关键词： 模式匹配; 跳转距离; BM算法; BMH算法; BMHS算法; DBMHS算法

中图分类号：TP393          文献标志码：A     文章编号：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 引言

随着网络技术的高速发展，网络资源呈爆炸式增长。如何在网络数据中找到需要的信息，已经成为人们研究的热点问题。模式匹配算法在很多领域得到了较为广泛的应用，如入侵检测、计算机病毒特征匹配[1]、搜索引擎、文本挖掘等。目前关于模式匹配的算法有很多，其中最著名的是BM算法[2]。BM算法发展的过程中，1980年Horspol发表了改进与简化BM算法的论文，即Boyer Moore Horspoo（BMH）算法[3]，随后Sunday在1990年在BMH算法的基础上又进行了改进，提出了BMHS算法[4]。本文对现有几种典型模式算法进行分析，在BMHS算法的基础上进行改进，并进行试验和结果分析。

1 典型算法

1.1 BM算法

BM算法是由Boyer和Moore在1977提出的单模式匹配算法。它是目前实际应用中效率较高的单模式匹配算法之一。BM算法采用从右向左比较的方法，同时应用到了两种启发式规则，即坏字符规则和好后缀规则，来决定向右跳跃的距离。BM 算法中坏字符跳跃表和好后缀跳跃表的设计对提高BM算法效率有至关重要的作用。设文本T（长度为n），模式串P（长度为m）。

⑴ 坏字符跳跃表：当Pk≠Ti，即不匹配情况发生时，若此时Pk是P的末字符且Ti在模式串P中不出现，则下一次比较可以将匹配窗口直接移动m个位置后继续匹配;若Ti在模式串P中出现，则找到Ti在模式串P中出现的最右边的位置j（1≤j≤m-1），匹配窗口移动的距离为m-j（如图1所示）。

图1  坏字符规则

⑵ 好后缀跳跃表： 当Pk≠Ti（k

图2  好后缀规则

在匹配过程中，模式串P与文本T从右向左开始匹配，一旦发现不匹配，取好字符跳转和坏字符跳转之间较大的值作为模式串P的向右跳转距离。最理想的情况是每次匹配时文本T中第一个匹配的字符不存在于模式串P中，此时BM的算法的时间复杂度为O（n/m）;最坏的情况是文本T中有多个重复的字符，并且模式串P由m-1个相同的字符前加一个不同的字符组成，在这种情况下，BM算法的时间复杂度为O（mn）。

1.2 BMH算法

Horspool提出的BMH算法相对于BM算法更容易实现。BMH算法在预处理阶段只使用了坏字符跳跃表，无论文本中哪个字符造成了匹配失败，都将依据坏字符跳转表向右移动。BMH算法的基本思想是：①搜索文本时，从头到尾搜索，匹配时从右向左匹配。首先比较文本指针所指字符和模式串的最后一个字符，如果相等，再比较其余m-1个字符，无论文本中哪个字符造成了匹配失败，都将由文本中和模式串最后一个位置对应的字符来启发模式串向右移动，即当匹配开始比较TiTi+1…Ti+m-1和P0P1…Pm-1时，一旦发生不匹配，计算跳转距离skip（Ti+m-1），跳转后将模式串和文本对齐后重新匹配。②如果与P完全匹配，返回在T中对应的位置;③如果搜索完T仍然找不到完全匹配的位置，则查找失败[3]（如图3所示）。坏字符跳转计算公式：

图3  BMH算法

如图3所示，当文本中的与T2（‘d）与模式串P中的P2（‘c）发生不匹配时，计算跳转距离skip（T4），可以看出P1与T4相等，模式串P向右移动3个字符，即skip（T4）等于3，然后将P1与T4对齐后重新匹配。

BMH算法简化了初始化过程，匹配过程中的判断过程也作了简化，因为BMH算法只采用了BM算法的坏字符移动规则，并且将失配情况与偏移量的计算独立，不关心文本串中哪个字符造成了失配，只考虑用于模式串最右端对齐的文本字符来决定偏移量。该算法的理论时间复杂度与BM算法一致，但实际使用情况下较BM算法效率高。

1.3 BMHS算法

BMHS算法在BMH算法的基础上作了进一步改进，该算法的主要思想是：当开始匹配TiTi+1…Ti+m-1和P0P1…Pm-1时，若发生不匹配，考虑下一个字节的情况，即利用下一个字符Ti+m决定右移量。当下一个字符Ti+m不在模式串P中出现时，它的右移量比BMH算法的右移量大，跳过m+1个字符。通常情况下，BMHS算法比BMH算法快，但当Ti+m-1不在模式中出现，而Ti+m出现在模式串中时， BMHS算法[4]的效果就不如BMH算法[3]。匹配过程如图4。BMHS算法的跳转距离计算公式为：

图4  BMHS算法

如图4所示，当Ti+m出现在模式串P中时，如图4（a），将模式串P中的字符‘e与Ti+m对齐;当Ti+m不存在于模式串P中时，如图4（b）所示，模式串P向右移动m+1个字符;而图4（c）中当Ti+m存在于模式串P中，而Ti+m-1不存在于模式串P中时，skip（Ti+m-1）等于5，而skip（Ti+m）等于1，Ti+m-1的跳转距离大于Ti+m的跳转距离，若还使用Ti+m为标准，则会降低匹配效率。在BMHS算法中最理想的时间复杂度为O（n/m+1）。

1.4 对各算法的已有改进

在模式匹配中存在两个基本定理：任何字符串匹配算法的最坏情况下必须检查至少n-m+1个文本中的字符;任何字符串匹配算法至少检查n/m个字符[5]。因此，没有一个算法比BM算法有更好的计算复杂度，但是我们可以通过改进来减少比较次数，提高匹配的平均性能。

基于以上三种模式匹配算法，近些年已经有多种改进算法。例如，利用统计字符在模式串中出现的频率来实现跳转[6];利用双字节计算偏移量[7-9];通过模式串P和文本T之间的关系来实现跳转[10];利用已匹配成功的字符串来进行跳转[11]，以及从模式串两端向中间匹配的方式[12]来改进模式匹配算法等。以上算法虽然减小了匹配次数，但相应增加了匹配的时间。接下来详细介绍一种通过双字节来计算偏移量的模式匹配改进算法。

2012年袁静波提出了一种改进的BMHS模式匹配算法[8]。该算法在BMHS算法的基础上利用文本T中与模式串P最后一个字符对应的字符Ti+m-1，以及Ti+m和Ti+m+1来实现跳转，模式串P和文本T从右向左匹配。以下是具体匹配过程。

第一步：当文本T和模式串P发生失配时，首先判断Ti+m是否在模式串中，若不存在直接跳过m+1的距离，如图5所示，文本T中的T4（‘d）不在模式串P中，则模式串P向右移动m+1个字符。

图5  Ti+m不在模式串P中

第二步：当Ti+m在模式串中时，判断子串Ti+m Ti+m+1是否在模式串P中，若不存在，则跳过m+2的距离，如图6，子串“be”不在模式串P中，则模式串向右跳转m+2个字符。

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

第三步：若模式串包含Ti+m Ti+m+1，则比较子串Ti+m-1Ti+m是否存在于模式串P中，不存在的话跳转m+1个字符，如图7，子串Ti+m Ti+m+1（“be”）存在与模式串P中，而子串Ti+m-1 Ti+m（“gb”）不存在与模式串P中，则模式串P向右跳转m+1个字符。

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

第四步：若Ti+m Ti+m+1和Ti+m-1 Ti+m都存在于模式串中，则取两者之间匹配的最大值进行跳转，如图8，可以看出，子串Ti+m Ti+m+1（“ea”）的跳转距离为2，子串Ti+m-1 Ti+m（“ae”）的跳转距离为3，取跳转距离较大的值，则模式串P应向右跳转3个字符。

图8  比较得到较大值进行跳转

在该改进算法中，模式串P最大的跳转距离为m+2，在理想的情况下该算法的时间复杂度为O（n/m+2）。

2 DBMHS算法

2.1 基本思想

通过观察BM，BMH和BMHS算法的匹配过程可以发现，这些算法在匹配窗口的首字符匹配均失败时效率最优。本文提出的DBMHS算法通过比较模式串P的第一个字符P0的跳转距离jump（P1）和在T中与模式串P最后一个字符对应的后一个字符Ti+m的跳转距离jump（Ti+m）来移动模式串P。跳转距离公式如下：

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

显然，提高首字符匹配失败的概率是提高算法效率的关键之一。改进的DBMHS算法结合了BMHS算法特点，首先模式串P与文本T左端对齐，从右向左开始匹配，先检测T中与模式串最后一个字符相对应的字符Ti+m-1是否在模式串P中，若Ti+m-1不在模式串P中出现，则检测后一个字节Ti+m是否存在于模式串P中，若Ti+m不在模式串P中出现，则模式串P可以向右移动最大的距离m+1，否则移动距离为m。如图9、图10所示。

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

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

若Ti+m-1与模式串P中对应的字符相匹配，则接着匹配余下的字符，一旦发生不匹配的情况，则检测Ti+m是否存在于模式串P中，若不存在，则模式串P直接向右移动m+1的距离，若存在则计算Ti+m的跳转距离，然后计算模式串P中第一个字符P0的跳转距离，比较这两个跳转距离，选择较大的跳转距离作为模式串P的实际跳转距离。从图11可以看出，若使用Ti+m进行跳转，则模式串P的跳转距离为1，若使用模式串P的第一个字符P0进行跳转，则模式串的跳转距离为2，通过比较，使用P0的跳转距离可以使模式串P尽量的向右移动。需要注意的是，若模式串P或文本T中同一个字符出现多次，在计算跳转距离时，需分情况处理，例如，若匹配Ti+m时，P中出现多个与Ti+m相同的字符，则选择最右端的字符与Ti+m对齐;若是在匹配P0时出现这种情况，则选择T中靠左的字符进行对齐。

图11  P1跳转距离大于Ti+m

若算法在匹配时自右向左均匹配成功，则此时找到一次完全匹配，算法结束。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算法在比较时利用下一个字符Ti+m决定右移量，当Ti+m不在模式串P中出现时会跳转最大的距离m+1，但当Ti+m出现在模式串P中时，由于多进行了一次匹配，BMHS匹配算法的效果就不如BMH算法。因此，DBMHS匹配算法通过模式串两端的字符来充分利用Ti+m。当Ti+m出现在模式串P中时，计算Ti+m的跳转距离，并计算第一个字符P0的跳转距离，通过比较这两个字符的跳转距离来实现更大的跳转，这样不仅提高了Ti+m的利用率，而且获得了更高的匹配效率。

3 算法性能测试

本实验使用的计算机硬件平台为IntelPentium G2020处理器，4G内存，软件平台为Windows 7操作系统，Microsoft Visual Studio 2010集成开发环境。在此环境下分别对BMHS算法、IBMHS算法和DBMHS算法进行测试，IBMHS匹配算法为文献[8]中提出的对BMHS匹配算法的改进算法。

实验随机选取4个不同长度的文本串，实验文本字符集由大小写字母，数字和空格组成。模式串从文本串中随机提取。分别执行BMHS算法、IBMHS算法和DBMHS算法程序，统计不同长度文本串，不同模式串的情况下，算法的执行时间和匹配窗口的移动次数。每个算法分别执行10000次，运行时间取平均值。得到的数据如表2和表3。

表2  匹配窗口移动次数

[文本长度＼&模式串长度＼&BMHS＼&IBMHS＼&DBMHS＼&匹配次数＼&匹配次数＼&匹配次数＼&2481＼&12＼&259＼&183＼&202＼&1138＼&10＼&114＼&90＼&95＼&555＼&14＼&44＼&32＼&35＼&225＼&12＼&16＼&13＼&14＼&]

表3  匹配时间

[文本长度＼&模式串长度＼&BMHS＼&IBMHS＼&DBMHS＼&匹配时间＼&匹配时间＼&匹配时间＼&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可以看出，本文提出的算法相比传统的BMHS算法有较大的改进。例如第一次匹配，DBMHS匹配次数较BMHS减少了约28%，并且文本长度越长，减少的匹配次数就会越多。此外，DBMHS在匹配用时上与传统的BMHS算法比较接近。虽然IBMHS算法的匹配次数少于DBMHS算法，但是匹配时间几乎是DBMHS算法的7倍。从效率上来说，DBMHS算法要优于其他算法。

4 结束语

本文通过分析BM，BMH和BMHS模式匹配算法，提出了一种改进的算法DBMHS。由于DBMHS算法充分利用了模式串两端字符，通过实验可以证明，该算法的匹配效率得到了显著提升。下一步的研究将考虑该算法应用在多模式匹配中，并利用语言学中的知识，如模式串与文本结构，使其性能更加优越。

参考文献：

[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] 李雪莹，刘宝旭等.字符串匹配技术研究[J].计算机工程，2004.30

（22）：24226

[6] 刘胜飞，张云泉.一种改进的BMH模式匹配算法[J].计算机科学，

2008.35（11）：164-165

[7] 姚保峰，王磊.一种改进的BMH模式匹配算法[J].湖南工程学院学报：

自然科学版，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] 王浩，张霖.基于坏字符序检测的快速模式匹配算法[J].计算机应用

与软件，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