文獻(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]?;贏ho-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)行簡單并行化易出現(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://ihrv.cn/resource/share/2000003063
作者信息:
熊仁都1,楊嘉佳1,朱廣宇1,唐 球1,隋 然2
(1.華北計(jì)算機(jī)系統(tǒng)工程研究所,北京100083;2.中央軍委后勤保障部 信息中心,北京100842)