snort算法中的BM模式匹配算法

第26卷第9期2009年9月
计算机应用研究
ApplicationResearchofComputersVol.26No.9Sep.2009
模式匹配BM算法改进
张红梅,范明钰
3
(电子科技大学计算机科学与工程学院,成都610054)
摘 要:研究BM串匹配算法,分析国内外各种改进算法,结合其优缺点,增加对模式串串末字符或坏字符的邻接字符在模式串中的首次出现位置、存在性、惟一性的判断。根据判断的结果对移动距离重新设置,增加模式串移动距离,减少字符重复比较的次数,以提高匹配效率。关键词:串匹配;末字符;坏字符;邻接字符;惟一性;存在性
中图分类号:TP30116 文献标志码:A 文章编号10012doi:10.3969/j.issn.100123695.2009.09.013
Imprstringmatching
Hong2mei,FANMing2yu
(SchoolofCom&UniversityofElectronicScience&TechnologyofChina,Chengdu610054,China)
Abstract:ThispaperresearchedalgorithmforBMstringmatching.Analyzedkindsofimprovedalgorithms.Onthebasisoftheadvantageofthesealgorithms,thefirstposition,judgedtheexistenceandtheuniquenessoftheneighborcharacteroftheendcharacterorthebadcharacterofthestring.Bytheresultofthesejudges,increasedthenewshiftdistance,reducedthetimesofthematch,andenhancedtheefficiencyofstringmatching.
Keywords:stringmatch;endcharacter;badcharacter;neighborcharacter;uniqueness;existence
引言
串匹配是文本挖掘、文献检索、搜索引擎、IP路由查找、模式识别、图像处理以及入侵检测技术等普遍采用的技术策略之一。串匹配算法是系统性能改进中极为重要的部分,系统性能的好坏取决于匹配算法及其实现的效率。学者们已提出大量串匹配算法,如Knuth等人
[1]
1
算法及其相关改进算法
算法原理
BM算法设置如下初始条件:
正文串T={T[0],T[1],T[2],…,T[n]}模式串P={P[0],P[1],P[2],…,P[m]}字符集Σa,b,…,其中:n>m,需要从T中查找出与P完全匹配的子串,并返回该子串在正文串的首字符的位置。
BM算法原理如下:在正文串T第i个位置开始与模式串P第0个位置对齐,从右往左进行比较。首先比较模式串P末
构造出KMP算法,Boyer等人
[2]
于1977年设计出BM算法。在这些常用的字符串匹配算法中,KMP和BM算法是其中较为著名的两种算法。这两种算法在最坏情况下均具有线性的查找时间,KMP算法匹配从左向右进行,移动距离不可能大于一次匹配操作所进行的字符比较次数;而BM算法匹配从右向左进行,当模式串P的末字符
P[m]与对应的正文串T中的字符T[i+m]进行比较时,若T[i+m]在模式串P中并不存在,则模式串可以一次向右移动m个字符,使模式串只经一次比较就可以移动模式串的长度,
字符P[m]与正文串T对应字符T[i+m]是否相匹配。一旦发现不匹配,通过查找预处理好的坏字符移动表Badchar与好后缀移动表GoodBuffer,对所得到的结果进行比较,用移动距离较大值向后移动模式串P的尝试位置。其中坏字符移动表用式(1),好后缀移动表用式(2)求出。
Badchar[c]m+1;c!
这使BM比KMP算法更快。在实用上,BM要比KMP算法快
3~5倍。
=P[j];0≤j≤m
本文分析BM算法及其各种相关改进算法,结合其优点对
BM算法作出新的改进。针对坏字符在模式串中出现的惟一
m-j;j=max{j|P[j]=c;0≤j≤m}
(1)
GoodBuffer[i+1]=ms|s>0,i<k<m,s≥kP[k-s]=P[k]
s<i,P[i-s]≠P[i]}
(2)
性,坏字符的前驱以及坏字符在正文串中对应字符的后继字符在模式串中的存在性,模式串末字符是否为模式串串首字符,以及坏字符与其后继字符在模式串中是否存在同样的子串进行分析,作出进一步的改进。
虽然BM算法执行效率较高,由于没有考虑好后缀与坏字符之间的前驱后继关系,使得算法在总体上效率不高,仍可以有更多的改进。目前就有多种对BM算法的改进,如BMG、
收稿日期:2008212202;修回日期:2009201209 基金项目:国家自然科学基金资助项目(60373109);北京电子科技学院开放基金资助项目(KFHT200704)
作者简介:张红梅(19822),女,四川南充人,硕士,主要研究方向为网络安全、信息安全等(zhanghongmei_abc@163.com);范明钰(19622),女,四川成都人,教授,博导,主要研究方向为信息安全.
Sep 2009 . 模式匹配 BM 算法改进张红梅, 范明钰摘 * (电子科技大学 计算机科学与工程学院, 成都 610054) 要: 研究 BM 串匹配算法, 分析国内外各种改进算法,...
在研究现有算法的基础上提出一种改进的模式匹配算法 ——— New - Search 算法 。 该算法以 BM 算法为基础 ,通过预处理阶段处理 ,首末字符部分定位的思想 , ...
2008 文章编号 : 1672 - 7843 (2008) 01 - 0054 - 04 一种 BM 模式匹配的改进算法李必鹏 ,肖书成 ,李 洋 1 2 3 ( 1. 后勤工程学院 政治部 ,重庆 ...
一种BM模式匹配算法的改进一种BM模式匹配算法的改进隐藏>> -.$/0123 4"5%"223%"5 ,"6 7//8%9,1%.": !""# $% &' &"% ...
对BM模式匹配算法的一种改进_专业资料。模式匹配在入侵检测系统中有着广泛的应用。在对BM以及相关算法分析的基础上,提出了一种基于BM算法的改进算法。该算法同时...
对BM模式匹配算法的一个改进_专业资料。在分析BM算法的基础上,提出了一个改进的模式匹配算法QBM算法。该算法采用最长前缀的思想,在匹配后缀的时候采用一个位置...
中被 广泛的应用它 也是 计算机基拙科 学的 一个重 要部 分现在比较著名、、 , , 的模式匹配算法有 B F 算法 K M p 算法 R K 算法和 B M 算法 。...
中被 广泛的应用它 也是 计算机基拙科 学的 一个重 要部 分现在比较著名 , , 的模式匹配算法有 B F 算法 K M p 算法 R K 算法和 B M 算法、、 。...
尽管如此,BM算法的效率还是可以再提高的。本文在介绍经典BM算法及其改进的BMH、BMHS算法的基础...更多>>模式匹配算法在数字通信、入侵检测等多种领域都有着广泛的...
热门文档