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

• 作者: 李萍 沈璐 纪允 纪冬宝
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 模式匹配 通配符 动态规划 Aho-Corasick自动机
• 年，卷（期）: 2015,（15）
• 所属期刊栏目: 理论研究、研发设计
• 页码范围: 43-47,55
• 页数: 6页
• 分类号: TP39
• 字数: 5593字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.1308-0067

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	沈璐	合肥工业大学计算机与信息学院	13	6	2.0	2.0
3	纪允	合肥工业大学计算机与信息学院	4	15	3.0	3.0
6	纪冬宝		1	1	1.0	1.0
7	李萍	安徽林业职业技术学院信息与艺术系	1	1	1.0	1.0