資源描述：
《多模式匹配算法及硬件實(shí)現(xiàn)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.ac.cnJournalofSoftware,Vol.17,No.12,December2006,pp.2403?2415http://www.jos.org.cnDOI:10.1360/jos172403Tel/Fax:+86-10-62562563?2006byJournalofSoftware.Allrightsreserved.?多模式匹配算法及硬件實(shí)現(xiàn)1,2+1,211李偉男,鄂躍鵬,葛敬國(guó),錢華林1(中國(guó)科學(xué)院計(jì)算機(jī)網(wǎng)絡(luò)信息中心,北京100080)2(中國(guó)科學(xué)院研究生院,北京100049
2、)Multi-PatternMatchingAlgorithmsandHardwareBasedImplementation1,2+1,211LIWei-Nan,EYue-Peng,GEJing-Guo,QIANHua-Lin1(ComputerNetworkInformationCenter,TheChineseAcademyofSciences,Beijing100080,China)2(GraduateSchool,TheChineseAcademyofSciences,Beijing100049,China)+Correspondingauthor:Phn:+86-10-5
3、8812364,Fax:+86-10-58812306,E-mail:wnli@cnic.cn,http://www.cnic.cnLiWN,EYP,GeJG,QianHL.Multi-Patternmatchingalgorithmsandhardwarebasedimplementation.JournalofSoftware,2006,17(12):2403?2415.http://www.jos.org.cn/1000-9825/17/2403.htmAbstract:Thispapersurveysthealgorithmsandhardwareimplementatio
4、nsofthemulti-patternmatching.Firstly,twocommonlyusedmulti-patternalgorithms,Aho-Corasick’sautomatabasedalgorithmandWu-Manber’shashbasedsuffixmatchingwithskippingalgorithmareintroduced.Andthen,someimprovingwaysarereferred.Next,timeandspacecomplexityofthesealgorithmsareanalyzed,andtheexperimenta
5、lresultsshowtheirperformances.Further,severalhardwarebasedimplementationsaretakenasexamplestodemonstratethegeneralmethodsandstrategiesfortheimplementationonhardware.Thedevelopingtrendispredictedintheend.Keywords:multi-patternmatching;Aho-Corasickalgorithm;finitestateautomata;Wu-Manberalgorithm
6、;FPGA(fieldprogrammablegatearray);TCAM(ternarycontentaddressablememory);bloomfilter摘要:介紹了多模式匹配的算法和硬件實(shí)現(xiàn)方法.首先介紹了兩種常用的多模式匹配算法——Aho-Corasick基于自動(dòng)機(jī)的算法和Wu-Manber基于hash的后綴匹配加移位跳躍的算法以及相關(guān)的改進(jìn)算法.并通過(guò)實(shí)驗(yàn)對(duì)各種多模式匹配算法的時(shí)空復(fù)雜度進(jìn)行了分析比較.通過(guò)幾個(gè)硬件實(shí)現(xiàn)的實(shí)例介紹了多模式匹配的硬件實(shí)現(xiàn)方法及策略.最后對(duì)多模式匹配的發(fā)展趨勢(shì)進(jìn)行了展望.關(guān)鍵詞:多模式匹配;Aho-Corasick算法;有限狀態(tài)自動(dòng)機(jī);
7、Wu-Manber算法;FPGA(現(xiàn)場(chǎng)可編程門陣列);TCAM(三態(tài)內(nèi)容尋址存儲(chǔ)器);bloomfilter中圖法分類號(hào):TP301文獻(xiàn)標(biāo)識(shí)碼:A模式匹配問(wèn)題是計(jì)算機(jī)科學(xué)中的一個(gè)基本問(wèn)題,其研究?jī)?nèi)容在信息檢索、模式識(shí)別等眾多領(lǐng)域均有重要價(jià)值,在拼寫檢查、語(yǔ)言翻譯、數(shù)據(jù)壓縮、搜索引擎、入侵檢測(cè)、內(nèi)容過(guò)濾、計(jì)算機(jī)病毒特征碼匹配以及基因序列比較等應(yīng)用中起著重要的作用.模式匹配按照匹配模式的數(shù)目分為單模式匹配和多模式匹配兩類.最初的單?SupportedbytheNation
