改进的AAC多模式实时匹配算法

• 作者: 史舒鹏 张晶 范洪博
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 改进的AC(AAC)算法 多模式 自动机 模式匹配
• 年，卷（期）: 2017,（3）
• 所属期刊栏目: 理论与研发
• 页码范围: 68-73
• 页数: 6页
• 分类号: TP39
• 字数: 4915字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.1605-0057

摘要

AAC算法(Advanced AC)是使用最为广泛的多模式串匹配算法,匹配性能高,匹配时间稳定.针对AAC算法为判定转移目标状态是否为终结状态,在匹配时每读入一个字符都要访问output表,代价较高的问题,通过两种方法改进了AAC算法.第一种方法为拷贝自动机中的终结状态,将其附加在AAC自动机后,并将原自动机中指向终结状态的转移目标修改为附加状态,直接根据转移目标位置判断当前状态是否是终结状态,从而提出Advanced AC with Additive state(AACA)算法.第二种改进方法为将自动机中指向终结状态的状态转移值置为负数,根据转移目标的值直接判断目标状态是否为终结状态,从而提出Advanced AC with Negative state(AACN)算法.以上两种改进算法只有在发现模式匹配时才需进行output表的访问.实验数据表明:AACA和AACN算法性能均高于AAC算法,特别在中小规模匹配上,性能提升更为明显.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张晶	昆明理工大学信息工程与自动化学院	60	174	8.0	9.0
2	范洪博	昆明理工大学信息工程与自动化学院	27	75	5.0	6.0
3	史舒鹏	昆明理工大学信息工程与自动化学院	1	1	1.0	1.0