FilterFA:一种基于字符集规约的模式串匹配算法

被引：4

作者：

张萍 ^{[1
,2
,3
]}

何慧敏 ^{[4
]}

张春燕 ^{[1
,3
]}

曹聪 ^{[1
,3
]}

刘燕兵 ^{[1
,3
]}

谭建龙 ^{[1
,3
]}

机构：

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

[2] 中国科学院大学

[3] 信息内容安全技术国家工程实验室

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

来源：

通信学报 | 2016年 / 12期

关键词：

入侵检测; 多模式串匹配; 字符集规约; 字符集映射;

D O I：

暂无

中图分类号：

TP391.1 [文字信息处理];

学科分类号：

摘要：

多模式串匹配技术是入侵检测系统的核心技术之一,Aho-Corasick算法广泛应用于其中。针对AC自动机内存开销巨大影响算法性能的问题,提出一种基于字符集规约的改进算法——FilterFA。利用字符集映射函数将原字符集压缩为多个像字符集,针对像字符集构造新的自动机FilterFA,将空间复杂度降至O(P|Σ′|)。在随机数据集和真实数据集ClamAV上的测试结果表明,当像字符集大小为8,且保证误识别率小于2%时,FilterFA算法消耗的存储空间仅为AC算法的3%左右。

引用

页码：103 / 114

页数：12

共 9 条

[1] HashTrie:一种空间高效的多模式串匹配算法
张萍
刘燕兵
于静
谭建龙
[J]. 通信学报 , 2015, (10) : 172 - 180
[2] 串匹配算法中的自动机紧缩存储技术
杨毅夫
刘燕兵
刘萍
郭莉
[J]. 计算机工程, 2009, 35 (21) : 39 - 41
[3] Compact representation of Web graphs with extended functionality[J] . Nieves R. Brisaboa,Susana Ladra,Gonzalo Navarro. Information Systems . 2014
[4] 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
[5] Storing a Sparse Table with 0 (1) Worst Case Access Time[J] . Michael L. Fredman,János Komlós,Endre Szemerédi. Journal of the ACM (JACM) . 1984 (3)
[6] STORING A SPARSE TABLE
TARJAN, RE
YAO, ACC
[J]. COMMUNICATIONS OF THE ACM, 1979, 22 (11) : 606 - 611
[7] A fast string searching algorithm[J] . Robert S. Boyer,J. Strother Moore. Communications of the ACM . 1977 (10)
[8] Efficient string matching[J] . Alfred V. Aho,Margaret J. Corasick. Communications of the ACM . 1975 (6)
[9] Flexible pattern matching in strings: practical on-linesearch algorithms for texts and biological sequences .2 Navarro G,Raffinot M. Cambridge UniversityPress . 2002

← 1 →