基于Aho-Corasick算法的多模式匹配算法研究

通过分析模式匹配算法在网络入侵检测中的重要作用和所面临的问题,对Aho-Corasick基于自动机的算法和以Aho-Corasick算法为基础的相关算法进行了分析,并通过实验对多种多模式匹配算法进行综合对比,最后对多模式匹配方法的发展趋势进行了展望。

面向入侵检测的Aho-Corasick算法内存消耗研究

多模式匹配算法在网络入侵检测系统中有着广泛的应用,目前的研究主要集中在如何提高算法的匹配速度上,对于算法的内存消耗研究较少。对于基于硬件实现的嵌入式入侵检测而言,如何降低多模式匹配算法的内存消耗也是一个值得关注的问题。Aho-Corasick(AC)算法是一个基于有限状态机的多模式匹配算法,该算法具有O(n)的时间复杂度,但是由于状态表存储开销较大使其难以应用到嵌入式入侵检测系统中。对AC算法的内存消耗进行了深入地研究,分析了几种可行的AC有限状态机存储策略,提出了一种改进的Banded-Row格式的AC有限状态机存储策略。实验结果表明,该策略能够在较小地影响AC算法匹配速度的前提下,更加有效地降低其内存消耗。

基于Aho-Corasick自动机算法的概率模型中文分词CPACA算法

Aho-Corasick自动机算法是著名的多模式串匹配算法,它在模式串失配时,通过fail指针转移至有效的后续状态,存在一个或多个有效的后续状态可能。据此特性,该文提出了一种适应于中文分词的自动机算法。该算法使用动态规划的方法,计算上下文匹配概率,转移至最佳的有效后续状态,即实现了基于字符串匹配的机械分词方法与基于统计概率模型的方法结合。实验结果表明,该算法分词准确率高。

基于知识图谱的海洋中药智能问答系统的设计与实现

目的当前公众对海洋中药信息了解不足,且缺乏海洋中药相关知识服务工具,为解决这一问题,研究开发海洋中药智能问答系统,为公众提供海洋中药知识查询工具。方法以前期构建的细粒度海洋中药知识图谱MMKG为知识库,综合利用Aho-Corasick、Word2Vec等算法获取海洋中药实体,从专业角度提出了一种细粒度海洋中药问题分类方法,构建海洋中药智能问答系统(MMKGQA)。结果通过问卷调查的问题语料测试,本系统在回答海洋中药常见6大类问题的平均精确率、平均召回率、平均F1值分别为97.93%、83.41%、89.10%,表明本系统能很好回答海洋中药的相关问题,具有较高的实用性和可行性。结论本系统可以帮助普通用户获取海洋中药的科普知识,为海洋中药研发人员的相关知识获取提供一种有效的知识服务工具,助力海洋新药研发。

多模式匹配算法及硬件实现

介绍了多模式匹配的算法和硬件实现方法.首先介绍了两种常用的多模式匹配算法——Aho-Corasick基于自动机的算法和Wu-Manber基于hash的后缀匹配加移位跳跃的算法以及相关的改进算法.并通过实验对各种多模式匹配算法的时空复杂度进行了分析比较.通过几个硬件实现的实例介绍了多模式匹配的硬件实现方法及策略.最后对多模式匹配的发展趋势进行了展望.

基于关键字树的DNA多序列星比对算法

在构建进化树、比较单体型序列等生物信息学研究中,需要比对多个相似程度很高的DNA序列.对于数量多、序列长的多序列比对问题,通常使用时间复杂度较低的星比对算法.然而在处理大规模数据时,星比对的平方时间复杂度依然不能满足需要.因此,在星比对思想的基础上,本文结合关键字树理论,先找出完全匹配的区域,然后比对剩余区域,以达到降低期望时间复杂度的目的.两组实验证明了本文算法的有效性,在取得相同比对效果的情况下,本文算法运行时间小于其他方法.

入侵检测中模式匹配算法的性能分析

模式匹配算法在入侵检测中有着广泛的应用,它直接影响到入侵检测系统的实时性能。论文主要研究了Boyer-Moore算法,ModifiedWu-Manber算法,Exclusion-Based算法和Aho-Corasick算法。通过实验对上述四种算法在混合攻击和特定攻击的条件下进行了性能测试,根据实验结果,得出了不同算法的应用范围,为今后入侵检测系统开发者选择模式匹配算法提供了有价值的参考。

基于距离比较的AC自动机并行匹配算法

随着网络带宽的快速增长,作为网络安全设备核心模块的多模式匹配(MPM)算法面临严峻的性能挑战。该文提出一种高效的数据包分割和并行匹配算法—距离比较并行匹配算法(DCPM)。和已有方法相比,并行的DCPM线程间不存在同步开销,引入的冗余检测开销达到理论最小。基于Aho-Corasick(AC)算法,在8核处理器平台上将DCPM算法与已有的数据包分割方法进行了性能比较。实验结果表明,和已有方法相比,DCPM算法的适应性更好,性能受网络流量中模式串占比、模式串长度及自动机状态数等因素的影响更小;在处理真实数据集时,DCPM算法的加速比提升1.3~3.5倍。

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

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

智能遥感卫星数据记录系统技术研究

本文针对传统遥感卫星数据记录系统需要人工输入工作计划的现状,以及无人职守工作模式的需求,提出一种智能化记录系统技术的解决方案。本方案主要采Aho-Corasick算法,通过搜索下行数据帧同步字的方法,区分卫星数据与无用信号;通过给定策略实现对记录系统起停的控制;通过给定任务需求策略,自动记录和传输有用卫星数据。本系统基于Aho-Cora-sick算法实现了识别20余颗卫星的能力。设计时采用Aho-Corasick算法作为帧同步字信号的盲搜或引导,一旦"锁定"卫星后则采用查找表的算法,提高了系统处理速度。实现后的记录系统仅需人工配置目标星和工作时间段等信息,之后运行工作可无人职守。

带可变长度通配符的模式匹配算法

针对目前已有的算法在计算带有可变长度通配符的模式在文本中的出现次数问题时,需要的时间是多项式级别,而且受文本长度、模式长度和通配符间距的影响比较大。提出了一种基于Aho-Corasick自动机的AAI(pAttern mAtching with wIldcards)算法,计算中采用了动态规划思想和有效的修剪技术。AAI算法的时间复杂度和空间复杂度分别为O(n+m+α)和O(m+B),其中n和m分别表示文本和模式的长度,α是所有子模式在文本中出现的数目,B是模式中通配符间距下限的总和。通过真实数据和人工数据的实验结果表明,AAI算法与同类算法相比具备显著的优势。

模式匹配技术在多序列比对中的应用

多序列比对一直是生物信息学中尚未解决的一个NP难题。在星比对算法和AhoCorasick算法的基础上,深入分析基于关键字树的DNA多序列比对算法,提出了一种新的多序列比对算法——基于模式匹配的DNA多序列比对算法。实验结果表明该算法是有效的。

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

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

基于GPU的AC模式匹配改进算法

字符串匹配算法的应用非常广泛,在信息检索、信息安全等领域都起着关键的作用。近年来,由于GPU通用计算的高速发展,且GPU具有很强的并行计算能力和很高的存储器访问带宽,利用GPU来加速字符串匹配算法吸引了越来越多的关注。提出的改进的AC模式匹配算法,在对前人工作的基础上,进一步消除了output表的存储,将纹理存储器中的查表操作转换为数值比较操作,与改进前算法相比,速度提高了80%以上;进一步的,引入了多个可变参数,提高AC算法的有效数据匹配率,并优化线程块的大小,优化后的算法与采用一种特殊匹配方式的高效的PFAC算法相比,速度提高了9%以上。

面向入侵检测的模式匹配算法研究

在入侵检测系统的实现中,关键部分是检测引擎的实现。而在检测引擎的实现中,关键的是数据分析模块。对于基于规则的入侵检测来说,模式匹配算法非常重要,它直接影响到系统的准确性和实时性能。论文主要研究了BruteForce算法,Boyer-Moore算法,Aho-Corasick算法,Set-wiseBoyer-Moore-Horspool算法,Aho-Corasick_Boyer-Moore算法。

AC多模式匹配算法研究

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

基于Trie树的哈希表

受到AC算法与链式哈希的启发,提出了一种基于Trie树的哈希表。该算法通过增加一个后继状态计数器,能够为后续的查找等运算提供更加简单和快速的信息。分析与实验表明该算法具有较高的效率、较强的稳定性,且降低了能耗。

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

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

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

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

入侵检测中的快速过滤算法

入侵检测系统是近年来发展迅速的一种网络安全技术。但是，随着计算机网络向着高速、宽带的方向发展，检测引擎越来越成为性能的瓶颈。如果检测速度不能跟上网络流量，就会丢包并发生漏报。这除了采用更高速的专业硬件来解决外，包过滤算法也有非常重要的作用。高速的过滤算法有助于过滤掉大量无关的信息，从而极大地提高入侵检测系统的性能。