对Horspool算法的改进

曹海锋 张维琪

摘  要：文章分析BM及其改进的Horspool和Sunday算法，在此基础上提出了Horspool的改进算法。该算法利用当前窗口的下一个字符信息以及当前窗口最后一个字符和文本字符不匹配这个事实，增大右移量，减少了匹配次数。实验结果表明，该算法比原有算法具有更高的效率。

关键词：串匹配;BM算法;Horspool算法;改进的Horspool算法

中图分类号：TP301     文献标识码：A      文章编号：1006-8937（2015）05-0046-03

目前，计算机通信网络在社会生活各方面的作用日益增大。社会对计算机网络的依赖也日益增强。随着网络技术在各行业中的广泛应用以及Internet的飞速发展，日益严重的网络安全问题已经引起了人们的高度重视。黑客、网络间谍、网络病毒等严重威胁着计算机网络的安全。为了抵御网络攻击，人们采用网络安全技术来保护其内部网络的数据资料，其中应用最广泛的是入侵检测系统（Intrusion Detection Systems：IDS）。

作为网络内容安全检查的重要技术，字符串匹配算法被广泛的应用在入侵检测、入侵保护、网络防病毒和网络内容监控等网络安全系统中。字符串匹配是网络安全系统中对计算资源要求最高的部分，据统计，在常用的入侵检测系统（IDS）SNORT中，70%的执行时间和80%程序的指令都用在特征串的匹配上：大约有30%的网络问题是由于安全系统中数据包过滤效率低下造成的。随着网络带宽的不断增加，入侵检测规则的持续增长，包过滤的效率已无法满足网络数据传输的需求，模式匹配正在成为网络入侵检测系统的性能瓶颈。因此提高串匹配效率对提高IDS的过滤能力至关重要。

1  现有串匹配算法的分析

串匹配就是在已知文本集合T中找出一个或者多个模式串P的所有出现。目前针对精确模式匹配算法已有40多年的研究，产生出了上百种模式匹配算法，其中最基本也最经典的是KMP算法和BM算法，这两种算法奠定了以后许多算法的基础，通常情况下BM算法的搜索速度是KMP算法的3-5倍。随后产生出对BM算法改进的Horspool算法和Sunday算法，这两种算法在大多数情况下都比BM算法具有更好的性能。

1.1  BM算法

Boyer和Moore两人在KMP算法的基础上，设计出的一种快速单模式匹配算法BM（Boyer-Moore）算法。BM算法进行模式匹配时，模式P沿着文本T从左到右移动，字符比较却从右至左进行，在每次比较失败后通过两种方式来决定下一次匹配动作匹配窗口的开始位置：好后缀转移机制和不良字符转移机制。

BM算法在当前窗口从右向左匹配过程中，设已读入字符串U，且已经匹配，即U是模式的后缀，也是文本在搜索窗口的后缀，此时再读入一个字符n后发生失配，此时用下面两种机制中滑动距离最远者来决定搜索窗口的右移距离。

1.1.1  好后缀转移机制

好后缀转移表的计算公式如下：

gs_shift[j]=

若已经匹配的后缀U在模式P中出现不止一次，则将搜索窗口向右滑动使将模式串U在其左边的第二次出现位置与文本串的U对齐，继续进行匹配。如图1所示。

若U在模式串中没有出现，但U的某个后缀恰好是模式P的前缀，设v为满足此条件的最长后缀，则滑动搜索窗口时文本串中U的最长后缀v与模式串的前缀对齐，继续进行匹配，如图2所示。

1.1.2  坏字符转移机制

坏字符转移表的计算公式如下：

bc_skip[x]=

如果从右向左匹配过程中，匹配到模式串的字符n时发现不匹配，假设字符n对应的文本中的字符是m，若m在P中出现，则将模式串向右移动使之与文本串中的m对齐，继续进行匹配，如图3所示。

如果m在P中未出现，则直接将模式串滑动到文本串中字符m的后面，继续进行匹配，如图4所示。

该算法由于存在比较坏字符和好后缀的环节，而在大多数情况下好后缀出现的情况很小，故影响了匹配效率。

1.2  Horspool算法

Horspool算法是对BM算法的一个简化，该算法在移动模式时仅使用坏字符启发规则。计算指针移动距离时首先判断窗口的最右字符与对应文本字符是否相等，將最右的字符t[i+m-1]与P[0…m-2]与最右面的相应出现对齐，如果P[0…m-2]中不存在t[i+m-1]字符，则滑动整个窗口。

和BM算法相比，Horspool只使用了一个数组，简化了初始化的过程，省去了比较坏字符和好后缀的步骤，在一般情况下比BM算法具有更好的性能。但由于该算法只是利用窗口的最后一个字符进行坏字符跳跃，故跳跃距离最大只能是窗口的长度m。

1.3  Sunday算法

Sunday算法也叫Quick Search算法，是BM算法的一个简化，同样只使用坏字符策略。在搜索阶段模式和文本字符的比较可以以任意的顺序进行，当发现不匹配时，通过紧跟在当前窗口之后的第一个字符t[s+m]来计算移动距离。虽然该算法具有最坏的平方级的时间复杂度，但在实际应用中对于短的模式串和大字母表的情况下非常快。

目前，针对上面三种经典的算法已有很多改进的算法，以适应不同的应用，如FJS算法、BMG算法EPSM算法等，但由于其实现都比较复杂，并不能显著的提高串匹配的效率。

2  改进的Horspool算法

通过对Horspool的分析与应用，受到Sunday算法的启发，本文提出了Horspool算法的改进思路：对于每次尝试，模式与当前窗口从右向左进行比较，当且仅当第一个字符不匹配时，即

p[m-1]t[s+m-1]，

使用壞字符规则计算移动增量，此时坏字符是模式串最后一个字符对应的文本字符;当第一个字符匹配并且该窗口匹配失败时，同样使用坏字符计算移动增量，改进在于此时的坏字符是模式串最后一个字符对应的文本字符的下一个字符。算法的具体描述如下：该算法的预处理阶段主要是初始化位置移动表——ihBc1表和ihBc2表。

设待匹配文本所在字符集的大小为ASIZE，该初始化程序的代码如下，该代码给出了ihBc1表的初始化方法，ihBc2表的初始化与其类似，差别在于表中的每一项均比ihBc1少1。

void preih1（char *x， int m， int ihBc1[]） {

int i;

for （i = 0; i < ASIZE; ++i）

ihBc1[i] = m + 1;

for （i = 0; i < m; ++i）

ihBc1[x[i]] = m- i;}

全文扫描阶段开始时，将文本串T与模式串P左对齐，从右向左逐个字符进行比较，当匹配失败的字符是窗口最右边的字符时，查询表ihBc2进行跳转，当匹配失败的字符不是窗口最右边的那个字符时，查询表ihBc1进行跳转。匹配流程如图5所示。

该改进算法的一个匹配实例见表1。

3  实验结果及分析

Horspool算法与改进后的Horspool算法的程序结构基本相同，时间复杂度和空间复杂度也基本一样，但由于其考虑的Horspool算法在失配时的位置，因此在实际中具有更高的效率。为了测试算法的性能，作者通过程序生成了128 M随机文本，并且将1 000个不同长度的模式分别播撒在该文本中，对BM、Horspool、Sunday、改进的Horspool算法进行测试，测试结果见表2。在windows环境下，可以通过QueryPerformanceCounter函数获得高精度的性能计数器，QueryPerformanceCounter可以获得CPU内部的计数器的值，这个计数器的值的精度非常高，能够达到一秒钟增加几百万的计数。

从表2中以看出，在随机纯英文文本上改进的Horspool算法的匹配时间平均比未改进的Horspool算法减少了15%，在匹配时间上较原来的Horspool算法有了明显提高。

4  结  语

改进的Horspool算法结合了Horspool算法与Sunday算法的优点，在匹配过程中，充分利用当前窗口的最后一个字符与文本不匹配和在匹配失败时窗口至少要移动一个字符这两条信息，使得该算法在实际应用中具有很好的性能。实验结果表明，Horspool算法显著提高了字符串匹配的效率，缩短了匹配时间，具有广阔的应用前景。

参考文献：

[1] Knuth D E，Morris J H，Pratt V R.Fast pattern matching in strings[J]. SIAM journal on computing，1977，（2）.

[2] Boyer R S，Moore J S.A fast string searching algorithm[J].Communica-

tions of the ACM，1977，（10）.

[3] Horspool R N.Practical fast searching in strings[J].Software：Practice and Experience，1980，（6）.

[4] Sunday D M.A very fast substring search algorithm[J].Communications of the ACM，1990，（8）.

[5] Franek F，Jennings C G，Smyth W F.A simple fast hybrid pattern-

matching algoritm[J].Journal of Discrete Algorithms，2007，（5）.

[6] 张娜，侯整风.一种快速的BM模式匹配改进算法[J].合肥工业大学学报：自然科学版，2006，（7）.

[7] Faro S and Kulekci M O.Fast Packed String Matching for Short Patterns.Meeting on Algorithm Engineering and Experiments[J]，ALE-

NEX，2013，（2013）.