字符串匹配算法Sunday的改进

字符串的模式匹配应用十分广泛,在信息的搜索查询等方面具有重要作用,研究串匹配算法的效率具有重要的理论价值和实际意义。在分析几种经典模式匹配算法的基础上,对当前应用最广泛的Sunday算法提出了改进的算法Zhusunday.算法主要改进之处是:在字符串从右向左匹配过程中,当文本字符中出现不匹配模式字符串的字符且该文本字符不是坏字符时,算法从右向左搜索当前文本字符在模式串中出现的位置;找到当前字符在模式串中的位置后继续再向左匹配模式串字符一次,如果仍不匹配时,模式窗口比Sunday算法多向右移动一个字符。改进的算法提高了模式匹配的执行效率,通过大量对比实验证明了该算法的有效性。最后得出结论:在实际应用中,坏字符大量存在的情况下,改进算法的最优时间复杂度可达O(n/m),在同一时间复杂度下,比Sunday算法效率提高25~50%.     

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

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

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

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

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

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

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

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

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

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

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

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

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

在分析了BM算法以及一些重要的改进算法的基础上,提出一种新的改进算法—Y_BMHS\r\n算法.该算法利用辅助的二维数组,考虑了文本串后间隔的两位字符和模式串首字符的唯一性,使\r\n得最大位移提升到m+3,出现概率也显著提高,加快了匹配速度.实验证明Y_BMHS算法比BM、\r\nBMH、BMHS等算法有更好的性能.     

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

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

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

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

Horspool扩展算法在方块苗文模式匹配中的应用

分析了Horspool算法的原理及特点,提出了一种适用于方块苗文环境的字符串模式匹配算法.该算法结合方块苗文的编码方式及字符串查找的特点,通过对Horspool算法中的字符处理单位进行扩展来适应方块苗文的字符串匹配.实验结果表明,在单字词、双字词和多字词的方块苗文字符串匹配过程中,该算法均呈现出较好的性能,能够用于解决方块苗文的快速检索问题.     

一种改进的KMP入侵检测的模式匹配算法

提出了一种基于KMP的模式匹配算法,给出了具体的实现方法。在不丢失匹配项的前提下,增大next函数的值,使得模式串向右尽可能得滑动更远的一段距离,忽略不必要的比较。通过实验证明,该方法与传统的方法相比能有效地加快匹配的速度,提高入侵检测的效率。     

一种快速近似模式匹配算法

为进一步提升传统的近似模式匹配问题解决方法——动态规划算法的性能,提出了一种新的过滤型近似模式匹配算法.该算法结合动态规划算法,切分模式串得到长度相等且更小的模式片;在此基础上将待匹配的文本串分割成子串,并建立相应的索引;同时设计了一个新的过滤策略来消除匹配检查中的冗余.通过实例将文中方法与现有方法进行对比,结果表明:文中方法的匹配时间较短,匹配性能优于现有方法;随着模式串长度的增加,文中算法的优越性更为明显,模式串长度大于45后,文中算法的匹配时间可比传统动态规划算法缩短一半以上.     

入侵检测中字符匹配系统的FPGA实现

在入侵检测系统中,由于基于软件的字符匹配系统受处理器性能与软件串行执行等因素影响,处理速度有限,故设计并实现了基于FPGA的字符匹配系统.以硬件电路的实现方式提升处理性能,并采用了适合于FPGA运算的XORHash算法快速计算地址,从地址中取数据进行匹配,并实现数据的并行处理.通过在原有入侵规则实现逻辑上进行修正,实现规则的更新,通过预处理对冲突的模式串单独匹配解决了冲突.实验结果显示,系统的数据处理能力达到了129Gbps,为软件方法的35倍以上.当处理更多Snort规则时,系统吞吐量不受影响,资源的消耗增加很少.     

一种时间序列曲线形态的描述方法及其在车型识别中的应用

提出时间序列曲线形态的一种新的描述方法。首先根据曲线段类型定义了5个语素和1个通配符,进而定义语素向量及通配符向量,使得对曲线的描述具有层次性。据此可将任意时间序列曲线转变为对应的二维表,二维表表头组成的字符串能够进行初级的模板匹配,二维表表列所代表的语素向量增强了语素关系运算的能力,可实现较深入的模式识别。为使所提出的描述方法能应用于曲线形态辨识,在经典回溯法的启发下设计了一种属性约束下的带通配符字符串匹配算法。最后,以基于感应线圈信号曲线的车型分类为例,验证了所提出的方法的有效性和合理性。     

带记忆的Boyer-Moore型模式匹配算法及其复杂性分析

通过构建前缀匹配自动机,使得每轮匹配后下个匹配窗口的文本总是保持左端部分为模式的一个前缀、右端部分全为未比较过的字符的形式.对于与此相应的模式匹配算法,已证明文本内的每个字符在整个匹配过程中最多被比较一次,从而字符总比较次数不超过n,已达到任意算法最坏情况下字符总比较次数的最小值.另外,在适当条件下还从理论上证明了此算法的亚线性(即字符总比较次数小于cn,其中常数c＜1).根据实验结果,算法的实际运行速度快于Boyer-Moore算法.     

基于结构相似的改进SIFT图像复制 粘贴篡改检测

基于SIFT算法的复制-粘贴篡改检测方法中用广义2NN测试获得的匹配点对存在错误匹配,产生误匹配点,针对这一问题,提出了一种利用匹配点对间的结构相似性对广义2NN测试得到的匹配点对进行提纯,剔除误匹配点对,提高匹配正确率;误匹配点对的剔除,减少了匹配点对,使后续的聚类和几何评估操作减少了时间,由此提高了整个算法的执行效率;实验表明改进算法性能有较大提升。