基于异构隐式存储的多模式匹配算法
提出了紧缩存储型Aho-Corasick算法变体,以异构的按需隐式存储取代同构的例行显式存储,从横向扇出压缩与纵向路径压缩两个方向入手,围绕着压缩稀疏事件表展开,当字符集大小σ=256时可将存储量缩减为原来的0.6906左右,而σ=64K时则达0.004％,即空间复杂度降为原来的(1092σ)／σ左右。依据扇出疏密程度的不同,分类采用了四种有针对性的快速事件定位方法,加之优化的失败迁移,使得存储量的大幅缩减不以速度的明显损失为代价,实验也证实了这一点。适用于需承载大型模式集和较长模式串而对时延和抖动都比较敏感的场合(如在线数据流过滤),在宽字符(如IJNICODE 型亚洲字符)匹配方面拥有显著优势。
多模式匹配 存储量 扇出压缩 路径压缩 事件定位
李志东 杨武 张汝波 王巍 张乐君
哈尔滨工程大学信息安全研究中心,黑龙江 哈尔滨 150001
国内会议
深圳
中文
32-38
2008-04-07（万方平台首次上网日期，不代表论文的发表时间）