分块法的模式匹配算法的研究

为提高模式匹配算法性能,介绍经典的模式匹配算法Byoer-Moore和Sunday,分析它们改进后的效率,根据分块法的特点,提出一种新的分块模式匹配(block pattern matching,BPM)算法?BPM算法在预处理阶段先确定模式串的首字符在文本串的位置,再确定此字符后长度等于模式串长度的字符是否等于模式串的尾字符,若符合条件,采用单链表存储结构进行存储,在匹配阶段,利用单链表信息进行双向匹配?实验结果表明,BPM算法大大减少了匹配次数和字符比较个数,从而提高匹配效率?     

一种改进的BM算法性能分析

BM是一种基于坏符号和好后缀规则的字符匹配算法,从右向左进行字符匹配,虽然算法简单易懂,但是有一些比较是多余的,导致效率不高,因此提出一种改进的BM算法,实验数据表明,随着文本串长度的增加,模式串和文本串的比较次数以及模式串的移动次数都明显降低,算法的效率得到提高。     

一种改进的Sunday模式匹配算法

字符匹配效率是很多计算机应用系统的性能瓶颈,研究设计高效的匹配算法有助于提高相应系统的应用性能。在分析典型Sunday匹配算法的基础上,对其进行了较为有效的改进。改进算法在字符串匹配前先计算模式串的倒序特征值,也就是以此计算出模式串的最后s个字符在本模式串中倒序除自己以外的下一次出现的位置。每一次字符匹配都采用倒序匹配并利用这种匹配的结果,匹配结果结合倒序特征值可以直接决定特征串的下一次位移数。在进行完一次字符匹配后,采用增加一个遍历字符的Sunday算法来遍历模式串以计算下一次位移数,以此尽可能地排除无效匹配。实验结果表明改进算法的效率比Sunday算法有一定提高。     

一种改进的Sunday字符串匹配算法

针对Sunday匹配算法在首字符和正文存在大量重复,使得其平均执行效率降低这一问题,提出了一种改进的Sunday算法。首先将重复的首字符压缩为一个字符,然后使用压缩后的字符串和正文进行匹配,若匹配成功,对成功匹配的位置信息前的字符和首字符进行循环匹配;如果匹配位数和模式串相同,则返回成功,否则返回失败。改进后的算法大大减少了匹配次数,使执行速度有了明显的提高。     

一种改进的KMP高效模式匹配算法

针对KMP算法存在着主串与模式串中多个相同字符重复比较的缺陷,在KMP算法的基础上,给出了一种新的模式匹配算法,该算法不像KMP算法那样向左滑动模式串的指针,而是每次比较字符不匹配时,根据模式串当前字符的特征值k,使主串的指针向前跳跃k个值,且使模式串的指针置于起始位置,开始新一轮的匹配,加快了主串的匹配速度．理论分析和试验证明,该算法需要的比较次数比KMP算法减少将近一半．     

适合中文的双向比较模式匹配算法

分析了几种常用的模式匹配算法,提出一种适合于中文的基于KMP的改进算法,即双向比较模式匹配算法.该算法以KMP算法为基础,引入特征数组以记录模式串尾字符在模式串中出现的位置信息,从而获得模式串在匹配过程中的最大移动距离和最少比较次数.实验结果表明,双向比较模式匹配算法可有效降低匹配次数.     

一种快速的多模式字符串匹配算法

以基于有限自动机的多模式匹配算法（DFSA）为基础，结合Boyer-Moore(BM）和Quick Search（QS)快速单模式匹配算法的优点，提出了一种快速的多模式字符串匹配算法，在一般情况下，该算法不需要匹配目标文本中的每个字符，能充分利用匹配过程中本次匹配不成功的信息和已经匹配成功的信息，跳过尽可能多的字符。实验表明，模式串较短时，本算法所需时间为DFSA算法的1／2－1／3；模式串较长时，本算法所需时间为DFSA算法的1／2－1／3；模式串较长时，其所需时间为DFSA算法的1／3－1／5。     

一种改进的多模式匹配算法

在基于有限状态自动机的多模式匹配算法(DFSA算法)基础上,结合Tuned BM算法的优点,提出一种快速的多模式字符串匹配算法,实现了多模式匹配过程中不匹配字符的连续跳跃.在一般情况下,算法不需要匹配目标串中的每个字符,而是在实际比较之前跳过尽可能多的字符,以减少字符比较的操作,实现快速匹配.在模式串较长和较短的情况下,算法都有很好的性能.分析指出算法实际比较的字符数随着模式串长度的增加而下降,并随模式集的增大有所增多.实验表明,在模式串较短时,算法需要的匹配时间仅为AC算法的50%到33.3%,AQR算法的90%左右;在模式串较长时,所需时间为AC算法的25%至12.5%,AQR算法的75%左右.     

一种新的多模式快速匹配算法

提出了一种针对多模式的快速模式匹配算法.算法分为预处理阶段和匹配阶段两个部分,预处理阶段对所有待匹配的模式进行分析,构造一个关于这些模式的树型有限状态自动机,匹配阶段利用这个模式自动机,对文本串进行一次性的搜索,查找文本是否包含模式集中的模式.为了提高了匹配速度,算法利用已匹配的字符串信息实行跳跃式的比较,避免了文本扫描指针的回溯.     

模式匹配算法的优化研究与实现

模式匹配算法已在入侵检测、文本挖掘等多种领域中被普遍运用,尤其是网络安全方面,如信息过滤、入侵检测等等.而模式匹配算法的效率性能对于提升网络安全性能有很直接的影响,所谓的模式匹配算法,即是在给定的文本主串T中寻找模式串P并进行匹配定位的一个过程.本文对一些比较经典、在实际应用中使用广泛的算法做了简要的介绍和分析,并且基于BMH算法和BMHS算法做了一些优化和改进,本文融合了BMH算法和BMHS算法之所长,并且在匹配的时候进行了双向匹配,仿真实验结果表明本文提出的改进算法提高了匹配效率缩短了执行时间.     

一种新的多模式快速匹配算法

提出了一种针对多模式的快速模式匹配算法。算法分为预处理阶段和匹配阶段两个部分，预处理阶段对所有待匹配的模式进行分析，构造一个关于这些模式的树型有限状态自动机，匹配阶段利用这个模式自动机．对文本串进行一次性的搜索，查找文本是否包含模式集中的模式。为了提高了匹配速度，算法利用已匹配的字符串信息实行跳跃式的比较，避免了文本扫描指针的回溯。     

一种新的快速移动单模式匹配算法

针对单模式匹配算法BM算法中平均移动距离较小的特性,文章对BM算法进行改进,提出了一种新的可以增加平均移动距离的字符串匹配算法BMN算法。该算法首先在预处理阶段使用任意的2个字符作为字符块来计算移动距离,并设置最大移动距离为模式串长度加1;然后在查找阶段通过比较连续的2个字符块来增加大距离移动的概率。实验表明,无论模式串的长短,所提出的算法对于英文文本和二进制串均具有较快的速度。     

基于WM算法改进的多模式匹配算法

为提高入侵检测系统整体的性能和效率,在研究经典的WM(Wu-Manber)多模式匹配算法的基础上,提出一种改进的WM多模式匹配算法.该算法使用后缀表方法,减少了匹配过程中模式字符串与文本的比较次数.实验结果表明,该算法有效提高了入侵检测系统匹配的速度和效率.     

一种改进的BMH模式匹配算法

目前的入侵检测系统大多是基于特征的，系统的性能瓶颈在于模式匹配算法的执行效率．在探讨几种典型的模式匹配算法的基础上，提出了改进的BMH算法．该算法通过取文本串中的两个连续字符计算偏移量的方式，减少了匹配的次数．实验结果证明匹配速度得到了一定程度的提高．     

基于BM算法的匹配算法的改进

对SNORT的原有规则匹配算法BM算法改进,利用规则树实现了BM算法的多模式匹配功能,在跳跃方面主要依靠于最短模式串与规则树首字符重复出现间隔距离双重控制,在首字符不匹配的情况下,移动模式串的最大距离就是前缀树中最短模式串长度,在整个匹配过程中,最大移动距离是由该前缀树中最短模式串的长度决定;而首字符匹配时,最大移动距离是由规则树首字符重复出现间隔距离决定。     

IDS中一种新的模式匹配算法及其并行化

基于字符串匹配的检测方法是入侵检测系统(IDS)中一类很重要的分析方法,文章分析了著名的BM模式匹配算法,提出了一种新的字符匹配算法zY模式匹配算法,该算法的时间复杂度为O（n*(m-1)),比BM算法的时间复杂度O(n*m)低。最后对ZY模式匹配算法进行了并行化设计,并给出了设计代码。     

基于BM算法的网络入侵检测算法研究

以BM算法为基础,提出一种快速的字符串模式匹配方法,该算法在匹配的过程中采用新的坏字符规则比传统的BM算法跳过的距离更大,并且在前缀不匹配的极端情况下能减少匹配的次数。实验证明,该算法具有良好的性能。     

面向入侵检测系统的模式匹配算法研究

针对入侵检测系统对基于攻击特征的网络数据包的检测效率低和丢包率高的问题,在分析典型的模式匹配算法的基础上,提出了一种Boyer Moor Horspool Fast(BMHF)匹配算法.引入一个新的判断函数Q(X)指出字符X在模式串中出现的次数,当出现次数为1时可以利用已匹配的信息加大移动距离,同时利用文本串中不匹配字符后面的一个字符进行匹配,从而得到一个移动距离.将不同移动规则下获得的移动距离的最大值作为实际的移动距离,依次进行,直到匹配完成.实验结果表明,BMHF算法的CPU运算时间比典型的模式匹配算法可平均节省5.7%,平均匹配次数减少12.5%.     

改进的KR模式匹配算法的研究与实现

文章在详细分析KR匹配算法的基础上,提出了改进的I_KR算法.I_KR算法的改进之处:一是采用2次Hash函数的方法在计算T的子串的散列值之后,马上与P的散列值进行比较;二是采用双向并行方式进行匹配.为了分析I_KR算法的性能,从不同文本串和模式串角度,在匹配次数和比较的字符个数方面对I_KR算法进行实验.实验结果表明,I_KR算法能够极大地减少匹配次数,缩短匹配时间,有效地提高模式匹配速度.     

基于划分的模式匹配改进算法

为提高基于划分窗口的字符串匹配算法(SKIP和KMPSKIP算法)的性能,结合QS算法的优点,通过提前预览下一窗口最后一个字符的移动信息跳过尽可能多的字符进行下一轮匹配,减少了匹配次数,提高了匹配效率.理论分析及实验结果均表明,改进算法在平均时间复杂度方面优于原始算法,在模式较短的情况下,ISKIP算法的平均运行时间仅为BMH算法的65%~85%.