文档介绍：:..基于统计特征的模式匹配算法针对传统模式匹配算法的按模式中字符排列顺序匹配的过程,该算法模拟人脑思维利用模式屮字符出现频率、位置等特征信息建立了一个新的匹配序列,打乱了原來的顺序匹配过程,从而在匹配过程中,利用特征信息尽可能的跳过更多的字符,从而达到比较高的匹配效率。该算法的另一大特点就是不需要遍历完所冇文本中的字符就可以找出与模式匹配的字符串。与传统的BF、KMP、BM等算法相比,该算法的平均时间复杂度已经达到了他们的最好情况。关键词:模式匹配;算法;统计特征AbstractThedifferencetothetraditionalAlgorithmofString-,,likeBF,KMP,BM,thisAlgorithm':string-matching;algorithm;haracteristic引言 11绪论 22传统的模式匹配算法 53基于统计特征的模式匹配算法 7结束语 9参考文献 10引言字符串匹配是字符串的基本运算之一。串的模式匹配即子串定位,是一种重要的串运算。模式匹配就是在主串S二S£2S:$……屮查找模式串T二……的所冇出现,该技术在很多领域都发挥重要的作用,比如在情报检索、网络搜索、文木检索、拼写检杳、语言翻译、数据压缩、网络入侵检测、计算机病毒特征码匹配以及DNA序列匹配等各个方而都冇着很重要的应用。通过模式匹配,我们可以得到很多我们想要知道的信息,而这些是靠人工难以完成的。尤其是在以后的段落搜索,自然语言查询屮,对模式匹配的速度、效率等要求会越来越高,而传统的BF、KMP和BM等算法并不能很高效的给出结果,因此我们有必要对模式匹配的算法进行进一步发展。木文主要在介绍了BF算法、KMP算法的基础上提出一种更好的算法一基于统计特征的模式匹配算法。1绪论我们在日常生活中经常以局部特征判定事物,而这种方式是普遍认可的,也是最佳的。-•项将此技术应用于计算机科学领域的就是基于统计特征的模式匹配算法。、BM等算法有一个共同的特征:顺序扫描一或者从左至右,或者从右至左。这样的好处是匹配时有顺序的规律可循,比较容易理解,操作起来比较方便,缺点就是没冇最大限度利用模式自身的一些统计特征一而只是利用了顺序的特征。如何利用统计特征呢?举个例了来证明。在街上我们遇到了一个似曾相识的人,我们判断那个人是不是我们认识的人的时候,我们是把遇到的那个人与我们记忆中的那个人的特征相比较,比如说禿顶,眼角有颗痔,身高,性别,胖瘦,脸型,肤色等等。我们比较是鲜明的特征,而不是从头到脚的扫描比较。也就是说我们在比较两个事物的吋候是优先比较他们比较特殊的地方。对于模式匹配,这个优先级似的比较方式依然成立。,出现了很多模式匹配的算法,在这里为后续内容分析而规定:主串S的长度为n,模式串T的长度为ni,子串的定位操作Indcx(S,T,pos),其中pos为某个字符在主串中的位置。2传统的模式匹配算法木章介绍三种典型的传统的模式匹配算法,并分别给出部分算法实现。(Brute-Force)算法即简单模式匹配算法,也称朴素串匹配算法算法,其算法思想:对主串S和模式串T进行从左至右顺序匹配比较,若主串S的第一个字符和模式串T的第一个字符进行比较,若相等则同吋向后移动一位,继续逐个比较后续字符,否则如果在完全匹配结束前发生不匹配,那么模式串T回溯到模式首字符,而主串s则回溯到起始位置的卜•一个字符进行比较。依次类推,直至模式串T和主串S中的一个子串相等,此时称为匹配成功,否则,称为匹配失败。图2-1展示了pos=l时,模式串T=,abcac,和主串S=,ababcabcacbab,的匹配过程。其中?•和丿•指示主