资源描述：
《基于异构隐式存储的多模式匹配算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第3期李志东等：基于异构隐式存储的多模式匹配算法·125·基于异构隐式存储的多模式匹配算法李志东，杨武，张汝波，王巍（哈尔滨工程大学信息安全研究中心，黑龙江哈尔滨150001）摘要：提出了紧缩存储型Aho-Corasick算法变体，以异构的按需隐式存储取代同构的例行显式存储，从横向扇出压缩与纵向路径压缩2个方向入手，围绕着压缩稀疏事件表展开，当字符集大小σ=256时可将存储量缩减为原来的0.69%左右，而σ=64K时则达0.004%，即空间复杂度降为原来的(lbσ)/σ左右。依据扇出疏密程度的不同，分类采用了4种有针对性的快速事件定位方法，加之优化的失败迁移，使得
2、存储量的大幅缩减不以速度的明显损失为代价，实验也证实了这一点。适用于需承载大型模式集和较长模式串而对时延和抖动都比较敏感的场合(如在线数据流过滤)，在宽字符(如UNICODE型亚洲字符)匹配方面拥有显著优势。关键词：多模式匹配；紧缩存储；扇出压缩；路径压缩；事件定位中图分类号：TP301文献标识码：B文章编号：1000-436X(2009)03-0119-06Multi-patternmatchingalgorithmbasedonheterogeneousimplicitstorageLIZhi-dong,YANGWu,ZHANGRu-bo,WANGWei(Re
3、searchCenterofInformationSecurity,HarbinEngineeringUniversity,Harbin150001,China)Abstract:AvariationofAho-Corasickalgorithmviacompactstoragewaspresented,whichreplacedhomogeneousroutineexplicitstoragewithheterogeneousrequirementorientedimplicitone,firststartedfromtwoaspectsofwidthwisef
4、an-outcompressionandlengthwisepathcompression,thenexpandedaroundthecompressionofsparseeventtable,thusreducedmemoryusagetoabout0.69%oforiginalonewhenalphabetsizeσ=256,0.004%whenσ=64K,andspacecomplexityapproximate(lbσ)/σoforigin.Accordingtodifferentdegreesoffan-out,fourkindsofspecificfa
5、steventlocationmethodswereadopted,plusoptimizedfailuretransitions,ledtothefactthatthedramaticreductionofmemoryusageisn’tatthecostofobviouslossofspeed,whichwasalsoprovedbyexperiments.It’ssuitabletobeappliedinthecasesthatneedholdingmasssetoflongerpatternsandaresensitivetodelayandjitter(
6、forexample,onlinedatastreamfiltering),andpresentsdistinguishedsuperiorityinwide-character(suchasAsiancharacterofUNICODEtype)matching.Keywords:multiplepatternsmatching;compactstorage;fan-outcompression;pathcompression;eventlocation第3期李志东等：基于异构隐式存储的多模式匹配算法·125·1引言收稿日期：2008-08-28；修回日期：20
7、08-12-30基金项目：国家重点基础研究发展计划（“973”计划）基金资助项目（2007CB311100）；国家高技术研究发展计划（“863”计划）基金资助项目（2007AA01Z473）FoundationItems:TheNationalBasicResearchProgramofChina(973Program)(2007CB311100);TheNationalHighTechnologyResearchandDevelopmentProgramofChina(863Program)(2007AA01Z473)数据流或网络流的在线过滤一直是多模式匹配的关
8、键应用领域
