一种改进的Sunday匹配算法

字符串的模式匹配算法在多协议识别技术中,起着至关重要的作用,为了提高多协议识别效率,该文在分析几种经典模式匹配算法的基础上,提出一种基于Sunday算法的改进算法。算法主要是在每次匹配开始前通过一个条件判断语句,判断主串中的相应后缀是否在模式串中,从而减少了无意义的匹配次数,提高了算法的执行效率,通过对比实验证明了该算法的有效性。     

一种字符串模式匹配算法的实现

为寻求更有效的字符串搜索方法,利用有穷自动机的定义,分析KMP算法以及自动机状态转换规律,提出了一种新的字符串模式匹配算法.结果表明此算法具有比基本的串匹配算法更优越的算法复杂度,并且相对KMP算法而言更简洁易懂,在计算机上容易实现.     

改进的Sunday模式匹配算法的设计与实现

针对Sunday模式匹配算法低效率问题,研究了它的改进算法I—Sunday算法．依据模式匹配算法的跳跃思想,I—Sunday算法在遇到坏字符时,不但考虑当前匹配窗口的下一位字符,而且也考虑了下一位字符之后长度为模式串长度的那个字符,这就跳跃了更大的距离．另外,匹配时采用双向并行方式进行匹配．为了验证I—Sunday算法的性能,在同等条件下,在匹配次数和比较的字符个数两方面对I—Sunday算法进行实验．实验结果表明,由于I—Sunday算法能够跳过大量的坏字符,大大地减少匹配次数和字符的比较,从而缩短匹配时间,有效地提高模式匹配速度．     

基于Wu-Manber的快速跳跃多模式匹配算法

海量信息处理以及网络入侵检测等应用都对串匹配技术提出了新的挑战。在分析多模式匹配的Wu-Man- ber算法之后,提出一种基于WM的快速跳跃多模式匹配算法。该算法采用增大跳跃距离、减少冗余移动的方法,提高了WM算法的查找效率。试验数据表明该算法的查找时间比WM算法减少了5-9%。     

一种基于位图的多模式匹配算法

为降低自动机类多模匹配算法的空间开销,同时仍保持较低的算法时间复杂度,提出了一种基于位图的空间优化算法.将自动机全部状态按照字典树结构的层数划分,将访问频率较低的后若干层状态对应的转移表压缩存储,并使用位图提高对被压缩信息的检索速度.经过实验和在实际应用环境中的验证,这种改进算法能够大幅降低空间开销,而匹配时间或响应时间基本不变.在模式串的数量达到万条以上规模时,实验表明优化算法能够降低25%～70%的空间消耗.     

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

针对WM算法在模式集规模大且最短模式长度小的情况下性能较低的问题,分析了WM算法及其改进的快速WM(QWM)算法的优缺点,在此基础上提出了模式分集思想,并优化了跳跃和确认机制,设计了子集WM(SWM)算法;然后针对该算法在域名过滤中的应用,对hash函数、匹配顺序等进行进一步优化．针对域名过滤的实验结果表明,当模式数量超过10000条时,SWM算法匹配时间是WM算法的8.9％～11.6％,说明SWM算法在模式集规模较大时,匹配速度能显著提高．     

一种多模式匹配高效算法的设计与实现

随着国家信息化的不断推进和计算机网络飞速发展,网络信息安全审计成为网络信息安全中不可或缺的重要组成部分．网络信息安全审计系统从网络关键点采集数据包,对其传送内容进行审计分析,达到网络信息内容的监控．在网络信息安全审计系统中,需要对大量的关键字进行匹配,匹配算法的性能极大程度地影响了整个审计系统的性能．通过比较分析现有的多模匹配算法,设计实现了一种基于二叉树多模匹配的算法,并在最后通过实验测试,得到了良好的性能指标．     

字符串的模式匹配算法——基于KMP算法的讨论

重点对基本的串匹配算法和 KMP算法进行了探讨。通过对这两种算法的比较分析提出了一个新算法 ,此算法具有比基本的串匹配算法更优越的时间复杂性 ,并且相对KMP算法而言更简洁易懂     

一种基于硬件的高速低功耗多模式匹配算法

介绍了一种基于硬件的多匹配分类引擎,克服了传统的包分类引擎只能够找到一个给定数据包的最优匹配的局限性。同时提出了一种新的TCAM节能方法,在满足骨干链路速率的基础上,其硬件功耗较现有算法分别节省72．25％和87．29％。     

一种基于TCAM的PLO_OPT算法的改进

在最大前缀长度为L的TCAM(Ternary Content Addressable Memory)中,采用PLO_OPT算法更新路由表项仍然有很大的时间消耗,其时间复杂度为O(L/2)。为了进一步提高路由更新速度,根据路由前缀数量分布图,本文提出了一种PLO_OPT路由更新算法的改进方案,每更新一次表项只需进行一次操作即可,可以使时间复杂度达到O(1),且更有效地利用了存储空间。     

一种基于遗传算法的立体匹配方法

立体匹配问题是被动视觉研究中最关键的问题之一。本文定义了描述立体匹配问题的染色体表示,设计了相应的适应度函数,并按照立体匹配中相应的约束条件,将遗传算法应用于该问题中。实验证明该算法具有较强的适应性和稳定性。     

基于投影与KMP简约算法的一维快速模板匹配算法

传统的模板匹配算法(如NC和SSDA)虽然具有匹配精度高的优点,但由于其计算量大,使得匹配时间过长。本研究提出了一种新的基于投影与KMP简约算法的一维快速模板匹配算法,首先将图像进行降维处理,得到特征字符串,通过对特征字符串的匹配,实现粗匹配,可大幅度地减少图像匹配时间;然后利用NC匹配算法,对粗匹配的结果进行验证,以达到快速匹配的目的。通过实验证明了本算法的快速性和准确性。     

改进的AC-BM字符串匹配算法

提出了改进的AC-BM算法,将待匹配的字符串集合转换为一个类似于Aho-Corasick算法的树状有限状态自动机。匹配时,采取自后向前的方法,并借用BM算法的坏字符跳转和好前缀跳转技术。改进的AC-BM算法借助BMH算法思想,取消了原AC-BM算法的好前缀跳转,并对坏字符跳转部分的计算进行优化。新算法修改了skip的计算方法,不再保留每个节点的好前缀跳转参数及坏字符跳转参数,因此匹配只与当前匹配字符有关,而与当前节点无关,可以实现大小写正文的识别。     

计算DNA序列模式特征的匹配算法

分析了DNA序列特征计算过程中的特殊性,提出了一种基于“空间换时间”的模式匹配算法,设计了以map数据结构来存储中间结果的方案,使得扫描DNA序列一次即可同时计算所有元组模式在该序列中出现的次数。实验结果及分析表明,算法提升了DNA序列模式特征计算的效率,较好地解决了计算DNA序列模式特征的问题。     

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

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

基于自适应遗传互相关算法的模板匹配

提出一种将自适应遗传算法与灰度互相关函数结合的模板匹配方法。通过合理设计自适应遗传算法和遗传参数以充分发挥遗传算法的全局寻优能力，从而降低模板匹配的时间复杂性，提高模板匹配的实时性。     

自适应窗口和半全局立体匹配算法研究

针对区域立体匹配算法中匹配窗口的选择和在图像中视差不连续、弱纹理区域误匹配率较高的难题,提出了一种自适应窗口和半全局算法相结合的立体匹配算法.该算法先通过基于灰度的自适应窗口算法计算初始匹配代价,然后利用相邻像素之间的视差梯度作为约束,采用半全局立体匹配算法以得出视差图.最后对左右视差图进行左右一致性遮挡检测,获得精确的稠密视差图.针对不同的图像信息采用自适应窗口和半全局算法相结合的立体匹配算法,剔除、修正了视差不连续、弱纹理区域的误匹配点,得到匹配效果较好的视差图.实验结果表明:该算法有效降低了视差图在视差不连续、弱纹理区域和遮挡处的误匹配率.     

一种面向入侵检测的模式匹配算法

模式匹配算法是入侵检测系统中的一种重要算法,算法的效率直接影响入侵检测系统的性能。针对 传统模式匹配算法按照模式中字符排列顺序进行匹配的过程,提出一种基于统计的模式匹配算法,该算法利用字符 串本身的统计特征,利用子串中在主串中出现频率最少的字符为关键字符,通过该字符在主串中出现的位置进行跳 跃式匹配,加快了模式匹配的速度。实验结果表明,该算法比同类的其它算法更加高效。