%0 Journal Article
%T 一种基于位图的多模式匹配算法
%A 张元竞
%A 张伟哲
%J 哈尔滨工业大学学报
%P 277-280
%D 2010
%R 10.11918/j.issn.0367-6234.2010.02.022
%X 为降低自动机类多模匹配算法的空间开销,同时仍保持较低的算法时间复杂度,提出了一种基于位图的空间优化算法.将自动机全部状态按照字典树结构的层数划分,将访问频率较低的后若干层状态对应的转移表压缩存储,并使用位图提高对被压缩信息的检索速度.经过实验和在实际应用环境中的验证,这种改进算法能够大幅降低空间开销,而匹配时间或响应时间基本不变.在模式串的数量达到万条以上规模时,实验表明优化算法能够降低25%～70%的空间消耗.
%K 多模匹配
%K AC算法
%K 有限状态自动机
%K 位图
%U http://journal.hit.edu.cn/hitxb_cn/ch/reader/view_abstract.aspx?file_no=20100222&flag=1