一种改进的字符串匹配算法

《一种改进的字符串匹配算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第32卷第2期计算机工程2006年1月January2006VoL32抽2ComputerEngineering·软件技术与橄据库·文章幼号:1000-3428(2006)02-0062-03文献标识码:A中.分类号:TP301.6一种改进的字符串匹配算法王成1,2，刘金阴1,2(1.首都师范大学计算机科学联合研究院，北京00037;2.中国科学院计算技术研究所，北京100080)摘要:基于字符申匹配的检测方法是入侵检测系统中的一种重要方法。在分析了几种常见的字符串匹配算法(BF.KMP,BM.Sund

2、ay等)的基础上，提出了一种改进的字符串匹配算法一一SundayNew。该算法使每一次匹配不成功后都能跳过尽可能多的字符以进行下一轮匹配，并且匹配次数大大减少，从而提高了匹配效率。最后，分析了该算法的性能，并用具体的实验数据给出了几种匹配算法的测试结果。关性侧:字符申搜索;模式匹配;算法AnImprovedStringMatchingAlgorithmWANGChengt'2,LIUJingangt'2(1.JointFacultyofComputerScientificResearch,Capital

3、NormalUniversity,Beijing100037;2.InstituteofComputingTechnology,ChineseAcademyofSciences,Beijing100080)[Abstract]Stringmatchingalgorithmisanimportantmethodinintrusiondetection.Animprovedalgorithmisproposedforstringmatchingbasedonthediscussionsofseveralco

4、mmonstringmatchingalgorithms,forexample,BF,KMP,BM,Sunday,etc.Thisalgorithmcanjumpovermoretodonextmatchingwhenthismatchingislost.Atthesametime,thematchingtimesdecreasessharply.Inthiscase,itimprovesthematchingefficiency.Intheend,theanalysisofthisalgorithm'

5、sperformanceandthecomparisonsofthetestingresultsofseveralmatchingalgorithmsaregiven.[Keywords]Stringsearching;Patternmatching;Algorithm当今随着网络应用范围的不断扩大，对网络的各类攻击位置，再依次进行比较。如果存在s,1

6、坏情System,IDS)由于可以为网络安全提供实时的入侵检测及采况下要进行M*(N-M+1)次比较，时间复杂度为O(M*N)o取相应的防护手段而倍受青睐。目前市场上较常见的IDS是1.2KMP算法[21误用入侵检测系统(MisuseIntrusionDetectionSystem,KMP(Knuth-Morris-Pratt)算法是D.E.Knuth,J.H.MorrisMIDS)，它是基于模式匹配(字符串搜索)技术。随着网络带宽和V.R.Pratt3人于1977年提出来的。其核心思想是:在发生的扩大

7、和攻击手段的多样化，匹配算法的效率已成为MIDS失配时，正文不需要回溯，而是利用已经得到的“部分匹配”的瓶颈{’!。因此，如何改进字符串匹配算法，提高搜索速度，结果将模式申右移尽可能远的距离，继续进行比较。这里要是目前IDS研究的重要领域之一。强调的是，模式申不一定向右移动一个字符的位置，右移也字符串的模式匹配问题的形式化定义是:在字符集Y,上，不一定必须从模式串起点处重新试匹配，即模式串一次可以给定一个长度为N的文本字符串T[1...N]，以及一个长度为右移多个字符的位置，右移后可以从模式串起点后的某

8、处开M的模式字符串P[1...M]。如果对于1