BM算法中函数shift的研究

开篇：润墨网以专业的文秘视角，为您筛选了一篇BM算法中函数shift的研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要：建立bm算法中函数shift及其构造算法的严格的形式理论，对于BM算法及其各种变形的研究与改进是十分必要的。给出了shift的一个清晰的形式定义，引入模式串后缀的特征集及其最小值函数，通过特征集描述了shift的构造，从而严格建立了shift及其构造算法的理论基础。根据shift的构造定理与最小值函数的迭代计算方法，给出了shift的一个新的构造算法，证明了该算法具有线性的时间与空间复杂度。理论分析和计算结果表明，该算法比已有算法更简单，计算复杂度更低，因而更适合硬件实现。

关键词：串匹配；BM算法；好后缀规则；shift函数；复杂度分析

中图分类号： TP301.6

文献标志码：A

0 引言

串匹配是指在文本串中查找模式串的第一次出现或所有出现。串匹配算法在文本检索、语言翻译、数据压缩、搜索引擎等应用中起着关键作用。近年来，在病毒检测、网络入侵检测、网络协议识别、计算生物等领域也都大量应用了串匹配技术。因此，串匹配算法一直是计算机科学领域的研究焦点之一。

根据扫描策略的不同，已有的精确串匹配算法大致可以分为三类：1）自左向右匹配窗口中文本串与模式串的最大前缀，具有线性的最差时间复杂度；2）自右向左匹配窗口中文本串与模式串的最大后缀，具有亚线性的平均时间复杂度；3）自右向左匹配窗口中文本串与模式串的最大子串，也具有亚线性的平均时间复杂度，甚至能达到最优平均时间复杂度。

BM（BoyerMoore）算法[1]是最早的第二类算法。在BM算法的各种变形[2-5]中，Horspool算法、Sunday算法是BM算法的简化；CommentzWalter算法是BM算法在多模式匹配的推广，SetHorspool算法是Horspool算法在多模式匹配的推广；WuManber算法则是SetHorspool算法的一个改进。

BM算法及其各种变形一直被认为是实际应用中最有效的串匹配算法。例如，开源入侵检测系统Snort就是采用BM算法，在监听到的数据中匹配系统的安全规则，根据发现的入侵情况采取相应的安全措施。

BM算法通过两个预先计算好的函数来确定下一个窗口的起始位置，本文中，这两个函数分别记为skip与shift。其中，skip十分简洁且容易计算，在大字母表、小模式串的情形具有很高的效率；然而，shift的计算却远比skip困难得多。1977年，Boyer与Moore在1975年最初定义的基础上，给出了shift的一个改进了的定义，但没有给出构造算法。同年，Knuth等[6]也给出了一个定义并描述了构造算法，但没有详述计算方法，其算法也不完全正确。1980年，Rytter[7]完善了Knuth等的构造算法，但没有给出计算方法的严格的形式证明。因此，Hume等[8]指出shift的构造算法难以理解，Horspool甚至认为shift并不真正实用，这也正是Horspool算法中仅保留并改进了skip而去掉了shift的原因。近年来，对BM算法的各种改进也主要是针对skip的改进[9-11]。

其实，shift保证了BM算法在最坏情况下是线性时间复杂度[6，12-13]，这在小字母表情形（例如基因序列匹配和蛋白质序列匹配）以及模式串与文本串相似度较大的情形[14]是非常重要的。随着串匹配技术应用领域的不断扩大和理论研究的不断深入，研究人员逐渐开始关注串匹配算法应用环境因素及其之间的关系，尤其是模式串与文本串之间的关系；在网络内容安全方面，也开始关注串匹配算法的抗攻击性能。现在看来，仅仅根据传统文本检索的实验结果，并不足以低估shift的作用。所以，建立shift及其构造算法的严格、清晰的形式理论，对于BM算法及其各种变形的研究与改进是十分必要的。

2009年，Yang[15]试图通过一个新的辅助数组suffixLength计算shift并给出了形式证明，但辅助数组suffixLength既不如Knuth所引入的辅助数组直观，而且证明过程也非常冗长复杂。

本文给出了shift及其计算方法的严格、清晰的形式表述和数学证明，并在此基础上给出了shift的一个新的构造算法。

6 结语

本文首先分析了BM算法中函数shift的经典定义，给出了shift及其计算方法的严格、清晰的形式表述和数学证明；在此基础上，给出了shift的一个新的构造算法，证明了其时间复杂度与空间复杂度均为O（m）。

值得注意的是，随着串匹配技术应用领域的不断扩大，基于软件的实现已经不能充分满足对匹配速度日益增长的需求，因此，基于硬件的实现逐渐出现，并成为当前的研究热点。理论分析与计算结果表明，本文给出的shift构造算法比已有的算法更简单，计算复杂度更低，从而更适合硬件实现。

BM算法及其各种变形的平均时间复杂度仍然是一个尚未完全解决的问题。目前的研究结果主要集中在没有shift的Horspool算法，最近的结果有：在文本字符相互独立且同分布的假设下，Mahmoud等[16]证明了Horspool算法的平均时间复杂度是渐进正态的，Smythe[17]应用Markov链理论也得到了这一结果。至于BM算法，shift使得算法分析变得更加复杂，虽然Boyer与Moore证明了是亚线性的，但其概率模型有待商榷。因此，BM类算法的平均时间复杂度有待进一步研究。

参考文献：

[1]BOYER R S， MOORE J S. A fast string searching algorithm [J]. Communications of the ACM， 1977， 20（10）： 762-772.

[2]HORSPOOL R N. Practical fast searching in strings [J]. Software Practice and Experience， 1980， 10（6）： 501-506.

[3]SUNDAY D M. A very fast substring search algorithm [J]. Communications of the ACM， 1990， 33（8）： 132-142.

[4]COMMENTZWALTER B. A string matching algorithm fast on the average [C]// Proceedings of the 6th Colloquium， on Automata， Languages and Programming， LNCS 71. Berlin： SpringerVerlag， 1979： 118-132.

[5]WU S， MANBER U. A fast algorithm for multipattern searching， TR-94-17 [R]. Tucson： University of Arizona， 1994.

[6]KNUTH D E， MORRIS J H， PRATT V R. Fast pattern matching in strings [J]. SIAM Journal of Computing， 1977， 6（2）： 323-350.

[7]RYTTER W. A correct preprocessing algorithm for BoyerMoore string searching [J]. SIAM Journal of Computing， 1980， 9（3）： 509-512.

[8]HUME A， SUNDAY D M. Fast string searching [J]. Software Practice and Experience， 1991， 21（11）： 1221-1248.

[9]张红梅，范明钰.模式匹配BM算法改进[J]. 计算机应用研究，2009， 26（9）： 3249-3252.

[10]

董明明，巩青歌，张琦.入侵检测系统中模式匹配算法的改进[J]. 计算机应用与软件，2011， 28（5）： 272-274.

[11]王浩，张霖.基于坏字符序检测的快速模式匹配算法[J]. 计算机应用与软件，2012， 29（5）： 114-116.

[12]GUIBAS L J， ODLYZKO A M. A new proof of the linearity of the BoyerMoore string searching algorithm [J]. SIAM Journal of Computing， 1980， 9（4）： 672-682.

[13]COLE R. Tight bounds on the complexity of the BoyerMoore algorithm [J]. SIAM Journal of Computing， 1994， 23（5）： 1075-1091.

[14]刘萍，刘燕兵，郭莉，等.串匹配算法中模式串与文本之间关系的研究[J]. 软件学报，2010， 21（7）： 1503-1514.

[15]YANG W. On the shifttable in BoyerMoores string matching algorithm [J]. International Journal of Digital Content Technology and its Applications， 2009， 3（4）： 10-20

[16]MAHMOUD H M， SMYTHE R T， REGNIER M. Analysis of BoyerMooreHorspool stringmatching heuristic[J]. Random Structures Algorithms， 1997， 10（1/2）： 169-186.

[17]SMYTHE R T. The BoyerMooreHorspool heuristic with Markovian input [J]. Random Structures Algorithms， 2001， 18（2）： 153-163.