HybridFA:一种基于统计的AC自动机空间优化技术

摘要：

针对高级Aho-Corasick (AC)自动机为提高串匹配速度而造成的空间浪费问题,研究发现数据流对自动机节点的访问规律,据此提出基于数据访问特征的混合自动机构建算法HybridFA.分别研究了基于访问频率、访问层次以及结合上述2种特征对AC自动机的部分节点实现完全化的算法.在Snort、ClamAV、URL等真实数据集上的实验结果表明,HybridFA算法的存储空间低于高级AC自动机的5％.此外,结合访问频率和访问层次的改进算法在保证匹配速度的同时具有更强的数据适应性.

关键词：多模式串匹配、空间优化、高级AC自动机、统计策略、节点完全化

所属期刊栏目：36

分类号：TP301.1(计算技术、计算机技术)

资助基金：中国科学院战略性科技先导专项基金资助项目XDA06030602;国家高技术研究发展计划“863”计划基金资助项目2011AA010703;国家自然科学基金青年基金资助项目61202477The Strategic Priority Research Program of the Chinese Academy of SciencesXDA06030602;The National High Technology Research and Development Program of China 863 Program2011AA010703;The National Natural Science Foundation of China61202477

在线出版日期：2015-09-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：31-39