資源描述：
《多模式匹配算法及硬件實現(xiàn)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
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.?多模式匹配算法及硬件實現(xiàn)1,2+1,211李偉男,鄂躍鵬,葛敬國,錢華林1(中國科學(xué)院計算機(jī)網(wǎng)絡(luò)信息中心,北京100080)2(中國科學(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摘要:介紹了多模式匹配的算法和硬件實現(xiàn)方法.首先介紹了兩種常用的多模式匹配算法——Aho-Corasick基于自動機(jī)的算法和Wu-Manber基于hash的后綴匹配加移位跳躍的算法以及相關(guān)的改進(jìn)算法.并通過實驗對各種多模式匹配算法的時空復(fù)雜度進(jìn)行了分析比較.通過幾個硬件實現(xiàn)的實例介紹了多模式匹配的硬件實現(xiàn)方法及策略.最后對多模式匹配的發(fā)展趨勢進(jìn)行了展望.關(guān)鍵詞:多模式匹配;Aho-Corasick算法;有限狀態(tài)自動機(jī);
7、Wu-Manber算法;FPGA(現(xiàn)場可編程門陣列);TCAM(三態(tài)內(nèi)容尋址存儲器);bloomfilter中圖法分類號:TP301文獻(xiàn)標(biāo)識碼:A模式匹配問題是計算機(jī)科學(xué)中的一個基本問題,其研究內(nèi)容在信息檢索、模式識別等眾多領(lǐng)域均有重要價值,在拼寫檢查、語言翻譯、數(shù)據(jù)壓縮、搜索引擎、入侵檢測、內(nèi)容過濾、計算機(jī)病毒特征碼匹配以及基因序列比較等應(yīng)用中起著重要的作用.模式匹配按照匹配模式的數(shù)目分為單模式匹配和多模式匹配兩類.最初的單?SupportedbytheNation
