单模跳跃算法的分析与改进

为改进串匹配的效率,通过引入有效载荷,对Horspool算法进行了分析。在字符集较小而模式串长度较大时,跳跃距离受字符集大小限制严重。结合好后缀思想,提出了基于好后缀的Horspool算法GsHor:比较窗口内对应末位字符相同的情况下使用好后缀距离移动窗口;结合Quick Search思想,提出了基于坏字符块的Horspool算法BcbHor。实验表明:字符集大小为4时,GsHor算法的比较次数比Horspool算法减小18%以上,BcbHor算法至少减少42.4%。     

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

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

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

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

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

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

基于混合策略的单模式匹配算法

结合后缀有限自动机和正向有限自动机的优点,提出了两个单模式匹配算法.算法中,无论是后缀自动机还是正向有限自动机,只要扫描到的模式前缀长度R>0或者超过模式长度的1/2时,使用正向有限自动机继续向右进行扫描;否则都滑动m-R个字符,使用后缀自动机反向扫描模式串的前缀.两个算法的最差、最好时间复杂度分别为O(n)和O(n/m).结果表明,在短模式的情况下,两个算法的平均时间复杂度均好于RF和LDM,在小字符集长模式或大字符集短模式的情况下它们的平均性能好于BM.     

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

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

Wu-Manber算法的一种综合改进

对孙晓山等提出的Wu-Manber算法的后缀改进算法作进一步的改进,在对next链表进行分类的同时把含有互为后缀的结点提到链表的前部,并整合了张鑫提出的精神的不良字符转移和弱化的良好后缀转移的改进方法,新改进的算法充分利用以上两种算法的优点,使区配过程中字符比较好的次数得到了进一步减少.新改进的Wu-Manber匹配算法在实验中取得了更高的效率.     

字符串匹配算法Sunday的改进

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

一种分布式后缀树构造与匹配算法

提出一种基于消息传递模式的分布式后缀树构造算法(DPSTG)及相应的并行匹配算法.DPSTG算法按不同的字符将原始字符串的后缀树分解成若干个子后缀树后由多个处理器并行构造.处理器间通过消息传递方式连接各个子后缀树,匹配时首先将要查找的字符串分割成若干不同首字符的子字符串,然后在构造相应首字符子后缀树的处理器上实现多个子字符串的并行匹配.理论分析表明DPSTG算法的时间复杂度要优于现有的大多数后缀树并行生成算法.模拟实验结果表明DPSTG算法的并行加速比随着待处理字符串的长度增加而提高.     

一种改进的Wu-Manber多模式串匹配算法

在分析Wu—Manber算法的基础上，结合QS算法思想，设计了一种改进的多模式串匹配算法：QWM（quick Wu—Manber）．算法充分利用紧邻当前窗口之后的B字符块，使算法的最大移动距离由原来的（m—B＋1）增大至（m＋B），平均移动距离也得到很大提高．同时对QWM算法和Wu-Manber算法进行了实验对比，无论模式串数量和最小长度怎么变化，性能都有较大提升．实验表明，改进的算法在对英文文本进行扫描时有4％～13％的提高．     

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

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

一种改进的多关键字匹配算法

基于多关键字匹配的Sun Wu算法进行的分析，结合Qs算法的思想，设计了一种改进的多关键字匹配算法：QMS（quick multi-pattern searching）。算法使用散列技术和前缀表减少发生部分匹配时实际进行的关键字比较次数。在计算跳跃距离时，充分考虑当前窗口的紧邻下一个字符带来的信息，进而使用更加精确的跳跃距离计算方法以获得更大的平均跳跃距离，从而获得更高的扫描效率和空间利用率。在真实文本上的对比实验表明，在通常应用环境中，该算法显著的缩短了扫描时间，取得了很好的效果。     

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

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

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

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

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

针对WM算法的查找效率随着模式集规模的增大而降低的问题,提出一种改进算法.在预处理阶段,改变原有Hash表中的链表结构,采用双哈希法将模式串存放在Hash1表中指定的区间,Hash表中存放该存储区间的起始位置与区间长度;Prefix表用于判断模式集中是否存在与当前匹配窗口中文本前缀相同的模式;当Shift表中出现移动值为0时,根据后缀出现在模式串其他位置的信息计算匹配窗口可滑动的最大距离并存于Shift1表中.在查找阶段,采用双哈希法在Hash1表的某一区间中查找模式串,避免在大规模模式集情况下查找过长的模式链表,扩大匹配操作后匹配窗口滑动的距离,减少冗余的匹配操作,缩短查找时间.研究结果表明:在模式集规模较大时,改进后的算法显著地提高了匹配速度;当模式串数目超过5 000条时,改进算法的查找时间要比WM算法缩短40％～47％.     

一种集成的字符集检测方法研究

有些文本缺少字符集信息,因而阻碍了字符信息的正确解析.为了获得字符集信息可以根据文本中字符信息的统计特征以及各种字符集之同的差异来识别出文本的字符集.集成的字符集检测方法通过综合应用编码模式检测方法、字符分布方法和双字符序列检测方法来检测字符集.它根据算法复杂度和每种算法的准确率来调度算法.使得在用一种方法不能确定字符集的情况下利用其它方法来检测出字符集实验结果表明:集成的字符检测技术具有较高的准确率.集成的字符检测方法在某些情况下通过适度增加一些时间来获得较高的精度.     

基于改进后缀树算法中英文聚类引擎的实现

提出一种基于改进后缀树与交互聚类思想相结合的算法ISTC算法, 通过改造传统后缀树结构实现了对文档标题和摘要的层次化聚类, 同时用交互聚类的方式替代了传统的递归算法. ISTC算法具有语言无关性, 不仅适用于基于单词的西方文字, 而且可以在不引入词典分词技术的情况下有效地处理基于单字的中文字符. 在此算法基础上, 设计并实现了基于改进后缀树算法的交互聚类引擎, 在不同的网络环境下对其 进行了系统测试, 并与其他元搜索引擎进行了对比. 实验结果表明, 使用改进后缀树算法进 行实时交互式聚类是可行的.     

一个基于序列比对的概念漂移检测算法

概念漂移检测目的在于准确捕获相邻窗口数据模式的变化,包括突变式概念漂移以及渐变式概念漂移。以往算法主要通过比较相邻窗口中聚类结果的差异来判断漂移,文章将序列比对的思想用于概念漂移检测,针对原序列比对算法只注重比中字符数目的局限性,提出了一种可同时考虑比中字符数目和连续匹配字符数目的序列相似性度量。并基于此,提出了一个基于序列比对的概念漂移检测算法CDD_BSA。实验表明:CDD_BSA在符号数据流上具有较好的概念漂移检测效果。     

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

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

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

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