PARA-AC：一种基于AC自动机的高性能匹配算法

被引：7

作者：

熊仁都 ^{[1
]}

杨嘉佳 ^{[1
]}

朱广宇 ^{[1
]}

唐球 ^{[1
]}

隋然 ^{[2
]}

机构：

[1] 华北计算机系统工程研究所

[2] 中央军委后勤保障部信息中心

来源：

电子技术应用 | 2020年 / 46卷 / 11期

关键词：

多模式串匹配; AC自动机; 多线程; 并行化;

D O I：

10.16157/j.issn.0258-7998.200096

中图分类号：

TP301.6 [算法理论];

学科分类号：

摘要：

原始AC自动机由于匹配性能低,无法满足当前大数据环境下大规模特征串实时匹配的应用需求。针对这一问题,提出一种基于多线程的多模式串匹配加速算法,称之为PARA-AC(Parallel Aho-Corasick automaton)。该算法将待匹配字符串切割成若干字符子串以及若干切割点边界字符集,并将字符子串、切割点边界字符集输入至线程池中进行匹配,从而实现字符串的并行化加速处理。实验结果表明,与原始AC自动机匹配算法相比,PARA-AC算法显著提高了匹配速度,约为原始AC的13.91倍。

引用

页码：87 / 90+95 +95

页数：5

共 6 条

[1] 一种基于Aho-Corasick算法改进的多模式匹配算法
陈永杰
吾守尔·斯拉木
于清
[J]. 现代电子技术, 2019, 42 (04) : 89 - 93
[2] FilterFA:一种基于字符集规约的模式串匹配算法
张萍
何慧敏
张春燕
曹聪
刘燕兵
谭建龙
[J]. 通信学报, 2016, (12) : 103 - 114
[3] 一种改进的AC多模式匹配算法
刘春晖
黄宇
宋琦
[J]. 计算机工程, 2015, 41 (10) : 280 - 285
[4] HybridFA:一种基于统计的AC自动机空间优化技术
熊刚
何慧敏
于静
刘燕兵
郭莉
[J]. 通信学报, 2015, 36 (07) : 31 - 39
[5] 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
[6] Efficient string matching[J] . Alfred V. Aho,Margaret J. Corasick.Communications of the ACM . 1975 (6)

← 1 →