针对大规模url关键字的多模匹配算法的性能优化

《针对大规模url关键字的多模匹配算法的性能优化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文针对大规模URL关键字的多模匹配算法的性能优化PERFORMANCEOPTIMIZATIONOFTHE MULTI-PATTERNMATCHING ALGORITHMFORTHELARGE-SCALE URLKEYWORDS李伦2011年6月国内图书分类号：TP301.6学校代码：10213 国际图书分类号：004.6密级：公开工学硕士学位论文针对大规模URL关键字的多模匹配算法的性能优化硕士研究生：李伦导师：李东教授申请学位：工学硕士学科：计算机科学与技术所在单位：计算机科学与技术学院答辩日期：2011年6月授予学位单位：哈尔滨工业大学Clas

2、sifiedIndex:TP301.6 U.D.C:004.6DissertationfortheMasterDegreeinEngineeringPERFORMANCEOPTIMIZATIONOFTHEMULTI-PATTERNMATCHINGALGORITHMFORTHELARGE-SCALEURLKEYWORDSCandidate：LiLunSupervisor：Prof.LiDongAcademicDegreeAppliedfor：MasterofEngineeringSpeciality：ComputerScienceandTechnologyAf

3、filiation：SchoolofComputerScienceandTechnologyDateofDefence：June,2011Degree-Conferring-Institution：HarbinInstituteofTechnology哈尔滨工业大学工学硕士学位论文摘要字符串匹配算法一直是计算机科学的研究热点，尤其是信息时代数据爆炸式的增长对字符串匹配算法的性能提出了更高的要求。在信息安全领域中，关键字规模大，实时性要求高、匹配数据复杂多变使得大规模URL关键字的多模匹配算法中巨大的内存消耗成为当今入侵检测等信息安全系统的性能瓶颈。本文研究了

4、多种精确多模匹配算法，总结并分析各算法的优缺点。深入分析了大规模URL关键字的长度特征和匹配需求特征，总结出URL关键字中，长度较长的URL关键字较多，短关键字较少，且具有与表达式匹配需求的关键字比例较少的特点。提出针对大规模URL关键字匹配的性能优化算法PMUC(Multi-patternMatchingAlgorithmforURLBasedonClassification)，该算法结合AC算法和Wu-Mamber算法的优势，对URL关键字进行分类匹配，达到性能优化的目的。对经典的AC算法和Wu-Mamber算法均进行了改进，将长度较短且具有与表达式匹配

5、需求的关键字使用AC算法的改进算法GFAM进行匹配，其余关键字使用Wu-Mamber算法的改进算法WMS进行匹配。本文实现了基于PMUC算法进行性能优化后的URL关键字多模匹配模块，并加入到可扩展的入侵监测系统进行性能测试。离线测试首先测试优化后的匹配算法的正确性，在验证算法正确性的基础上给出了优化后的匹配模块性能与原匹配模块性能的对比结果，同时仔细调整了分类参数：分类长度m和自动机深度D，测试了调整参数对算法的性能影响，给出基于14万条配置的参数经验值。在线测试使用真实的网络动态数据，认为算法针对大规模URL关键字匹配具有实际应用价值。实验结果表明使用PM

6、UC算法对匹配模块进行性能优化后，内存可压缩为未优化前的5%以内，同时针对大规模URL关键字的初始化时间有明显的缩短。关键词：字符串匹配；大规模URL关键字匹配；AC算法；Wu-Mamber算法；内存压缩-I-哈尔滨工业大学工学硕士学位论文AbstractStringmatchingalgorithmhasalwaysbeenaresearchfocusincomputerscience.Higherrequirementshavebeenputforwardfortheperformanceofstringmatchingalgorithmsduetoth

7、eexplosivegrowthofdata.Ininformationsecurityarea,thelarge-scaleofkeywords,real-timedemandingandcomplexmatchingdatamakethehugememoryconsumptionoflarge-scaleURLkeywordsmatchingalgorithmstheperformancebottlenecksintheinformationsecuritysystemlikeintrusiondetection.Inthispaper,severals

8、tringmatchingalgorithmsare