|
一种基于BMH 算法的模式匹配算法
陈杰*
作者简介：陈杰，（1986-），男，硕士研究生，主要研究方向：通信系统. E-mail: chenjie236@sina.com
（北京邮电大学信息与通信工程学院，北京 100876）
5 摘要：在介绍两种常用的单模式匹配算法BM 算法和BMH 算法的基础上，分析其改进的思路，
重点分析BMH 算法，并对BMH 算法进行了改进，主要针对模式串的特点减少匹配次数有效地
提升BMH 算法的性能。并且通过测试程序首先比较分析BM 算法、BMH 算法和文中改进算法
在对同一文档同一模式串情况下的性能，其次主要分析比较BMH 算法和改进算法在不同长度
模式串情况下的性能，实验结果能很好的证明文中改进算法在模式串长度较长的情况下有更
10 高的效率。
关键词：BM 算法；BMH 算法；模式匹配
中图分类号：TP309
0 引言
字符串的模式匹配用于定位模式串的位置，是一种重要的字符串运算。模式匹配广泛的
应用于入侵检测系统以及文本查找中。对于给定的长度为n 的文本串T=T0,T1,T3……Tn 和
长度为m的模式串P=P1,P2,P3……Pm，在T 中查找模式串P 首次出现的位置称为模式匹配。
30 简单的模式匹配算法是BF 算法，其基本思想是，从文本串开始位置逐个字节进行匹配。
算法的时间复杂度是O(n*m)，算法虽然简单但是是一种效率极低的算法。
KMP 算法作为一种对BF 算法的改进算法，其基本思想是：在某趟Ti 和Pj 匹配失败后，
i 的位置不回溯，模式P 滑动到某个位置，使Pk 对准Ti 继续向右匹配。算法的关键部分在
于P 滑动距离的函数定义。KMP 算法将模式串向右滑动提高了匹配效率，但相对比较复杂，
35 其时间复杂度为O(n+m)。Boyer 和Moore 在KMP 算法思想的启发下，提出了一种效率更高
的模式匹配算法——BM 算法。
1 BM 算法
BM 算法的基本思想是模式串从右向左与文本串进行匹配，一旦不匹配则根据模式串生
成的坏字符表和好后缀表进行跳转继续进行匹配[1]。其中，坏字符表和好后缀表是由模式串
40 决定的。
（1）坏字符表
在匹配从右向左扫描过程中，若发现某个字符c 不匹配，及出现坏字符，则根据此坏字
符在模式串中出现的情况来进行对模式串的跳转。坏字符表定义如公式(1)[2]：
45 其中，p[j]代表模式串的第j 个字节，c 表示字符c 不在模式
串P 中出现。另一种情况是字符c 在模式串P 中出现，且max(c)表示字符c 在模式串P
中出现的最右的位置。
（2）好后缀表
当某个字符不匹配的同时已经有部分字符已经匹配，及后缀已匹配，则可以利用匹配的
50 后缀结合模式串特点来进行对模式串的跳转。好后缀的思想是，当模式串后部与文本串匹配
的一部分中，有一部分在模式串中其他地方出现，则可将模式串向右移动，直接使这部分对
齐，而且要求这部分尽可能大。具体有以下两种情况[3]：
a. 模式串P 中某一子串P[j-s+1]…P[m-s-1]与已经比较部分P[j+1]…P[m-1] 相同，则可
以让P 右移s 位；
55 b. 模式串P 已经匹配部分P[j+1]…P[m-1]的后缀P[s]…P[m-1]与P 的前缀P[0]…P[m-s-1]
相同，则可让P 右移s 位。
满足上述两种情况的s 的最小值为最佳右移距离，好后缀表定义如公式(2)
以测试中用到的模式串amounts 为例给出其坏字符表和好后缀表如表2-1 所示：
60
表2-1 坏字符表和好后缀表
j 0 1 2 3 4 5 6
字符 a m o u n t s others
skip 6 5 4 3 2 1 0 7
shift 13 12 11 10 9 8 1
当匹配到某个字符，Ti 和Pj 失配时。取skip[Ti]和shift[j]的较大值及为下一趟匹配的跳
转距离。BM 算法在最坏的情况下匹配时间复杂度为O(n*m)，最好的情况下时间复杂度为
65 O(n/m)。
关于坏字符表和好后缀的使用对比，研究表明[4]，坏字符表在匹配过程中占主导作用的
概率为94.03%，远远高于好后缀表的使用。同时相对来说好后缀表的计算过程相对复杂，
因此更多改进BM 算法都基于省去好后缀表的计算，并且省去了比较坏字符和好后缀的过
程，Horspool 于1980 年发表了改进与简化BM 算法的论文[5]，即BMH 算法。
70 2 BMH 算法
BMH 算法在移动模式串是仅考虑坏字符表。它首先比较文本指针所指字符和模式串的
最后一个字符，如果相等再比较其余m-1 个字符。无论文本中哪个字符造成了失配，都将
由文本中和模式串最后一个位置对应的字符来启发模式向右移动。
BMH 算法的基本思路为：
75 从文本串Ti=Tm-1 开始，
(1) 查坏字符表，若skip[Ti]=0，则尾字符匹配，执行(3)，若尾字符不匹配则执行(2)；
(2) 向右滑动模式串，i+=skip[Ti]，跳回(1)；
(3) 从i-1 开始匹配模式串，若都匹配，则返回，若不匹配则i++，跳回(1)；
例如，文本串T=”abdacbacdbcacabcac”，模式串P=”abcac”，根据模式串计算的坏字符
80 表如表2 所示，BMH 算法的匹配过程如表2-1 所示：
表 1-1 "abcac"的坏字符表
字符 a b c others
skip 1 3 0 5
表 2-2 BMH 算法匹配过程
匹配开始，第一次匹配，m=5，T4=c，skip[c]=0，尾字符匹配，向左继续匹配，出现失
配模式串向右滑动一个字节；第二次匹配，继续比较T5=b，skip[b]=3，模式串滑动3 个字
节；第三次匹配，T8=d，skip[d]=5，模式串向右滑动5 个字节；第4 次匹配，T14=a，skip[a]=1，
模式串向右移动1 个字节；第5 次匹配，T15=b，skip[b]=3，模式串向右滑动3 个字节；第
90 6 此匹配，为字符匹配，且字符串匹配，返回结果。
比较上述BMH 算法的匹配与BM 算法的匹配，比较次数有所减少，因此匹配效率提高，
并且只用了坏字符表，而摒弃了好后缀表。
在模式匹配中存在两个基本定理：任何字符串匹配算法最坏情况下必须检查至少n-m+1
个文本中的字符；任何字符串匹配算法至少要检查n/m 个字符[3]。因此没有哪一种算法会比
95 BM 算法有更好的时间复杂度，因此BMH 算法从减少比较次数来提高BM 算法的性能。
3 一种改进的算法
经过对BM 算法以及BMH 算法的分析和实际应用的测试，提出BMH 的改进思路，加
入了对模式串特点的分析，在实际应用中，多数情况匹配的模式串是一个英文单词，而英文
单词有相同后缀的概率会比较高，因此改进的算法在继承BMH 算法从右向左比较和只考虑
100 坏字符表的思想的基础上做了改进，在匹配过程中，只匹配模式串的尾字符，如果尾字符已
经匹配，不继续匹配尾字符之前的一个字符而去匹配模式串的首字符，若首字符也匹配再去
逐字节匹配中间的字符。在进行匹配之前结合了BMH 算法查找尾字符的思想，在不匹配出
现时查找下一个尾字符匹配的位置。
改进算法的伪代码如下所示：其坏字符表的计算与上述BM 算法相同。
105 从文本串Ti=Tm-1 开始，
(1) 查坏字符表，若skip[Ti]=0，则尾字符匹配，执行(3)，若尾字符不匹配则执行(2)；
(2) 向右滑动模式串，i+=skip[Ti]，跳回(1)；
(3) 匹配T[i-m+1](首字符)和P[0]，若匹配执行(4)，若不匹配则i++，跳回(1)；
(4) 匹配T[i-m+2]…T[i-1]，若匹配则返回结果，若不匹配i++，跳回(1)。
110 此改进算法，在时间复杂度上与BMH 算法相同，而且模式串滑动次数也和BMH 算法
相同，但是，改进算法在一定概率上减少了BMH 算法的比较次数，因此一定程度上提升了
匹配的性能，匹配效率上，经过测试比较BMH 算法略有提升。
改进BM 算法实现流程如图3-1 所示。
115 图 3-1 改进算法基本流程
4 三种模式匹配算法比较分析
上文对BM 算法，BMH 算法以及改进的BM 算法进行了简单介绍。下面为对三种模式
匹配算法在实际匹配过程中性能的比较，比较的主要参数是匹配某个文本中的一个模式串所
120 消耗的时间。实验平台是windows XP 操作系统，开发工具是Microsoft Visual Studio2008。
其中BMH算法摘自snort 源码，版本为2.9.0.5。计算时间消耗利用QueryPerformanceCounter()
函数来获取计数器的值再通过时钟频率计算时间，可以精确到微秒。
表4-1 和表4-2 为BMH 算法和改进算法详细的匹配过程。从表中可以看出，改进算法
相对于BMH 算法在匹配表中文本串时，减少了比较次数。其滑动的距离是相同的。其原因
125 在于文本串中出现了后缀相同的单词，改进算法很好的避开了这种情况，所以减少了比较次
数，而在比较大的文档中，这种情况通常是比较多见的。
从理论上比较分析BM 算法，BMH 算法和改进算法，首先，BM 中好后缀表的预处理
较困难，占用大量的运算时间，而BMH 算法和改进算法并未使用好后缀表，此为优势之一。
其次，三种算法大部分比较在于模式串最后一个字节与文本串的比较，BM 算法的操作过程
130 分三步，检查尾字符是否匹配，查好后缀表和坏字符表。而BMH 算法和改进算法只用了一
步操作，及查坏字符表。省略了两步操作改进了匹配效率。最后，在尾字符匹配后，前m-1
个字符发生失配的情况也比较普遍，BM 算法根据失配的字符决定滑动距离，而BMH 算法
和改进算法根据尾字符的下一个字符决定滑动距离，原因在于发生失配后，模式串肯定要向
右滑动，而最少的滑动为一个字符，因此可以直接先滑动一个字节再决定是否继续滑动[6]。
135 接下来，通过实验从时间消耗角度对三种算法进行详细比较。
表 4-1 BMH 算法匹配过程
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 24 28
c l i e n t s a r e p r i v y t o l a r g e a m o u n t s
a m o u n t s
a m o u n t s
a m o u n t s
a m o u n t s
a m o u n t s
140
表 4-2 改进算法匹配过程
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 24 28
c l i e n t s a r e p r i v y t o l a r g e a m o u n t s
a m o u n t s
a m o u n t s
a m o u n t s
a m o u n t s
a m o u n t s
首先，考虑了对同一个文档，同一个模式串三种算法的耗时比较，分别重复匹配文档
100 次统计数据，并对数据进行处理，排除操作系统等外界因素的干扰，然后根据实验结果
145 绘制图表。如下表4-3 和图4-1。
表4-3 RFC2616 文档匹配比较
匹配算法 BM BMH 改进算法
匹配文档 RFC2616.txt
文档大小 423KB
模式串 Acknowledge
重复次数 50
总耗时（毫秒） 60.27 33.66 31.5
平均耗时（毫秒） 1.21 0.67 0.63
原创学术论文网Tag：职称论文发表 代发论文 代写代发论文 计算机论文 代写工科论文
|
