一种适合中文的多模式匹配算法

中文字符的相互独立性导致AC算法的时空性能急剧下降。针对此问题,对AC算法的存储结构进行了改进,提出了一种适合中文的多模式匹配算法——AC_SC算法。该算法以邻接链表存储有限状态自动机,尝试解决存储空间快速膨胀问题,并将状态“0”的长链表转化为散列链表,以提高算法的匹配效率。实验结果表明,AC_SC算法具有良好的时空性能。     

基于Horspool算法的模糊匹配

匹配模式中存在模糊信息的匹配形式称为模糊匹配,它是目前字符串匹配的重要研究方向。Horspool算法是精确匹配的经典算法,但不能实现模糊匹配。该文将要求匹配的模式转化为相应的二进制数序列,在HorSpool算法基础上扩大其功能,使其能够实现模糊匹配,且不影响其精确匹配的功能。     

一种单模式匹配算法

本文在介绍经典模式匹配算法BM算法及其改进算法BMH算法的基础上,提出了一种单模式匹配算法。实验表明,该算法有效的加快了模式匹配的速度,提高了匹配效率。     

一种改进的模式匹配算法

本文分析了入侵检测系统中常用的模式匹配算法及现有的一些改进算法,在此基础上提出了一种新的改进算法,指出了进一步改进的方向.本文的算法利用了已匹配子串的信息,增大了模式串的右移量,提高了算法效率.试验结果表明该算法能够有效地减少模式串的移动次数,提高入侵检测系统的检测速度.     

一种节约内存的中文多模式匹配算法

AC及其改进算法基于有限状态自动机,随着中文模式串数目增加,完全Hash表和状态表矩阵存储方式会导致存储空间快速膨胀,状态转移函数计算量大,Cache命中率下降,算法的时空性能急剧下降。提出以邻接链表方式存储有限状态自动机,并将状态"0"的链表转化为线性表,以提高算法的时空效率。在此基础上,设计了一种适合中文的多模式匹配算法,该算法所需存储空间仅为完全Hash表方式的10%,约为状态表矩阵方式的20%。     

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

首先介绍了目前最常用的BM模式匹配算法,以及其改进算法Boyer Moore Horspool(BMH)算法,在此基础上提出了另一种改进的BM算法,该算法减少了匹配次数,有效的加快模式匹配的速度。     

一种改进的针对中文编码的Wu-Manber多模式匹配算法

Wu-Manber算法是多模式匹配领域性能优越的算法之一.针对Wu-Manber算法不能很好的用于中文环境,以及滑动距离受限和冗余匹配的问题,提出一种改进的针对中文编码的WM_CH多模式匹配算法.WM_CH针对中文编码修改了哈希函数,优化了建立哈希表的过程;修改并优化了算法匹配过程,在执行精确匹配时消除了冗余匹配,增大了单次精确匹配后的滑动距离.实际测试表明,该算法性能优异,保持与原算法匹配精确度一致,针对中文编码能快速过滤非中文字符.在特征串集规模大于50 000时,匹配速度比原算法提升40%以上,同时滑动窗口的跳转次数显著下降.     

一种入侵检测系统的模式匹配算法*

提出了一种基于后缀树自动机的模式匹配算法,匹配中应用后缀启发机制进行启发跳跃,忽略不必要的比较。实验表明,该方法与传统模式匹配方法相比能有效地加快模式匹配的速度,提高入侵检测效率。     

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

分析了目前网络上最流行的BM算法及其改进算法BMH,在此基础上提出了BMH算法的改进算法BMH2。考虑了模式串自身的特征,在原有移动距离数组的基础上增加一个新的移动数组,从而充分利用模式串特征进行更大距离的移动,使算法获得更高的效率。实验证明,改进后的算法能够增加“坏字符”方法的右移量,有效地提高匹配速率。     

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

基于字符串匹配的检测方法是入侵检测系统中的一种重要方法。通过分析几种常见的字符串匹配算法（AC、AC_BMH、Sunday等）的基础,提出了一种对AC算法的改进,新算法每一次匹配不成功后都能跳过尽可能多的字符以进行下一轮匹配,使得匹配次数大大减少,从而提高了匹配效率。分析了该算法的性能,并用具体的实验数据给出了几种匹配算法的测试结果。     

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

在对Boyer-Moore(BM)算法及其改进的Tuned Boyer-Moore(TunedBM)算法进行分析的基础上,提出了一种更加快速的单模式匹配算法--NFS.该算法利用当前尝试中匹配失败字符的位置信息进行更大的尝试位置移动,使算法具有更高的效率.实验结果表明,NFS算法的性能优于同类的其他算法,特别是在模式长度较短的情况下,优势更为明显.     

一种带稀疏间隙约束的并行模式匹配算法

带通配符的模式匹配是一个经典的研究问题,带有可变间隙约束的模式匹配是近年来比较热门的研究方向.为适应某些查询精度要求较高的应用领域,提出一种在稀疏间隙约束条件下求解模式匹配完备解的算法SGPM-SAI（pattern matching with sparse gaps constraint based on suffix automaton index）.SGPM-SAI通过对文本串预处理,建立一种称为W-SAM的图索引结构,然后对模式串分段查找EndPos集合,最后以集合归并求交的方法得到模式匹配的完备解.实验结果表明：在不考虑预处理时间的情况下,相比几种最典型的模式匹配算法（KMP,BM,AC,suffix array）,SGPM-SAI算法性能优势显著,至少高出3~5倍.通过与SAIL算法的最新优化版本（SAIL-Gen）进行比较,在稀疏间隙约束条件下,SGPM-SAI的性能要显著优于SAIL-Gen算法.此外,为有效利用现代处理器的大规模并行处理单元,提出了并行优化后的算法Parallel SGPM-SAI.实验结果表明：Parallel SGPM-SAI算法的加速效果显著,且具有良好的并行可扩展性,能够充分利用现代众核处理器的高并行计算优势.     

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

模式匹配在计算机应用中扮演着很重要的角色。通过分析BM,BMH和BMHS算法及相关改进算法,提出BMHS算法的改进算法(DBMHS)。该算法(DBMHS)充分利用模式串两端字符,通过比较模式串两端字符的跳转距离来实现更大距离的跳转。实验证明,改进后的算法显著增加了匹配窗口的跳转距离,有效地提高了匹配效率。     

BM模式匹配算法在中文应用中的改进

本文在BM（Boyer-Moore）模式匹配算法的基础上,利用中文字符出现频率不同的特点,改变字符比对的顺序,优先从低频字比对,减少比对次数,从而提高了中文搜索的效率。     

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

基于字符串匹配的检测方法是入侵检测系统中的一种重要方法。在分析了几种常见的字符串匹配算法（BF、KMP、BM、Sunday等）的基础上,提出了一种改进的字符串匹配算法——sundayNcw。该算法使每一次匹配不成功后都能跳过尽可能多的字符以进行下一轮匹配,并且匹配次数大大减少,从而提高了匹配效率。最后,分析了该算法的性能,并用具体的实验数据给出了几种匹配算法的测试结果。     

一种高效的模式匹配算法

在时Boyer-Moore(BM)算法进行分析的基础上,提出一种更加快速的模式匹配算法--EPM.在单模式匹配过程中,该算法通过模式匹配中最后字符位置的下个字符来确定偏移量,从而增大搜索步长.在多模式匹配过程中,通过在预处理阶段采用散列法来减小比较的模式数,提高匹配的速度.     

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

针对BM模式匹配算法的效率问题,提出其改进算法.分析BM模式匹配算法的原理,若文本串中连续的几个字符不在模式字符串中出现,则不需要被比对,以此改变模式字符串的匹配顺序,提高算法的匹配效率.实验结果表明,改进的BM模式匹配算法可以有效地减少字符串的匹配次数和比对次数,能获得良好的字符串匹配效率.     

对BM模式匹配算法的一种改进

模式匹配在入侵检测系统中有着广泛的应用。在对BM以及相关算法分析的基础上,提出了一种基于BM算法的改进算法。该算法同时运用BMH和BMHS算法的思想对模式进行移动,并利用了模式串末字符与首字符的组合性,缩短了比较过程,有效地减少了匹配过程中的字符比较次数。实验证明,该算法具有高的匹配效率。     

一种基于QS的字符串匹配改进算法

本文在分析BM和QS算法特点的基础上,综合利用了正文T[i m-1]和T[i m]位置上 的字符信息,提出一种移动距离不小于模式长度的快速字符串匹配算法。该算法解决了QS算法在 skip[i m-1]相似文献