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

被引：4

作者：

熊刚 ^{[1
]}

何慧敏 ^{[2
]}

于静 ^{[1
]}

刘燕兵 ^{[1
]}

郭莉 ^{[1
]}

机构：

[1] 中国科学院信息工程研究所

[2] 中国移动(深圳)有限公司

来源：

通信学报 | 2015年 / 36卷 / 07期

关键词：

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

D O I：

暂无

中图分类号：

TP301.1 [自动机理论];

学科分类号：

摘要：

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

引用

页码：31 / 39

页数：9

共 4 条

[1] 基于存储优化的多模式串匹配算法
刘燕兵
刘萍
谭建龙
郭莉
[J]. 计算机研究与发展, 2009, 46 (10) : 1768 - 1776
[2] Fast and flexible string matching by combining bit-parallelism and suffix automata[J] . Gonzalo Navarro,Mathieu Raffinot. Journal of Experimental Algorithmics (JEA) . 2000
[3] OPTIMIZATION OF PARSER TABLES FOR PORTABLE COMPILERS
DENCKER, P
DURRE, K
HEUFT, J
[J]. ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 1984, 6 (04): : 546 - 572
[4] Efficient string matching[J] . Alfred V. Aho,Margaret J. Corasick. Communications of the ACM . 1975 (6)

← 1 →