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

摘要

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