文獻(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.
0 引言
模式串匹配的作用是給定一組特定的字符串集合 S={s1，s2，…，sm}，對(duì)于任意一個(gè)字符串T=t1t2…tn，找出S中所有字符串在T中出現(xiàn)的位置[1]。基于Aho-Corasick(AC)自動(dòng)機(jī)的模式串匹配算法在當(dāng)前的串匹配算法中占據(jù)著重要地位，它以Trie樹為基礎(chǔ)，通過fail指針來實(shí)現(xiàn)狀態(tài)匹配失效的過程跳轉(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]。但是，這些算法的處理過程本質(zhì)上為串行匹配，因而匹配性能較低，無法滿足大數(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ī)匹配速度較慢的問題，本文提出了一種基于多線程并行化的多模式串加速匹配算法。通過將文本分割成若干文本段進(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://m.jysgc.com/resource/share/2000003063
作者信息：
熊仁都1，楊嘉佳1，朱廣宇1，唐 球1，隋 然2
(1.華北計(jì)算機(jī)系統(tǒng)工程研究所，北京100083；2.中央軍委后勤保障部 信息中心，北京100842)