模式匹配算法的分析与研究

余飞

摘要：模式匹配算法是计算机领域的一个重要研究方向，是防火墙系统、安全扫描系统、入侵检测系统等核心技术之一。该文分析了四种经典算法，研究了算法原理，展示了模式匹配算法发展过程，研究表明模式匹配算法具有较高的用途和实用价值。

关键词：模式匹配算法；算法原理；核心技术

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2018）10-0251-02

Abstract： Pattern matching algorithm is an important research field in computer field. It is one of the core technologies of firewall system， security scanning system， intrusion detection system and so on. In this paper， four classical algorithms are analyzed， the algorithm principle is studied， and the development process of pattern matching algorithm is shown. The research shows that pattern matching algorithm has high practical and practical value.

Key words： Pattern matching algorithm； algorithm principle； core technologies

模式匹配算法是网络安全系统的核心技术之一。现在比较流行的网络安全系统包括病毒防护系统，防火墙系统，安全扫描系统，入侵检测系统等等。在病毒防护系统和入侵检测系统中，模式匹配算法能够帮助筛选或识别出病毒程序和入侵操作，在防火墙系统和安全扫描系统中，模式匹配算法可以按照特征库扫描或过滤出符合要求的数据。因此，模式匹配算法是计算机领域的一个重要研究方向。

1 模式匹配算法概述

模式匹配算法具有广泛的使用价值。字符串模式匹配算法可用于对文本的查找与搜索，可用于网络安全中在数据流里对特征值的有效匹配和识别，可用于在生物科学中匹配DNA序列；图像模式匹配算法可用于军事上导航精确打击武器的图像匹配系统；点模式匹配算法可用于无人驾驶的物体识别系统以及安防人脸识别系统等等。这一切都是以经典的模式匹配算法为基础的。

以用途最广的字符串单模式匹配算法为例，模式匹配算法就是指以匹配模式串P[0，1，2，…，m-1]为查找内容，在文本串T[0，1，2，…，n-1]中进行查找的方法。最简单的方法是按顺序将模式串的字符逐一与文本串字符进行比较，直到在文本串中找到与模式串一模一样的字符串，则匹配成功；如果找不到则匹配失败。为了增加匹配的效率，缩短匹配的时间，大多数算法将模式串与文本串的比较次数减少，比较频率降低。

2 字符串模式匹配算法

字符串模式匹配是指对于给定的字符集，判断一个模式串是否在给定的文本串中出现。如果出现次数为0，则称匹配失败；如果出现的次数大于0，则称匹配成功。

设 文本串为T[0，1，2…n-1]，长度为n。

模式串P[0，1，2…m-1]，长度为m。

字符串单模式匹配算法以T[j]与P[0]为比较起始位，按字符顺序将模式串P逐一与文本串T进行比较。若比较到T[j+m-1]与P[m-1]处所有字符均相同，则匹配成功一次；若比较到T[i+j]与P[i]处字符不相同，则匹配失败。比较结束后，模式串P按顺序偏移一位，继续下一轮的比较。

2.1 BF（Brute Force）算法

BF（Brute Force）算法将P[0]与T[0]，P[1]与T[1]，P[2]与T[2]，…，P[m-1]与T[m-1]逐一进行比较。如果全部相同，则匹配成功；如果有一个不相同，匹配模式串P[0，1，2，…，m-1]向右移一位继续比较，即P[0]与T[1]，P[1]与T[2]，P[2]与T[3]，…，P[m-1]与T[m]逐一进行比较。若再不成功，继续右移一位，直到匹配成功或将文本串全部比较完为止。

2.2 KMP（Knuth-Morris-Pratt）算法

BF算法结构简单，容易理解和实现，但模式串要与文本串中的每一个字符反复比较，效率低下[2]。KMP算法对BF算法进行了改进。改进的措施是，当模式串与文本串从左向右按顺序进行匹配，P[j]与T[i]不相同时，则文本串T保持不动，模式串P根据预先定义好的next数组中的next[j]的值，向右滑动一段距离继续比较。

例如，next[j]等于2的话，模式串P向右滑动，使得T[i]与P[2]进行比较。若相等，继续比较T[i+1]与P[3]，直至比较结束全部相同，则找到一个匹配；若不相等，模式串P继续根据next[2]的值向右滑动。如图1所示。

在KMP算法中，next数组的值起到了非常重要的作用，直接影响到了算法的质量。next数组值有三种类型：

（1）next[j]值为-1

当模式串P与文本串T在P[j]和T[i]处失配，next[j]的值为-1，表明模式串P向右滑动，使得P[0]与T[i+1]對齐。

（2）next[j]值为k（1≤k

当模式串P与文本串T在P[j]和T[i]处失配，next[j]的值为k，表明模式串P向右滑动，使得P[k]与T[i]对齐。

（3）next[j]值为0

当模式串P与文本串T在P[j]和T[i]处失配，next[j]的值为k，表明模式串P向右滑动，使得P[0]与T[i]对齐。

2.3 BM（Boyer-Moore）算法

BM算法是由R.S.Boyer，J.S.Moore共同提出的。不同于BF和KMP算法，BM算法是一种全新的算法。近些年产生的模式匹配新算法都是在BM算法的基础上进行的改良，因此BM算法是模式匹配算法中一个非常重要的经典算法。

BM算法的第一个特别之处就在于，在匹配过程中，文本串T不动，模式串P从左向右移动，但是在字符比较的时候，却是自右向左进行的。即先匹配T[j+m-1]和P[m-1]，再比较T[j+m-2]与P[m-2]是否相等……直到比较至T[j]和P[0]处。如果全部相等，则匹配成功。大多数的时候，都会在中间处发现不相等的字符，该处的位置可以认为是T[i+j]，P[i]。这个时候需要调用偏移函数Goodsuffix（好后缀函数）与Badchar（坏字符函数）[3]，若函数Goodsuffix得出偏移的位数大于Badchar，则使用Goodsuffix得出偏移的位数；反之，使用Badchar得出的位数[4]。

Badchar函数：

在T[i+j]与P[i]处失配，则在模式串中寻找与T[i+j]相等的字符P[k]。找到，T[i+j]与模式串中P[k]处对齐；找不到，则T[i+j+1]与P[0]对齐。

Goodsuffix函数：

在P[i]与T[j+i]处失配，但T[j+i]…T[j+m-1]与P[i]…P[m-1]都是匹配的，这些相同的字符串，标记为u。如果u再次出现在模式串P中，并且后缀u的前一个字符不是a，则将模式串P中u前的一个字符与文本串中u前的一个字符对齐。如果文本串T有一个后缀v，与模式串的一个前缀相同，并且是能够匹配的最长的后缀与前缀，则将它们相同的部分对齐。

2.4 BMH（Boyer-Moore-Horspool）算法

BM算法的Badchar函数的应用次数远远大于Goodsuffix函数。因为在模式串P中能找到后缀u的次数非常少，大部分的偏移都在Badchar函数处执行。BMH算法直接删掉了Goodsuffix函数，并对Badchar函数进行了改进[5]。其改进思想是：模式串P与文本串T进行匹配，从右向左比较P[m-1]和T[j+m-1]，若相同则继续比较P[m-2]和T[j+m-2]，…，一直比较至P[0]与T[j]为止。如果都相同，则匹配成功；如果中间发现P[i]与T[j+i]不相等，则分为如下情况：

如果在P[i]与T[j+i]处失配，但T[j+i]…T[j+m-1]与P[i]…P[m-1]都是匹配的，这些相同的字符串，标记为u。在u中，最后一个字符T[j+m-1]，标记为d。如果在模式串P中，除P[m-1]外，还能找到P[k]处值为d。则模式串P向右滑动，让T[j+m-1]与P[k]对齐，并从模式串末端开始，从右向左继续比较[6]。如果除P[m-1]外，在模式串P中，d没有找到。则从模式串末端开始，模式串继续向右滑动m位，从右向左开始新的一轮比较。如图2所示。

3 小结

本文探讨了四种经典的模式匹配算法及其原理和实现过程，包括BF，KMP，BM，BMH算法。早期的BF和KMP算法虽然匹配结果精确，但效率低下。BM算法的出现改变了这种状况，是模式匹配算法发展的里程碑。BMH算法是BM算法的改进算法，进一步提高了匹配效率。

参考文献：

[1] 潘超，杨良怀，龚卫华，古辉，等.模式匹配研究进展[J].计算机系统应用，2010（19）：265-277.

[2] 徐周波，张永超，古天龙，宁黎华.面向入侵检测系统的模式匹配算法研究[J].计算机科学，2017（9）：125-130.

[3] 尹志喜，甄国涌.基于模式匹配的大规模数据分析软件设计与实现[J].计算机系统应用，2010，19（2）：185-188.

[4] 夏念，嵩天.短规则有效的快速多模式匹配算法[J].计算机工程与应用，2017（7）：1-8.

[5] 劉顺江，刘国华，李颍.基于数据源信息语境的复杂模式匹配方法[J].计算机工程与应用，2010，46（9）：120-122.

[6] 单懿慧，蒋玉明，田诗源.面向入侵检测的改进BMHS模式匹配算法[J].计算机工程，2009，35（24）：170-173.