盗墓笔记同人小说,好看的小说君子以泽,欢乐颂小说结局是什么

PARA-AC：一種基于AC自動(dòng)機(jī)的高性能匹配算法

2020年電子技術(shù)應(yīng)用第11期

熊仁都1，楊嘉佳1，朱廣宇1，唐球1，隋然2

1.華北計(jì)算機(jī)系統(tǒng)工程研究所，北京100083；2.中央軍委后勤保障部信息中心，北京100842

摘要： 原始AC自動(dòng)機(jī)由于匹配性能低，無(wú)法滿足當(dāng)前大數(shù)據(jù)環(huán)境下大規(guī)模特征串實(shí)時(shí)匹配的應(yīng)用需求。針對(duì)這一問(wèn)題，提出一種基于多線程的多模式串匹配加速算法，稱之為PARA-AC(Parallel Aho-Corasick automaton)。該算法將待匹配字符串切割成若干字符子串以及若干切割點(diǎn)邊界字符集，并將字符子串、切割點(diǎn)邊界字符集輸入至線程池中進(jìn)行匹配，從而實(shí)現(xiàn)字符串的并行化加速處理。實(shí)驗(yàn)結(jié)果表明，與原始AC自動(dòng)機(jī)匹配算法相比，PARA-AC算法顯著提高了匹配速度，約為原始AC的13.91倍。

關(guān)鍵詞： 多模式串匹配 AC自動(dòng)機(jī) 多線程并行化

中圖分類號(hào)： TP391.1
文獻(xiàn)標(biāo)識(shí)碼： A
DOI：10.16157/j.issn.0258-7998.200096
中文引用格式： 熊仁都，楊嘉佳，朱廣宇，等. PARA-AC：一種基于AC自動(dòng)機(jī)的高性能匹配算法[J].電子技術(shù)應(yīng)用，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={s₁，s₂，…，s_m}，對(duì)于任意一個(gè)字符串T=t₁t₂…t_n，找出S中所有字符串在T中出現(xiàn)的位置^[1]。基于Aho-Corasick(AC)自動(dòng)機(jī)的模式串匹配算法在當(dāng)前的串匹配算法中占據(jù)著重要地位，它以Trie樹為基礎(chǔ)，通過(guò)fail指針來(lái)實(shí)現(xiàn)狀態(tài)匹配失效的過(guò)程跳轉(zhuǎn)，保持了較為穩(wěn)定的匹配性能。因此，基于AC自動(dòng)機(jī)的串匹配算法在字符串搜索、生物特征識(shí)別、網(wǎng)絡(luò)安全等領(lǐng)域有著廣泛的應(yīng)用。

截至目前，已經(jīng)提出了各式各樣的AC自動(dòng)機(jī)優(yōu)化算法，包括基于前綴識(shí)別的自動(dòng)機(jī)算法AC^[2]、基于狀態(tài)轉(zhuǎn)移表加速的算法^[3]、利用字符跳躍的加速匹配算法^[4]。但是，這些算法的處理過(guò)程本質(zhì)上為串行匹配，因而匹配性能較低，無(wú)法滿足大數(shù)據(jù)環(huán)境下的高性能數(shù)據(jù)實(shí)時(shí)處理要求。此外，直接對(duì)AC自動(dòng)機(jī)進(jìn)行簡(jiǎn)單并行化易出現(xiàn)假陰性錯(cuò)誤。

因此，針對(duì)原始AC自動(dòng)機(jī)匹配速度較慢的問(wèn)題，本文提出了一種基于多線程并行化的多模式串加速匹配算法。通過(guò)將文本分割成若干文本段進(jìn)行多線程加速匹配，同時(shí)為保證算法功能的正確性，提取出切割點(diǎn)附近的邊界字符形成切割點(diǎn)邊界字符集進(jìn)行處理。理論分析與實(shí)驗(yàn)結(jié)果表明，此算法與原始AC自動(dòng)機(jī)的性能加速比達(dá)到8.38，性能提高接近1個(gè)數(shù)量級(jí)，非常適合于大規(guī)模數(shù)據(jù)的實(shí)時(shí)處理。

本文詳細(xì)內(nèi)容請(qǐng)下載：http://www.viuna.cn/resource/share/2000003063

作者信息：

熊仁都1，楊嘉佳1，朱廣宇1，唐球1，隋然2

(1.華北計(jì)算機(jī)系統(tǒng)工程研究所，北京100083；2.中央軍委后勤保障部信息中心，北京100842)

原創(chuàng)聲明：此內(nèi)容為AET網(wǎng)站原創(chuàng)，未經(jīng)授權(quán)禁止轉(zhuǎn)載。

相關(guān)內(nèi)容