一种基于位图的多模式匹配算法

• 作者: 张伟哲 张元竞
• 来源期刊: 哈尔滨工业大学学报
• 学科: 工学
• 关键词: 多模匹配 AC算法 有限状态自动机 位图
• 年，卷（期）: 2010,（2）
• 页码范围: 277-280
• 页数: 4页
• 分类号: TP311
• 语种: 中文

摘要

为降低自动机类多模匹配算法的空间开销,同时仍保持较低的算法时间复杂度,提出了一种基于位图的空间优化算法.将自动机全部状态按照字典树结构的层数划分,将访问频率较低的后若干层状态对应的转移表压缩存储,并使用位图提高对被压缩信息的检索速度.经过实验和在实际应用环境中的验证,这种改进算法能够大幅降低空间开销,而匹配时间或响应时间基本不变.在模式串的数量达到万条以上规模时,实验表明优化算法能够降低25%～70%的空间消耗.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张伟哲		37	798	15.0	28.0
2	张元竞		1	0	0.0	0.0