基于字符频率的字符串模式匹配算法的研究

【10】?第35卷?第9期?

2013-09(上)

收稿日期：2013-04-17

基金项目：国家十二五科技支撑计划项目（2012BAH27F05）；广东省自然科学基金项目（S2012020011071）；广东省 战略性新兴产业核心技术攻关项目（2012A010701004）作者简介：巫喜红（1975 -），女，副教授，研究方向为

基于字符频率的字符串模式匹配算法的研究

Research of the string pattern matching algorithm based on characters frequency

巫喜红1，凌 捷2

WU Xi-hong 1，LING Jie 2

(1. 嘉应学院 计算机学院，梅州 514015；2. 广东工业大学 计算机学院，广州 510090)

摘 要：文章分析了经典的BM算法和Sunday算法，根据字符频率的特点提出了一种新的模式匹配算法CFPM。CFPM算法确定模式串中字符频率最低的关键字符后，扫描文本串中该关键字符的位

置并存储，最后根据这些位置信息进行快速地匹配，匹配方式是以关键字符为始点先匹配左部分再匹配右部分。为了验证CFPM算法的性能，在相同的文本串和模式串情况下，从匹配移动次数和匹配的字符个数两方面对CFPM算法进行实验。实验结果证明，由于CFPM算法能够很大限度地跳过坏字符，大大减少了匹配次数和字符比较个数，有效地加快了匹配速度，其效率优于BM、Sunday等算法。

关键词：字符频率；模式匹配；BM算法；Sunday算法

中图分类号：TP393 文献标识码：A

文章编号：1009-0134(2013)09(上)-0010-05Doi：10.3969/j.issn.1009-0134.2013.09(上).01

0 引言

网络带给人们方便的同时也存在安全隐患，而入侵检测系统(IDS)也越来越广泛地应用到网络系统中，因为它是提高网络系统安全性的重要技术之一。目前，许多IDS都是依靠模式匹配技术来进行入侵检测的，但是，在进行入侵检测时，花费在模式匹配上的时间占到整个IDS总处理时间的30%，对于密集型的流量，这一消耗达到80%[1]。因此，模式匹配性能的提高成为解决IDS的关键技术。目前，国内外对于模式匹配算法已有不少的研究成果，比如典型的单模式算法有Brute Force 算法[2]、Knuth-Morris-Pratt(KMP)算法[3]、Byoer-Moore(BM)算法[4]、Sunday算法[5]，多模式算法主要有Aho_Corasick(AC)算法[6]、Wu_Mander算法[7]。这些算法在实际应用中忽略了字符串的特征，没有实际考虑到字符的频率情况，为此，本文提出了利用字符统计特征的算法，在扫描过程中利用某个频率字符去进行匹配，跳过了一系列无用的字符，从而提高匹配速度。

1 几种经典的模式匹配算法

设文本串T =T 0……T n -1，n 为文本串的长度；模式串P=P 0……P m-1，m为模式串的长度，(n>>m)；T和P都建立在有限字符集上，大小为σ。

对于文本串T和模式串P，在T中寻找等于P的子串，如果在T中存在等于P的子串，则称匹配成功，函数值返回为P中第一个字符相等的字符在主串T中的序号，否则称为匹配失败，这个搜索过程就是模式匹配。至于如何在T中寻找等于P的子串，各种算法各显神通，各有各的寻找方法，在此简要介绍4种经典匹配算法。

BF算法[2]是效率最低的算法，从左到右进行匹配。首先将T[1]与P[1]进行比较，若不同，就将T[2]与P[1]进行比较，……，否则从T[2]开始与P[1]进行比较，继续开始下一趟的比较，重复上述过程。

KMP算法是由BF改进后不产生回溯的一种算法，每当匹配过程中出现字符串比较不等时，不