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

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

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

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

改进的多模式匹配算法

在有限自动机的多模式匹配算法（DFSA算法）的基础上，结合Quick Search算法的优点，提出了一个快速的多模式字符串匹配算法，之后在算法中以连续跳跃的思想，给出了另一个更加有效的改进，在一般情况下，这两个算法不需要匹配目标文本串中的每个字符，并充分利用了匹配过程是本次匹配不成功的信息，跳过尽可能多的字符，在模式串较长和较短的情况下，算法都有很好的性能，实验表明，在模式串较短时，所提出的算法需要的匹配时间仅为DFSA算法的1／2到1／5，在模式串较长时，所需时间为DFSA算法的1／3至1／7。     

一种存储优化的多模式匹配算法

AC(Aho-Corasick)自动机是经典的多模式匹配算法,但在模式串字符集较大的情况下,AC自动机的存储开销较大。为降低存储开销提出了存储优化的多模式匹配算法SMMA,该算法在Trie树建立阶段利用正向表来存储每个状态的后续状态指针以及失配指针,而无需存储字符集所有字符的后继指针,从而压缩了每个状态的储存空间。实验表明,所提出的算法与AC自动机算法在时间效率上相近,但极大地降低了存储开销。     

一种基于反馈模糊图论的视频多语义标注算法

为了弥补视频语义检索中视频底层特征与高层语义概念之间的“语义鸿沟”,提出了一种基于反馈模糊图论的视频多语义标注算法。该算法首先构造一个包括所有数据的时间和空间分布信息的小样本集,据此进行人工标注并将其作为训练集。然后将模糊算子引入图论中,将语义概念间的关系模糊化,以实现模糊推理。最后将标注完成的测试集中的样本加入到训练集中,以完成视频标注的反馈。实验结果表明,使用反馈的模糊图不仅可以很好地建立语义概念间的关系,还能提高视频标注的准确率,表现出良好的性能。     

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

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

一种基于压缩矩阵的Apriori算法改进研究

针对已有基于矩阵的Apriori算法存在的问题,提出了一种改进的基于压缩矩阵的Apriori算法。算法进行了以下方面的改进:增加了两个数组,分别用于记录矩阵行与列中1的个数,使得算法在压缩矩阵时减少了扫描矩阵的次数;在压缩矩阵中,通过增加删除不能连接的项集和非频繁的项集的操作,使得矩阵压缩得更小,提高了空间效率;改变了删除事务列的条件和算法结束的条件,以减少挖掘结果的误差和算法循环的次数。算法性能分析和实验分析证明,改进后的算法能有效地挖掘频繁项集,并且比现有的算法具有更高的计算效率。     

基于有序二叉树的多模式匹配算法

一、简介在一个文本串中查找用户指定的模式串在信息抽取和文本编辑中有着广泛的应用。当前,有限状态自动机(DFSA)算法是解决多模式匹配问题的常用方法。DFSA算法在匹配前对模式串集合进行预处理,转换成树型有限状态自动机,然后只需对文本串进行一次扫描就可找出所有模式串,其查找时间复杂度是O(n)。后来,在这个算法的基础上又有一些改进,实现了跳跃式查找。基于树型结构的有限自动机特别适     

中文多模式匹配算法性能的分析与研究

模式匹配算法一般不具有所有环境下的通用性,不同的算法在不同语义环境下的表现,往往差异较大。为实现中文环境下对模式串的快速多模式匹配,选择出在中文环境下的最优匹配算法,分析了几种经典的多模式匹配算法。通过对各个算法设计思路、时间性能与空间性能的研究,推导出基于“坏字符”的算法设计思路最适用于中文环境下大字符集、短字符串的特点,并通过实验对理论推测的中文环境最优算法-Wang算法的性能与其他几种经典算法的性能进行了比较,验证了理论推导的正确性。     

一种定向式挖掘的连续域蚁群算法

针对蚁群算法在求解连续域优化问题时存在复杂度较大、迭代次数较长等问题,提出了一种用于连续域寻优的改进蚁群算法。改进的蚁群算法通过对解空间定向式挖掘来实现全局快速搜索。给出了新算法仿真实验步骤,并将改进后的蚁群算法与其他连续域蚁群算法以及其他智能优化方法进行仿真对比实验。详细的测试结果表明,改进后算法具有优良的全局优化性能,收敛速度也有很好的提升。     

AC多模式匹配算法研究

AC算法的内存空间开销大,不利于硬件实现。为此,提出AC多模式匹配算法。分析AC算法的特点,使用位图存储技术和压缩处理技术对其进行改进。从模式串长度和模式串数目角度出发进行实验,结果表明,该算法能缩短扫描时间,提高模式匹配速度和访问速度。     

一种基于有序二叉树的多模式匹配算法

传统的多模式匹配算法是用树型结构的有限自动机实现的 ,它具有很多缺点 .本文提出的多模式匹配算法是基于有序二叉树的多模式匹配算法 .实验证明 ,本文算法不但具有和传统算法相当的查找速度 ,而且构造速度快、内存耗费少 .因此 ,本文提出的算法特别适用于要求动态构造自动机的情况     

一种新的快速多模式匹配算法

在实际网络中,入侵数据包只占网络总流量的极少一部分.系统资源的消耗主要不是在对入侵包的检测,而是在对正常数据包的穷举匹配.针对这一实际情况,提出并实现了一种新的匹配算法.该算法采用两次匹配的思想,大幅度地提高了系统的检测速率.     

一种高效的多模式字符串匹配算法

在Fan-Su(FS)多模式字符串匹配算法基础上,结合BM-Horspool(BMH)算法和Quick Search(QS)算法的优点,提出一种高效的多模式字符串匹配算法。该算法能够充分利用本次匹配失败和部分匹配成功的信息,一方面增加模式树根节点失配的概率,提高匹配过程中失配时的跳跃距离。另一方面避免不必要的状态转移,实现不匹配时的连续跳转。分析指出,在最好情况和平均情况下,时间复杂度均优于ACBM算法和FS算法。实验结果表明,一般情况下该算法的查找时间仅为AC算法的10%~35%,ACBM算法的50%~60%,FS算法的70%左右,FSQB算法的65%左右。     

改进的模式匹配算法在入侵检测中的应用

随着网络技术的高速发展,网络安全问题日益突出,入侵检测技术成为当今关注的焦点。模式匹配算法的性能对入侵检测系统影．响很大。在分析现有模式区配算法的基础上,提出了改进的AC_BM算法,该算法在文本与模式某次匹配失败后,跳过尽可能多的字符,实现更快的匹配过程。实验证明,改进后的算法大大提高了检测的性能。     

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

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

入侵检测多模式匹配算法

基于模式匹配的入侵检测是目前最重要的一种入侵检测方法,面字符串匹配效率是该方法的核心,直接影响检测效率。该文在充分分析BM算法、AC算法及AC_BM算法的基础上提出了一种新的更好搜索步长的多模式匹配算法NMSA,并具体分析了该算法的效率,通过实验数据对比,再次证明NMSA算法具有更好的搜索步长、更好的效率。     

一种改进的多模式匹配算法在Snort中的应用

模式匹配算法是入侵检测系统的重要组成部分。为进一步提高入侵检测系统的性能和效率,提出一种新的多模式匹配算法——完全自动机匹配算法(CA-AC算法),并将其应用于入侵检测系统Snort中。该算法是对Aho-Corasick算法的改进,根据新算法进行状态转换使得自动机状态减少,相应节约了存储空间。分析了算法的复杂度。实验表明,完全自动机算法在Snort中的应用改进了算法的性能,提高了Snort系统的规则检测效率。