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

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

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

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

网络信息审计系统中的多模式相似匹配算法

针对网络信息审计系统的需要,提出一种新颖的基于Episode距离的快速多模式相似串匹配算法.该算法把模式串集合转换为多个有限自动机,然后利用模式串集合建立一个状态驱动器.依次用待匹配串的字符驱动状态驱动器,由状态驱动器驱动各个有限自动机,实现了中英文混合的允许插入错误的相似多模式匹配.该算法不需要匹配每个字符,能充分利用匹配过程中本次匹配不成功的信息并结合改进的文本窗机制,跳过尽可能多的字符;能够控制每个模式串的允许错误上限;匹配速度与允许插入的错误字符教k无关.该算法在信息审计、数据库、信息检索等领域有     

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

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

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

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

多模式匹配算法的优化研究

模式匹配技术有着广泛的应用且模式匹配算法已经被研究了很多年,同时对稀疏存储及其结构的操作也有大量的文献资料。本文首先描述了Aho-Corasick多模式匹配算法,该算法是基于自动机及状态向量的,然后提出了使用banded-row稀疏存储对Aho-Corasick算法中的状态转换表进行存储优化的观点,给出了优化算法。最后给出了和原Aho-Corasick算法相比较的测试结果,该结果表明在大模式集的情况下,使用banded-row稀疏存储的Aho-Corasick算法减少了存储需求,进一步地提高了性能。     

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

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

改进的多模式匹配算法

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

一种基于有限自动机的快速串匹配算法

串匹配是字符串的基本操作之一,因此为它设计一个高效算法具有一定意义.文中基于有限自动机理论,在对经典的K.M.P.算法进行分析的基础上,提出了一种快速的串匹配算法.该算法利用自动机的状态转换表实现串匹配,避免了扫描字符串时的失败链回溯,从而加快了算法的运行速度.理论分析与实验结果均表明,在正文串比较长,模式串中局部匹配失败时失败链反馈较多的情况下,该算法在速度上明显优于K.M.P.算法.但在空间复杂度上,该算法需要较多的存储空间.     

一种快速的基于BM模式匹配的改进算法

模式匹配算法是入侵检测系统(IDS) 中非常重要的一种算法. 在研究和分析几种常用模式匹配算法的基础 上, 提出一种快速的基于BM(Boyer-Moore) 模式匹配的改进算法—–IBM 算法. 该算法充分利用模式串的末字符和 末字符所对应的文本串的后两字符的唯一性, 同时参考文本串本身的信息来提高模式串的移动量, 使得每次失配后, 在保证不丢失匹配成功可能性的前提下尽可能多地向后跳跃. 实验结果表明, 该算法相比其他模式匹配算法, 在检测 性能和匹配效率上均具有很大优势, 并且能够有效地提高IDS 的检测效率和性能.

     

多模式匹配算法的优化研究

模式匹配技术有着广泛的应用且模式匹配算法已经被研究了很多年，同时对稀疏存储及其结构的操作也有大量的文献资料。本文首先描述了Aho—Corasiek多模式匹配算法，该算法是基于自动机及状态向量的，然后提出了使用banded—row稀疏存储对Aho—Corasick算法中的状态转换表进行存储优化的观点，给出了优化算法。最后给出了和原Aho—Corasick算法相比较的测试结果，该结果表明在大模式集的情况下，使用banded—row稀疏存储的Aho—Corasick算法减少了存储需求，进一步地提高了性能。     

新的自适应多串匹配算法

在不同关键词规模、最短关键词长度和字符集大小等情况下,有效的多串匹配算法是不同的。新提出的自适应多串匹配算法（Adapted Multiple Strings Matching Algorithm,AMSM）改善了SBOM算法中Oracle树存在不精确跳跃计算的缺点,同时采用了WuManber算法的块跳跃策略和压缩形式的Oracle树比较策略,提高了算法的性能,可适用于各种情况,是一种通用多串（多模式）匹配算法。     

一种快速高效的模式匹配算法的应用研究

提出一种高性能的模式匹配算法——MAC算法,它通过使用从确定性有限状态机（DFA）中得到的特征等同态,在保证高速匹配的前提下,极大地减少了内存需求。同时,该算法具有高度的灵活性,即通过调整就可以适应不同的特定性能和资源限制的要求。在软件使用环境中的实验结果表明,MAC算法的内存使用性能相对目前先进的模式匹配算法提高了1.51~2.40倍。     

多模式匹配算法的FPGA实现

针对目前模式匹配算法多采用软件实现,而软件实现效率低下的弊端,提出了一种基于硬件实现模式匹配算法的设计方案.综合Aho-Corasick(AC)算法原理和FPGA硬件特点,在FPGA上实现AC算法;然后利用Quartus Ⅱ对设计进行了验证和性能分析.实验结果表明,基于硬件实现的Aho-Corasick(AC)算法的效...     

面向移动终端的URL过滤方法

在移动终端内容安全检测中,“黑名单”过滤是一种常用的手段,但有限的存储空间制约了它的应用。根据“黑名单”过滤特点研究了一种多串匹配算法的改进,以Aho-Corasick算法为例,采用两种启发式策略从不等长的URL串中提取具有代表性的、等长的模式子串,并使用双数组进一步压缩。在Nokia 5230上的测试表明,该算法的存储空间是经典AC算法的0.7%,而速度可达到95%以上。     

基于FSA的DNA重复体频率统计算法

针对现有DNA重复体频率统计算法效率低、灵活性差等不足,基于字符串多模式匹配的有限状态自动机,构造DNA子序列比对自动机,利用KMP算法对自动机进行状态转移优化,由此提出一种高效的重复体频率统计算法。该算法通过对DNA数据库的线性扫描,得到每个DNA子序列在全局数据库中重叠与非重叠的重复体频率统计信息以及指定DNA序列集合的最长公共子序列信息。实验结果表明,该算法具有效率高、匹配精确、信息获取方式灵活、支持在线操作等优势。     

AC多模式匹配算法研究

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

Augmenting the aho-corasick pattern matching machine

The Aho-Corasick algorithm is a well-known method of determining the occurrences of one of several given pattern strings in a given text string. We address the question of augmenting the pattern matching machine constructed by this algorithm with a new pattern string, both on-line and off-line. We show that augmenting a machine of N nodes with a new pattern string of length m takes Θ(mN) time on-line and Θ(N) time off-line.