多模式匹配算法及硬件实现.pdf

ISSN1000-9825,CODENRUXUEWE-mail:[e-mail]
JournalofSoftware,Vol.17,No.12,December2006,pp.2403−2415http://www.jos.org.cn
DOI:10.1360/jos172403Tel/Fax:[phone]
©2006byJournalofSoftware.Allrightsreserved.

∗
多模式匹配算法及硬件实现

李伟男1,2+,鄂跃鹏1,2,葛敬国1,钱华林1

1(中国科学院计算机网络信息中心,北京100080)
2(中国科学院研究生院,北京100049)

Multi-PatternMatchingAlgorithmsandHardwareBasedImplementation

LIWei-Nan1,2+,EYue-Peng1,2,GEJing-Guo1,QIANHua-Lin1

1(ComputerNetworkInformationCenter,TheChineseAcademyofSciences,Beijing100080,China)
2(GraduateSchool,TheChineseAcademyofSciences,Beijing100049,China)
+Correspondingauthor:Phn:[phone],Fax:[phone],E-mail:[e-mail],http://www.cnic.cn

LiWN,EYP,GeJG,QianHL.Multi-Patternmatchingalgorithmsandhardwarebasedimplementation.
JournalofSoftware,2006,17(12):2403−2415.http://www.jos.org.cn/1000-9825/17/2403.htm

Abstract:Thispapersurveysthealgorithmsandhardwareimplementationsofthemulti-patternmatching.Firstly,
twocommonlyusedmulti-patternalgorithms,Aho-Corasick’sautomatabasedalgorithmandWu-Manber’shash
basedsuffixmatchingwithskippingalgorithmareintroduced.Andthen,someimprovingwaysarereferred.Next,
timeandspacecomplexityofthesealgorithmsareanalyzed,andtheexperimentalresultsshowtheirperformances.
Further,severalhardwarebasedimplementationsaretakenasexamplestodemonstratethegeneralmethodsand
strategiesfortheimplementationonhardware.Thedevelopingtrendispredictedintheend.
Keywords:multi-patternmatching;Aho-Corasickalgorithm;finitestateautomata;Wu-Manberalgorithm;FPGA
(fieldprogrammablegatearray);TCAM(ternarycontentaddressablememory);bloomfilter

摘要:介绍了多模式匹配的算法和硬件实现方法.首先介绍了两种常用的多模式匹配算法——Aho-Corasick
基于自动机的算法和Wu-Manber基于hash的后缀匹配加移位跳跃的算法以及相关的改进算法.并通过实验对
各种多模式匹配算法的时空复杂度进行了分析比较.通过几个硬件实现的实例介绍了多模式匹配的硬件实现
方法及策略.最后对多模式匹配的发展趋势进行了展望.
关键词:多模式匹配;Aho-Corasick算法;有限状态自动机;Wu-Manber算法;FPGA(现场可编程门阵列);TCAM(三
态内容寻址存储器);bloomfilter
中图法分类号:TP301文献标识码:A

模式匹配问题是计算机科学中的一个基本问题,其研究内容在信息检索、模式识别等众多领域均有重要价
值,在拼写检查、语言翻译、数据压缩、搜索引擎、入侵检测、内容过滤、计算机病毒特征码匹配以及基因序
列比较等应用中起着重要的作用.模式匹配按照匹配模式