资源描述：
《多模式匹配算法及硬件实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
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.∗多模式匹配算法及硬件实现1,2+1,211李伟男,鄂跃鹏,葛敬国,钱华林1(中国科学院计算机网络信息中心,北京100080)2(中国科学院研究生院,北京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摘要:介绍了多模式匹配的算法和硬件实现方法.首先介绍了两种常用的多模式匹配算法——Aho-Corasick基于自动机的算法和Wu-Manber基于hash的后缀匹配加移位跳跃的算法以及相关的改进算法.并通过实验对各种多模式匹配算法的时空复杂度进行了分析比较.通过几个硬件实现的实例介绍了多模式匹配的硬件实现方法及策略.最后对多模式匹配的发展趋势进行了展望.关键词:多模式匹配;Aho-Corasick算法;有限状态自动机;
7、Wu-Manber算法;FPGA(现场可编程门阵列);TCAM(三态内容寻址存储器);bloomfilter中图法分类号:TP301文献标识码:A模式匹配问题是计算机科学中的一个基本问题,其研究内容在信息检索、模式识别等众多领域均有重要价值,在拼写检查、语言翻译、数据压缩、搜索引擎、入侵检测、内容过滤、计算机病毒特征码匹配以及基因序列比较等应用中起着重要的作用.模式匹配按照匹配模式的数目分为单模式匹配和多模式匹配两类.最初的单∗SupportedbytheNation
