基于异构隐式存储的多模式匹配算法

• 作者: 张汝波 李志东 杨武 王巍
• 来源期刊: 通信学报
• 学科: 工学
• 关键词: 多模式匹配 紧缩存储 扇出压缩 路径压缩 事件定位
• 年，卷（期）: 2009,（3）
• 所属期刊栏目: 技术报告
• 页码范围: 119-124
• 页数: 6页
• 分类号: TP301
• 字数: 5079字
• 语种: 中文
• DOI: 10.3321/j.issn:1000-436X.2009.03.019

摘要

提出了紧缩存储型Aho-Corasick算法变体,以异构的按需隐式存储取代同构的例行显式存储,从横向扇出压缩与纵向路径压缩2个方向入手,围绕着压缩稀疏事件表展开,当字符集大小σ=256时可将存储量缩减为原来的0.69%左右,而σ＝64K时则达0.004%,即空间复杂度降为原来的(1bσ)/σ左右.依据扇出疏密程度的不同,分类采用了4种有针对性的快速事件定位方法,加之优化的失败迁移,使得存储量的大幅缩减不以速度的明显损失为代价,实验也证实了这一点.适用于需承载大型模式集和较长模式串而对时延和抖动都比较敏感的场合(如在线数据流过滤),在宽字符(如UNICODE型亚洲字符)匹配方面拥有显著优势.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张汝波	哈尔滨工程大学信息安全研究中心	110	1870	20.0	39.0
2	王巍	哈尔滨工程大学信息安全研究中心	78	697	13.0	22.0
3	杨武	哈尔滨工程大学信息安全研究中心	41	572	13.0	22.0
4	李志东	哈尔滨工程大学信息安全研究中心	9	47	4.0	6.0