基于统计特征的模式匹配算法

《基于统计特征的模式匹配算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于统计特征的模式匹配算法摘要针对传统模式匹配算法的按模式中字符排列顺序匹配的过程，该算法模拟人脑思维利用模式中字符出现频率、位置等特征信息建立了一个新的匹配序列，打乱了原来的顺序匹配过程，从而在匹配过程中，利用特征信息尽可能的跳过更多的字符，从而达到比较高的匹配效率。该算法的另一大特点就是不需要遍历完所有文本中的字符就可以找出与模式匹配的字符串。与传统的BF、KMP、BM等算法相比，该算法的平均时间复杂度已经达到了他们的最好情况。关键词：模式匹配；算法；统计特征AbstractThedifferencetot

2、hetraditionalAlgorithmofString-Matchingisthisalgorithmusesthestatisticcharacteristicofthepositionandfrequencyofthechartobuildanewmatchinglist.Duringtheprocessofthematching,thisalgorithmwilltryitsbesttousethischaracteristictoskipmuchmorecharstoimprovetheeffic

3、iencyofthematching.AnothercharacteristicofthisAlgorithmisitcansuccessfullyfinishwithoutcomparingallcharsintheText.ComparingwiththeAlgorithmbefore,likeBF,KMP,BM,thisAlgorithm’saveragecomplicationoftimereachesthenbestconditionofthese.Keywords:string-matching;a

4、lgorithm;statisticcharacteristic目录引言11绪论21.1基于统计特征的模式匹配算法提出原因21.2基本数据规定22传统的模式匹配算法22.1BF算法22.2KMP算法32.3BM算法53基于统计特征的模式匹配算法53.1算法思想53.2算法分析7结束语9参考文献10青海师范大学2010届本科生毕业论文引言字符串匹配是字符串的基本运算之一。串的模式匹配即子串定位，是一种重要的串运算。模式匹配就是在主串S=s1s2s3s4……中查找模式串T=t1t2t3t4……的所有出现，该技术在很

5、多领域都发挥重要的作用，比如在情报检索、网络搜索、文本检索、拼写检查、语言翻译、数据压缩、网络入侵检测、计算机病毒特征码匹配以及DNA序列匹配等各个方面都有着很重要的应用。通过模式匹配，我们可以得到很多我们想要知道的信息，而这些是靠人工难以完成的。尤其是在以后的段落搜索，自然语言查询中，对模式匹配的速度、效率等要求会越来越高，而传统的BF、KMP和BM等算法并不能很高效的给出结果，因此我们有必要对模式匹配的算法进行进一步发展。本文主要在介绍了BF算法、KMP算法的基础上提出一种更好的算法—基于统计特征的模式匹配

6、算法。1青海师范大学2010届本科生毕业论文1绪论我们在日常生活中经常以局部特征判定事物，而这种方式是普遍认可的，也是最佳的。一项将此技术应用于计算机科学领域的就是基于统计特征的模式匹配算法。1.1基于统计特征的模式匹配算法提出原因对于KMP、BM等算法有一个共同的特征：顺序扫描—或者从左至右，或者从右至左。这样的好处是匹配时有顺序的规律可循，比较容易理解，操作起来比较方便，缺点就是没有最大限度利用模式自身的一些统计特征—而只是利用了顺序的特征。如何利用统计特征呢？举个例子来证明。在街上我们遇到了一个似曾相识的

7、人，我们判断那个人是不是我们认识的人的时候，我们是把遇到的那个人与我们记忆中的那个人的特征相比较，比如说秃顶，眼角有颗痔，身高，性别，胖瘦，脸型，肤色等等。我们比较是鲜明的特征，而不是从头到脚的扫描比较。也就是说我们在比较两个事物的时候是优先比较他们比较特殊的地方。对于模式匹配，这个优先级似的比较方式依然成立。1.2基本数据规定传统的算法分析在有了模式匹配的需要后，出现了很多模式匹配的算法，在这里为后续内容分析而规定：主串S的长度为n，模式串T的长度为m，子串的定位操作Index(S,T,pos)，其中pos为

8、某个字符在主串中的位置。2传统的模式匹配算法本章介绍三种典型的传统的模式匹配算法，并分别给出部分算法实现。2.1BF算法BF（Brute-Force）算法即简单模式匹配算法，也称朴素串匹配算法算法，其算法思想：对主串S和模式串T进行从左至右顺序匹配比较，若主串S的第一个字符和模式串T的第一个字符进行比较，若相等则同时向后移动一位，继续逐个比较后续字符，否则如果在完全匹配结束前发生不匹配