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