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

• 作者: 方贤进 李龙澍
• 来源期刊: 科技与创新
• 关键词: 多模式匹配 Aho-Corasick算法 稀疏存储
• 年，卷（期）: 2007,（9）
• 所属期刊栏目: 软件时空
• 页码范围: 211-213
• 页数: 3页
• 分类号: TP3
• 语种: 中文
• DOI: 10.3969/j.issn.1008-0570.2007.09.084

摘要

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