Aho—Corasick算法与Boyer—Moore算法

在网络安全的研究过程中，字符串匹配是一种非常很重要的技术，很多杀毒软件的特征码匹配，都需要用到字符串匹配。字符串匹配是计算机科学中最古老、研究最广泛的问题之一。本文对多模式字符匹配的两种关键算法Aho—Corasick算法与Boyer—Moore算法进行讨论。

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

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

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

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

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

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

一种基于分类存储的空间高效Aho-Corasick算法

针对经典Aho-Corasick算法存在空间开销大,存储效率低的问题,提出一种改进的空间高效Aho-Corasick算法。新算法在预处理阶段根据状态转移函数、输出函数的不同特性,灵活选择不同的方式存储状态结点,实现对Aho-Corasick算法状态机的压缩。实验表明,新算法与经典Aho-Corasick算法、Bitmapped AC算法相比,以匹配阶段较小的时间性能为代价,极大幅度地压缩状态机的存储空间。

植物源天然产物AHO对番茄斑萎病毒属病毒病的田间防效

【目的】评价植物源天然产物3-丙酮基-3-羟基羟吲哚(3-acetonyl-3-hydroxyoxindole,AHO)对田间番茄斑萎病毒属病毒病的防控效果,为AHO开发成为新的抗病毒剂提供科学依据。【方法】选取5%AHO水剂和生产中常用的7种抗病毒剂(超敏蛋白、氨基寡糖素、盐酸吗啉胍、吗呱乙酸铜、宁南霉素、啸克、苯并噻二唑)在烟株移栽还苗后进行叶面喷施3次,药后调查烟株病毒病发生情况。【结果】供试药剂中除啸克外对大田烟株番茄斑萎病毒属病毒病均有很好的防控效果,连续施用3次后可较好地控制烟田番茄斑萎病毒属病毒病的发生和发展,其中,AHO对番茄斑萎病毒属病毒病的相对防效为79.86%,略低于宁南霉素的相对防效(80.60%);苯并噻二唑的相对防效最高,达83.75%;氨基寡糖素和吗呱乙酸铜的相对防效相当,分别为71.72%和72.67%;超敏蛋白和盐酸吗啉胍的相对防效稍低,分别为68.55%和67.82%;啸克的相对防效最低,仅为44.78%。【结论】AHO对大田烟株番茄斑萎病毒属病毒病有很好的防控效果,其对番茄斑萎病毒属病毒病的效果优于部分市售药剂,具有开发成为防控番茄斑萎病毒属病毒病抗病毒剂的潜力。

“AHO+多肽保”组合剂诱导不同烤烟品种抗TMV的效果

对不同烤烟品种施用"AHO+多肽保"组合防控剂,比较"AHO+多肽保"组合防控剂诱导不同烤烟品种抗TMV效果的差异.结果显示:"AHO+多肽保"组合剂诱导不同品种抗TMV的效果差异有统计学意义;对红大的诱导效果最好,云87次之,再次是K326,对云97和KRK26的诱导效果最差.相关性分析结果显示:不同品种移栽前发病率和苗期带毒率呈显著正相关;不同品种大田移栽后病情指数与苗期带毒率也呈显著正相关.

AHO刀柄的性能及定位精度分析

系统分析了AHO刀柄的结构及性能特点。对AHO刀柄和BT刀柄的轴向定位精度以及径向定位精度进行了详细的分析比较。分析结果表明,AHO刀柄具有很高的轴向重复定位精度和径向重复定位精度。

夹紧力对AHO工具系统径向刚度的影响

在不同夹紧力条件下,对AHO工具系统的径向刚度进行了有限元模拟与分析,获得了其径向位移端面间隙变化的具体数据。分析结果表明,足够大的夹紧力和双面接触是保证AHO工具系统高径向刚度的关键。

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

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

入侵检测中一种节约内存的多模式匹配算法

模式匹配既是网络入侵检测系统(NIDS)的关键,也是NIDS中消耗资源最多的部分。随着网络速度和入侵检测规则的持续增长,模式匹配正在成为NIDS的性能瓶颈。提出了一种基于非确定有限自动机结构的Aho-Corasick算法,通过压缩状态表,把状态和状态变迁存储在一个单一向量中,显著降低了内存需求,获得了良好的cache性能。测试表明,与其他Aho-Corasick算法相比,MEAC的内存消耗平均减少了92.3%～98.4%,同时保持了Aho-Corasick算法的良好性能。

一种基于关键字树的DNA数据库搜索算法

针对BLAST等软件在生物数据库中搜索DNA分子序列时,不能兼顾时间开销和搜索敏感性的问题,提出一种基于关键字树的多种子搜索算法。首先将查询序列分割成多个种子并将它们构建成一棵关键字树;然后利用Aho-Corasick算法在数据库中搜索,找到每个种子的所有完全匹配;最后检查种子匹配密度大的区域,确定其是否是查询序列的近似出现。实验表明算法兼顾了时间开销和搜索的敏感性,而且能发现基因序列中的移位现象.

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

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

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

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

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

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

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

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

AC多模式匹配算法研究

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

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

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

基于Trie树的哈希表

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