PARA-AC：一种基于AC自动机的高性能匹配算法
2020年电子技术应用第11期
熊仁都1，杨嘉佳1，朱广宇1，唐 球1，隋 然2
1.华北计算机系统工程研究所，北京100083；2.中央军委后勤保障部 信息中心，北京100842
摘要： 原始AC自动机由于匹配性能低，无法满足当前大数据环境下大规模特征串实时匹配的应用需求。针对这一问题，提出一种基于多线程的多模式串匹配加速算法，称之为PARA-AC(Parallel Aho-Corasick automaton)。该算法将待匹配字符串切割成若干字符子串以及若干切割点边界字符集，并将字符子串、切割点边界字符集输入至线程池中进行匹配，从而实现字符串的并行化加速处理。实验结果表明，与原始AC自动机匹配算法相比，PARA-AC算法显著提高了匹配速度，约为原始AC的13.91倍。
中图分类号： TP391.1
文献标识码： A
DOI：10.16157/j.issn.0258-7998.200096
中文引用格式： 熊仁都，杨嘉佳，朱广宇，等. PARA-AC：一种基于AC自动机的高性能匹配算法[J].电子技术应用，2020，46(11)：87-90，95.
英文引用格式： Xiong Rendu，Yang Jiajia，Zhu Guangyu，et al. PARA-AC：a high performance matching algorithm based on Aho-Corasick automaton[J]. Application of Electronic Technique，2020，46(11)：87-90，95.
文献标识码： A
DOI：10.16157/j.issn.0258-7998.200096
中文引用格式： 熊仁都，杨嘉佳，朱广宇，等. PARA-AC：一种基于AC自动机的高性能匹配算法[J].电子技术应用，2020，46(11)：87-90，95.
英文引用格式： Xiong Rendu，Yang Jiajia，Zhu Guangyu，et al. PARA-AC：a high performance matching algorithm based on Aho-Corasick automaton[J]. Application of Electronic Technique，2020，46(11)：87-90，95.
PARA-AC：a high performance matching algorithm based on Aho-Corasick automaton
Xiong Rendu1，Yang Jiajia1，Zhu Guangyu1，Tang Qiu1，Sui Ran2
1.North China Institute of Computer Systems Engineering，Beijing 100083，China； 2.Information Center，Logistics Support Department，CMC，Beijing 100842，China
Abstract： 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.
Key words : multi-mode string matching；Aho-Corasick automaton；multi-threading；parallelization
0 引言
模式串匹配的作用是给定一组特定的字符串集合 S={s1，s2，…，sm}，对于任意一个字符串T=t1t2…tn，找出S中所有字符串在T中出现的位置[1]。基于Aho-Corasick(AC)自动机的模式串匹配算法在当前的串匹配算法中占据着重要地位，它以Trie树为基础，通过fail指针来实现状态匹配失效的过程跳转，保持了较为稳定的匹配性能。因此，基于AC自动机的串匹配算法在字符串搜索、生物特征识别、网络安全等领域有着广泛的应用。
截至目前，已经提出了各式各样的AC自动机优化算法，包括基于前缀识别的自动机算法AC[2]、基于状态转移表加速的算法[3]、利用字符跳跃的加速匹配算法[4]。但是，这些算法的处理过程本质上为串行匹配，因而匹配性能较低，无法满足大数据环境下的高性能数据实时处理要求。此外，直接对AC自动机进行简单并行化易出现假阴性错误。
因此，针对原始AC自动机匹配速度较慢的问题，本文提出了一种基于多线程并行化的多模式串加速匹配算法。通过将文本分割成若干文本段进行多线程加速匹配，同时为保证算法功能的正确性，提取出切割点附近的边界字符形成切割点边界字符集进行处理。理论分析与实验结果表明，此算法与原始AC自动机的性能加速比达到8.38，性能提高接近1个数量级，非常适合于大规模数据的实时处理。
本文详细内容请下载：http://www.chinaaet.com/resource/share/2000003063
作者信息：
熊仁都1，杨嘉佳1，朱广宇1，唐 球1，隋 然2
(1.华北计算机系统工程研究所，北京100083；2.中央军委后勤保障部 信息中心，北京100842)
此内容为AET网站原创，未经授权禁止转载。