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.rjjo.cn/resource/share/2000003063
作者信息：
熊仁都1，楊嘉佳1，朱廣宇1，唐 球1，隋 然2
(1.華北計算機系統工程研究所，北京100083；2.中央軍委后勤保障部 信息中心，北京100842)
此內容為AET網站原創，未經授權禁止轉載。