贾泂

基本信息Personal Information

教授

性别 : 男

毕业院校 : 复旦大学计算机系

在职信息 : 在岗

所在单位 : 计算机科学与技术学院

入职时间 : 1987年08月01日

扫描关注

论文成果

当前位置: 中文主页 >> 科学研究 >> 论文成果

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

点击量 :

第一作者 : 陈新驰

发表时间 : 2012-01-01

发表刊物 : 计算机工程

所属单位 : 数理与信息工程学院

文献类型 : 期刊

期号 : 第11期

页面范围 : 173-176

ISSN : 1000-3428

关键字 : 模式匹配;自动机;动态规划;Trie树

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

是否译文 :

推荐此文