入侵检测系统中改进的AC_BMH算法

提出一种改进的AC_BMH算法。该算法利用双字符进行跳跃,可以在增大模式串失配概率的同时跳过更大的距离,通过结合QS算法进一步增加模式串匹配失败时的跳跃距离,并借助压缩存储机制降低内存的使用量。实验结果表明,相比原AC_BMH算法,改进算法的字符串匹配速度提高了29%~52%,在模式串较多时,内存使用量可减少90%。     

改进的多模式字符串匹配算法

在经典的AC多模式字符串匹配算法的基础上,结合BMH算法的优点,提出了一种快速的多模式字符串匹配算法。一般情况下,该算法不需要匹配目标文本串中的每个字符,而是在实际比较之前跳过尽可能多的字符,以减少字符比较的操作,实现快速匹配。在模式串较长和较短的情况下,算法都有很好的性能。实验表明,在模式串较短时,本算法所需的时间仅为AC算法的50%～30%;在模式串较长时,所需时间为AC算法的26.7%～15.2%。     

分段处理的1／p概率字符串匹配

现有的概率字符串匹配算法通过计算字符串之间的最小失配字符数(编辑距离),可求出字符串之间的相似度.这些算法平等地看待模式串和文本串,虽然可求出二者之间完整的编辑距离,但并不能解决以下问题:即判断是否模式串中至少有1/p的字符顺序地出现在文本串中.基于动态规划字符串匹配算法,提出了一个改进算法.该算法通过将字符串分段,在段内执行改进的概率匹配算法可求出段内的编辑距离,再结合回溯策略可以很好地解决上述问题.该算法的复杂性要低于基本动态规划匹配算法,且在某些情况下效率更高.就问题的一般性而言,该算法可广泛地应用于计算生物学、信息安全和信号处理等诸多领域.     

基于有序二叉树的快速多模式字符串匹配算法

将有序二叉树和QS算法相结合,提出一种快速多模式字符串匹配算法,实现在多模式匹配过程中不匹配字符的连续跳跃。为提高匹配速度,利用已匹配的字符串信息进行跳跃式的比较,避免文本扫描指针的回溯。实验结果表明,与SMA算法相比,该算法在预处理阶段构造速度和匹配速度更快,在模式串较长的情况下,性能更优越。     

大规模语料中频繁模式增量发现算法

提出一种适用于大规模语料的频繁模式增量发现算法。统计局部区域提取的字符串频度,对局部相对低频字符串进行剪枝。利用多模式串匹配算法,统计剪枝后局部相对高频字符串在整个语料中的频度,得到频度大于阈值的频繁模式。实验结果表明,该算法具有较低的空间复杂度和时间复杂度,内存消耗为基于后缀数组的频繁模式发现算法的20%左右。     

一种基于分段匹配的字符串匹配算法

针对已有算法对文本和模式的相关性依赖较大,提出一种基于分段的字符串匹配算法——SM。该算法利用特殊字符将文本先分段再匹配,且匹配过程对模式内容和长度不敏感。通过将SM算法与经典算法进行分析和实验对比,证明SM算法性能稳定,特别是在多模式字符串匹配情况下,SM算法具有比Wu-Manber算法更快的速度和更小的空间消耗。     

一种基于反向有限自动机的多模式匹配算法

在基于有限自动机的多模式匹配算法DFSA的基础上,结合改进的BM单模式匹配算法的优点,提出一种快速的多模式字符串匹配算法。在一般情况下,该算法不需要匹配目标文本串的每个字符,能充分利用匹配过程中本次匹配不成功的信息和已成功的信息,跳过尽可能多的字符。实验表明,模式串较短时,该算法需要的时间约为DFSA的1/2,模式串较长时,所需时间约为DFSA算法的1/3。     

基于AC自动机的多模式匹配算法FACA

Aho-Corasick自动机算法在模式匹配失配时,需要多次回溯才转移到有效的后继状态。为此,提出一种快速多模式匹配算法。该算法为每个状态建立失配时的后继指针,在模式匹配失配时,可以通过失配后继指针快速找到有效后继状态,从而避免Aho-Corasick自动机失配时的过多回溯,提高匹配效率。算法在自动机建立时采用动态规划的方法,为每个状态建立匹配长度和匹配量等信息,在模式匹配过程中,基于这些信息统计模式串在主串中的重复次数、最早出现模式串位置等信息。实验结果表明,该算法匹配精确、效率高,且支持在线操作。     

一种面向高速网络的模式匹配算法的设计与实现

本文在对Boyer-Moore(BM)算法及其改进的算法BoyerMoore-Horspool(BMH)算法进行分析的基础上,提出了一种更加快速的模式匹配算法-HPMA(High-Speed-Pattern-Matching-Algorithms,高速模式匹配算法)。该算法采用从模式两端向中间位置交替的匹配顺序,减少了模式的一部分后缀与文本匹配,而模式的前缀却不匹配情况下不必要的比较,同时考虑字符串后一位字母的唯一性,提高最大位移的出现概率。     

基于过滤的中文多模式近似字符串匹配算法

当前近似字符串匹配算法主要针对英文等中小字符集,该文针对汉字等大字符集的有效算法很少,尤其缺少适合汉字等大字符集的多模式近似匹配算法的情况,提出了一种适合汉字等大字符集的多模式近似匹配算法——MBPM-BM,通过实验证明了该算法的有效性。 近似字符串匹配;中文字符串匹配;多模式匹配;位并行运算;过滤     

入侵检测系统中的带权模式匹配算法

入侵检测系统（IDS）需要根据每个模式串的权值,计算给定主串的总权值并反馈给报警系统。传统的模式匹配算法在计算主串权值时效率低。为此,文中在Aho—Corasick算法的基础上,提出了带权模式匹配算法（WPM）及其改进算法（WPME）。算法优化了自动机的建立过程,对自动机每个节点的失配后继指针信息和匹配量信息进行预处理,从而避免了模式匹配阶段在计算主串权值时的回溯操作,降低了算法的时间复杂度。实验表明,改进后的算法具有效率高、匹配精确的特点。     

由粗到精稳像方法的应用研究

视频稳像的精度和处理效率在视频稳像处理中非常关键。通过分析视频稳像的原理和常用的几种算法,提出一种基于灰度投影和块匹配相结合的算法。先使用灰度投影算法进行首次匹配工作和粗补偿,针对灰度投影提出一种快速搜索算法,可以有效减少计算量。灰度投影算法的作用是为下一步的工作做铺垫。然后使用块匹配进行第二次匹配和精确补偿,其中菱形搜索（DS）策略的应用可以有效地提高算法效率。提出的算法体现了一种由粗到精的处理思路,灰度投影和块匹配算法可以很好地配合工作。实验结果表明,该算法在保持较高稳像精度的同时有效降低了计算复杂度。     

基于GPU的位并行多模式串匹配研究

图形处理器(GPU)具有较强的单一运算能力及高度并行的体系结构。根据上述特点,选择基于位并行技术的多模式串匹配算法M-BNDM,将其移植到GPU上加以实现和优化。通过对需要处理的数据进行预处理,将串匹配的过程简化为更适合CUDA计算数据的位操作。对基于CUDA架构的并行串匹配算法的性能影响因子进行分析。实验结果表明,与同等CPU算法相比,该算法能够获得约十几倍的加速比。     

基于像素字符串比较的图像快速匹配算法

在分析传统的模板匹配算法的基础上提出了一种新的基于字符串匹配的快速匹配算法。算法的思路是在模板图像上任意确定一列像素，并将这一列像素的灰度值看成是一个字符串，以此对原图像的每一列进行字符串匹配。如果在原图像上的某一列上找到了完全匹配的串，或者找到最大匹配的串，就找到了所要匹配的模板在图像中的可能位置。然后在所有找到的位置上再做进一步的字符串匹配。如此继续就可以确定模板图像在待匹配图像上的位置。算法在统计意义上保证了匹配效果，且提高了匹配速度。实验结果表明该算法是一种有效的图像匹配算法。     

改进的QS模式匹配算法的性能分析

在详细分析QS匹配算法的基础上,提出了一种改进的算法I_QS算法。I_QS算法把模式串中每相邻两个字符构成一个字符串,由这些字符串组成字符串表并确定其位置,同时通过当前匹配窗口的后三个字符来确定下一次的右移量。为了分析I_QS算法的性能,从不同模式串数目角度,对I_QS算法进行匹配所需要的时间、所尝试的次数、所比较的字符个数三方面进行实验。实验结果表明,由于I_QS算法能够最大限度地向右移动,从而大大地减少移动次数和缩短匹配时间,有效地提高模式匹配速度。     

基于压缩后缀数组的近似字符串匹配算法

近似字符串匹配是模式匹配研究领域中的一个重要研究方向。压缩后缀数组是字符串匹配、数据压缩等领域广泛使用的索引结构,具有检索速度快和适用广泛的优点。利用压缩后缀数组,提出了适合近似字符串匹配搜索算法的数据结构,并在此基础上提出了一种匹配搜索算法。实验结果表明,相对于现有的算法,提出的算法在小字母表的情况下具有计算优势。     

基于终端直通通信的多用户计算卸载资源优化决策

随着计算密集和时延敏感类应用的激增,移动边缘计算（MEC）被提出应用在网络边缘为用户提供计算服务。针对基站（BS）端边缘服务器计算资源有限以及网络边缘用户远距离计算卸载的时延较长等问题,提出了基于终端直通（D2D）通信的多用户计算卸载资源优化决策,将D2D融入MEC网络使用户以D2D方式直接卸载任务到相邻用户处执行,从而能够进一步降低卸载时延和能耗。首先,以最小化包括时延和能耗的系统计算总开销为优化目标,建模多用户计算卸载和多用户计算资源分配的联合优化问题;然后,将求解该问题看作是一个D2D配对过程,并提出基于稳定匹配的低复杂度的多用户计算卸载资源优化决策算法;最后,迭代求解D2D卸载的优化分配决策。通过理论证明分析了所提算法的稳定性、最优性和复杂度等特性。仿真结果表明,所提算法相较于随机匹配算法能够有效降低10%~33%的系统计算总开销,并且其性能非常接近最优的穷举搜索算法。可见,所提基于D2D卸载的决策有利于改善时延和能耗开销性能。     

一种新的字符串单模式匹配算法

在分析了BM模式匹配算法的基础上,提出了一种新的字符串单模式匹配算法,该算法通过对模式中的字符进行等级划分,设置模式中各个字符的优先级,改进模式串的移动方式,减少了模式匹配的次数和字符比较的次数,有效的提高了模式匹配的效率。实验显示,该算法有效的提高了模式匹配的效率。     

改进的AAC多模式实时匹配算法

AAC算法（Advanced AC）是使用最为广泛的多模式串匹配算法,匹配性能高,匹配时间稳定。针对AAC算法为判定转移目标状态是否为终结状态,在匹配时每读入一个字符都要访问output表,代价较高的问题,通过两种方法改进了AAC算法。第一种方法为拷贝自动机中的终结状态,将其附加在AAC自动机后,并将原自动机中指向终结状态的转移目标修改为附加状态,直接根据转移目标位置判断当前状态是否是终结状态,从而提出Advanced AC with Additive state（AACA）算法。第二种改进方法为将自动机中指向终结状态的状态转移值置为负数,根据转移目标的值直接判断目标状态是否为终结状态,从而提出Advanced AC with Negative state（AACN）算法。以上两种改进算法只有在发现模式匹配时才需进行output表的访问。实验数据表明：AACA和AACN算法性能均高于AAC算法,特别在中小规模匹配上,性能提升更为明显。