一种单字符串精确模式匹配算法

一种单字符串精确模式匹配算法

张静

北京邮电大学网络与交换国家重点实验室，北京（100876）

E-mail：athena1110@gmail.com

摘 要：模式匹配是当今网络中对病毒检测所采用的一般方法，一个好的匹配算法将使得网络性能得到有效提高。文章提出了一种应用于病毒检测系统的新的单字符串精确模式匹配算法，详细介绍了该算法的核心思想，并与当前两种经典的模式匹配算法（KMP算法和BM算法）的性能进行了比较。

关键词：模式匹配, 字符首次匹配算法（CFM），KMP，BM 中图分类号：TP393

1. 引言

KMP[1]算法和BM[2]算法是现今模式匹配中最常见的两种算法，大多数算法都是在此两者基础上进行改进，但是很少有与其思想差异很大的算法。

在网络中进行病毒检测[3]过程中，考虑到入侵的数据包（即文本）只需其内容部分与规则（即模式）进行匹配，且一个数据包的长度是1500字节，除去包头也有上千个字节。但无论多长的数据，都只有有限个字符，而经统计，在网络数据包中，经常出现的不同字符个数一般在60到90之间。

而在BM算法中的“BAD CHARACTER”移动在移动中跳跃是最远的，它利用了在主串中存在而在模式串中不存在的字符实现对主串的跳跃。受其启发，充分利用在计算机中会出现的一百多个字符，提出了“字符首次匹配算法”（CFM：algorithm of Character First Matching）。

2. 算法介绍

2.1.预处理阶段

2.1.1

求Bpattarn

bpattarn[128] 是自定义的数组数据类型，它包括三个成员： Character 记录模式串中出现的字符

Place 每个字符首次出现时在模式串中的位置 Count 每个字符在模式传中出现的次数

规则库中的每一条规则（模式），都对应一个bpattarn[128]，记录相应的信息。每条规则将被加入规则库时，都要对其扫描一遍，求其bpattarn值。为了节省空间，每个模式的bpattarn[128]的信息连同每个模式中出现的次数以及模式串本身都存放在一个文件中，形成规则库。

Bpattarn数组之所以选择128为其长度，一来是因为经过统计，一般数据包中所出现的字符有80多个（将在下一章中列举），另外其ASCⅡ码在0－127之间，为了方便。

以字符串“bpattarn”为例，其bpattarn值分别为

b p a t t a r n 1 2 3 4 5 6 7 8

-1-

http://www.paper.edu.cn

表 1 字符串的bpattarn值

Ch a b n p r t Count 2 1 1 1 1 2 Place 3 1 8 2 7 4 字符串出现l＝6个字符。 2.1.2

排序

在求出bpattarn后，需要对出现的字符进行排序。排序的目的是经可能的增多匹配过程中跳跃的字符数，以加快匹配的速度。

排序采用冒泡排序方法，经排序后，bpattarn[1-l]中依次存放出现次数逐渐增多的l－1个字符信息，但出现次数最多的一个字符要存放于bpattarn[0]中，也就是放在文件相应信息的第一个位置上，其目的是在匹配过程中实现文本与模式串的快速定位。

这是因为，出现次数最少的字符与文本中字符匹配的概率最低，但它一旦匹配，则下面几个字符与文本匹配的概率就会很高，也就是说其准确率比较高；而在模式串中出现次数最多的字符与文本中字符匹配的概率最高，可是当它匹配后，下面几个字符与文本匹配的概率相对会低些，或者说匹配的准确率相对低一些。在这两个对立的矛盾中，选择了以上的排序方式。

2.2.算法思想

字符首次匹配算法的基本思想是：

各字符首次出现的位置以及字符出现次数，形成首1． 求出每个模式串中出现字符数，次匹配的索引串；

2． 索引串与文本进行匹配，用第一个字符定位，根据各字符在模式串中的位置比较其他字符。

3． 如果索引串与本段文本不匹配，则进行下一段的比较；如果索引串与文本比配，则找到相应段，与模式串进行二次匹配。

4． 如果模式串的i个字符的首位置与文本都匹配，而第i＋1个字符的首位置失配，例如图1所示：

textpatterndwogpbqfnropnbnbpattarngbpattarn图1 字符串与模式串示例

首先，字符‘n’先匹配，再‘n’匹配，然后在比较‘p’，此时失配，如图2所示：

1234567101112131415161718192021222324textpatterndwogpbqfnropnbnbpattarngbpattarn↑图2 匹配过程中的失配位置

-2-

http://www.paper.edu.cn

这时，由于文本的第12个字符是‘n’，而且它与模式串中的字符已经匹配，但是在模式串中，与其匹配过的‘n’之前不会再有‘n’，所以下次匹配的位置就可以跳到第13个字符，重新开始匹配过程，由此实现匹配过程中的跳跃。

当然，在匹配过程中，在失配时，应选择尽量远的跳跃位置，在实现过程中，利用一个值max来记录这个最大跳跃间隔，以尽量减少匹配的次数。

3. 性能分析

字符首次匹配算法是与KMP算法和BM算法思想完全不同的匹配算法，虽然在匹配过程中也借鉴了BM算法的某些思想。介于它独特的思想，使得文本与模式串中很少字符进行比较，只要在模式串的重复字符并不是特别多时，它比前两种算法的效率更高。

本算法的预处理过程相对复杂些，但是在人工免疫系统中，匹配的预处理工作是在生成病毒库（模式）或者规则库时就进行的，所以在分析其性能时，不把预处理时间算在里面。

本算法的最大不足就是预处理后的信息需要相对较大的空间存储，这是相对其他两种算法最大的不足，下面将会详细分析其性能。

3.1.时间性能比较

3.1.1

文本生成

介于是理论分析，所以匹配中的文本并未选择网络中的数据包，而是采用一种模拟的方式：随机生成指定名称和容量的文本，作为匹配性能比较中的文本。具体方法如下：

1．输入文件名和容量（单位为兆，因为在文本小于1M时，匹配时间很少，以至于有时机器计算不出来，所以不用于比较），生成空文件并打开以写入字符；

2．将常用的102个字符放入一个数组中；

3．作如下循环：产生一个随机数，并模102（即数组长度）作为随机位数randnum，将数组的第randnum个字符写入文件，直至达到文本所需容量。

要说明的是，这种随机只是一种伪随机，也就是说并不是真正的随机，因为超过一定情况下，这种随机就会形成一种循环，但是由于这对我们的匹配没有什么影响，所以仍采用这种方法。 3.1.2

性能比较

字符首次匹配算法的时间复杂度是O(m+n)，与KMP算法和BM算法具有相同的时间复杂度，。最好的情况下，本算法的时间复杂度是O(l＋m/n)(l是模式串中不同字符的个数)，如图3所示：

12345671011121314151617181920textpatternabbadceawogawotapvwacdca图3 字符串与模式串示例

此时，预处理后的模式串只需与文本的第4，8，12，16，20五个字符比较。

但最坏的情况下，其时间复杂度是O(m*(n+k)),比前两种算法所用时间更长，可是这必须

-3-

http://www.paper.edu.cn

在一种极特殊的情况下，即模式串中所有字符首次出现的位置都与文本中相应子串中字符的首次出现位置都相同，但是主串中没有与模式串相同的子串，这种情况出现几率很小，所以我们这里不去考虑。

在一般情况下，字符首次匹配算法与另外两种算法的时间复杂度在一个数量级，但由于它在匹配过程中，与主串匹配的不是模式串本身，而是模式串中所有不同的字符，所以每次匹配的字符个数都少于其他两种算法，因而其匹配效率更高些。三者匹配时间如下图所示。

图4 三种算法匹配时间总体比较

-4-

http://www.paper.edu.cn

图5 匹配前与每个模式串匹配的时间

从上图可以看出，模式匹配所用时间与文本大小成正比。在相同条件下，无论是与单个模式串匹配，还是匹配的总体时间，都是新算法匹配所用的时间最少，效率更高。

3.2.空间性能比较

虽然新算法的效率比另外两种算法高，但是它是以较大的存储空间为代价的。

首先，在预处理过程中，先要为模式串中不同的字符分配空间， 如上所示的方法生成的文本有102各字符，利用各字符的ASCⅡ码，用三个长为128的数组存放模式串中的字符的处理信息，但是由于模式串的长度都比较小，在本课题中不超过10，所以比较浪费空间。

其次，处理完的信息（包括一个模式串的长度，串中出现的字符及个数，每个字符在模式串中首次出现的位置）需要放在一个文件中，形成病毒库（模式），也就是说新算法在匹配过程中所用的病毒库与另外两种方法所用的不是一个库，这个库的容量将会大很多，特别是在模式串特别短或者几乎没有重复字符的情况下，前者的容量大概是后者的四倍，如果用于人工免疫系统，在病毒库中病毒个数非常大时，将会直接影响系统的性能，这是新算法最大的缺点。

另外，在匹配过程中，还需要将这些信息读入系统，所以还需要一定的空间。 综合来看，如果在系统允许的情况下，即可以分配出一定量空间下，新算法的性能还是优于两外两种算法的，有很高的可行性。

4. 结束语

文章中所提出的“字符首次匹配算法”还有很多不足之处，比如它的空间复杂度相对较高等，还有很多可以改善的地方，但由于时间有限，没来得及对其进行进一步的设计，之后，将针对此算法进行改进，以求尽量减少其匹配的时间。

-5-

http://www.paper.edu.cn

鉴于模式匹配在人工免疫系统中的重要作用，仅仅单模式匹配已经不能满足系统对匹配速度的要求，如何对“字符首次匹配算法”进行改进，生成一个相对效率更高的多模式匹配算法，也将是下一步的工作。

参考文献

[1] 严蔚敏 陈文博. 数据结构. 机械工业出版社, 1990

[2] 李洋, 王康, 谢萍. BM模式匹配改进算法. 计算机应用研究, 2004, 04

[3] 牟永敏, 李美贵, 梁琦. 入侵检测系统中模式匹配算法的研究. 电子学报, 2006, S1

A Accurate Algorithm of Pattern Matching for Single String

Zhang Jing

Key National laboratory of Network and Switching, Beijing University of Posts and

Telecommunications, Beijing (100876)

Abstract

Pattern matching is one of the main methods of virus detection in network now. The performance of a network can be improved greatly with a excellent algorithm of pattern matching. A accurate algorithm of pattern matching for single string is presented in this article, and the central thought of the algorithm is introduced in detail, and the performance of the algorithm is compared by that of two other algorithm of pattern matching(KMP and BM).

Keywords: Pattern Matching; CFM; KMP; BM

-6-