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

PARA-AC:a high performance matching algorithm based on Aho-Corasick automaton

作　　者：熊仁都 杨嘉佳 朱广宇[1] 唐球 隋然 Xiong Rendu;Yang Jiajia;Zhu Guangyu;Tang Qiu;Sui Ran(North China Institute of Computer Systems Engineering,Beijing 100083,China;Information Center,Logistics Support Department,CMC,Beijing 100842,China)

机构地区：[1]华北计算机系统工程研究所,北京100083 [2]中央军委后勤保障部信息中心,北京100842

出　　处：《电子技术应用》2020年第11期87-90,95,共5页Application of Electronic Technique

摘　　要：原始AC自动机由于匹配性能低,无法满足当前大数据环境下大规模特征串实时匹配的应用需求。针对这一问题,提出一种基于多线程的多模式串匹配加速算法,称之为PARA-AC(Parallel Aho-Corasick automaton)。该算法将待匹配字符串切割成若干字符子串以及若干切割点边界字符集,并将字符子串、切割点边界字符集输入至线程池中进行匹配,从而实现字符串的并行化加速处理。实验结果表明,与原始AC自动机匹配算法相比,PARA-AC算法显著提高了匹配速度,约为原始AC的13.91倍。Due to low matching performance,the original AC automaton cannot meet the application requirements of real-time large-scale feature string matching under the current big data environment.To solve this problem,a accelerated multi-mode string matching algorithm based on multi-threading is proposed,which is called PARA-AC.The algorithm cuts the string to be matched into several character substrings and a number of boundary character sets.Then these character substrings and boundary character sets to be input to the pool of threads for matching.The experimental results show that the performance of the PARA-AC algorithm is 13.91 times better than that of the original AC matching algorithm.

关 键 词：多模式串匹配 AC自动机 多线程 并行化 

分 类 号：TP391.1[自动化与计算机技术—计算机应用技术]