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

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

2、ring-Matching is this algorithm uses the statistic characteristic of the position and frequency of the char to build a new matching list. During the process of the matching, this algorithm will try its best to use this characteristic to skip much more chars to improve the efficiency of the matching.

3、 Another characteristic of this Algorithm is it can successfully finish without comparing all chars in the Text. Comparing with the Algorithm before, like BF ,KMP, BM, this Algorithms average complication of time reaches then best condition of these. Keywords: string-matching; algorithm; statistic c

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

5、检索、网络搜索、文本检索、拼写检查、语言翻译、数据压缩、网络入侵检测、计算机病毒特征码匹配以及 DNA 序列匹配等各个方面都有着很重要的应用。通过模式匹配，我们可以得到很多我们想要知道的信息，而这些是靠人工难以完成的。尤其是在以后的段落搜索，自然语言查询中，对模式匹配的速度、效率等要求会越来越高，而传统的 BF、KMP 和 BM 等算法并不能很高效的给出结果，因此我们有必要对模式匹配的算法进行进一步发展。本文主要在介绍了BF 算法、 KMP 算法的基础上提出一种更好的算法 基于统计特征的模式匹配算法。青海师范大学 2010 届本科生毕业论文21 绪论我们在日常生活中经常以局部特征判定事物，而这

6、种方式是普遍认可的，也是最佳的。一项将此技术应用于计算机科学领域的就是基于统计特征的模式匹配算法。1.1 基于统计特征的模式匹配算法提出原因 对于 KMP、 BM 等算法有一个共同的特征：顺序扫描或者从左至右，或者从右至左。这样的好处是匹配时有顺序的规律可循，比较容易理解，操作起来比较方便， 缺点就是没有最大限度利用模式自身的一些统计特征而只是利用了顺序的特征。如何利用统计特征呢？举个例子来证明。在街上我们遇到了一个似曾相识的人，我们判断那个人是不是我们认识的人的时候，我们是把遇到的那个人与我们记忆中的那个人的特征相比较，比如说秃顶，眼角有颗痔，身高，性别，胖瘦，脸型，肤色等等。我们比较是鲜明

7、的特征，而不是从头到脚的扫描比较。也就是说我们在比较两个事物的时候是优先比较他们比较特殊的地方。对于模式匹配，这个优先级似的比较方式依然成立。1.2 基本数据规定传统的算法分析在有了模式匹配的需要后，出现了很多模式匹配的算法，在这里为后续内容分析而规定：主串 S 的长度为 n，模式串 T 的长度为 m，子串的定位操作 Index(S,T,pos)，其中 pos 为某个字符在主串中的位置。 2 传统的模式匹配算法本章介绍三种典型的传统的模式匹配算法，并分别给出部分算法实现。2.1 BF 算法BF（ Brute-Force）算法即简单模式匹配算法，也称 朴素串匹配算法算法，其算法思想：对主串 S

8、和模式串 T 进行从左至右顺序匹配比较，若主串 S 的第一个字符和模式串 T 的第一个字符进行比较，若相等则同时向后移动一位，继续逐个比较后续字符，否则如果在完全匹配结束前发生不匹配，那么模式串 T回溯到模式首字符，而主串 S 则回溯到起始位置的下一个字符进行比较。依次类推，直至模式串 T 和主串 S 中的一个子串相等，此时称为匹配成功，否则，称为匹配失败。图 2-1 展示了 pos=1 时，模式串 T=abcac和主串 S=ababcabcacbab的匹配过程。其中 i 和 j 指示主串 S 和模式串 T 中当前正待比较的字符位置。串的简单模式匹配算法描述如算法 2-1 所示。【算法描述】i

9、nt Index(SString S, SString T, int pos) int i, j;i=pos; j=1;While (i=T0) return (i- T0);else return 0;算法 2-1 串的简单模式匹配i=3第 1 趟匹配 S a b a b c a b c a c b a bT a b c a cj=3i=2第 2 趟匹配 S a b a b c a b c a c b a bT a b c a cj=1i=7第 3 趟匹配 S a b a b c a b c a c b a bT a b c a cj=5i=4第 4 趟匹配 S a b a b c a b

10、c a c b a bT a b c a cj=1i=5第 5 趟匹配 S a b a b c a b c a c b a bT a b c a cj=1i=11第 6 趟匹配 S a b a b c a b c a c b a bT a b c a cj=6图 2-1 串的简单模式匹配过程示意这种算法看起来比较简单，但是效率比较低，最好的情况下为 O(m+n)，在最坏情况下，每趟比较都在最后出现不等，最多要比较 n-m-1 趟，总比较次数为 O(n-m+1)m)，算法的时间复杂度为 O(m*n)。2.2 KMP 算法青海师范大学 2010 届本科生毕业论文42.2.1 简述KMP（ 无回溯的

11、模式匹配）算法正是由 D.E.Knuth 、V.R.Pratt 和J.H.Morris 同时发现的，因此称 KMP 算法。它是针对上述算法频繁回溯的不足做了实质性的改进。其基本思想是：某趟匹配中，主串字符 si和模式串 tj匹配失败后，指针 i 不回溯，而是让模式串 T 向右“滑动 ”至某个位置，假设这个位置是 k，使得 tj对准 si继续向右进行比较。因此，KMP 算法的关键就在于找到模式串向右“ 滑动的距离 ”。 若用数组元素 nextj来表示字符 tj不匹配时的滑动距离，则 nextj的取值满足以下 next 函数的定义：0nextj= maxk|1T0) return(i- T0);e

12、lse return 0;算法 2-2 KMP 模式匹配KMP 算法最大限度的利用先前已经匹配成功的部分模式串，减少比较的次数，过滤掉那些多余的比较，进行最大限度的向前跳跃，再继续进行比较，从而提高模式匹配的效率。当模式中很少自我匹配的子串时，运行速度比较快，是 O(m+n)。其在最坏情况下的运行时间仍然是 (n-m+1)m)。2.3 BM 算法 BM(Boyer Moore)算法可比 KMP 算法快上 3 至 5 倍。其与朴素匹配算法及KMP 算法的不同点是在作 Sk+1.k+m与 T1.m的匹配测试时是从后面往前面扫描，而不是从左到右。与 KMP 算法的相同点是在得到部分匹配时充分地利用部

13、分匹配所隐含的、可帮助跳过不必要的测试、提高算法效率的信息。采用“坏字符”和“ 好尾缀”的启发式技术来修改 s 的值。 坏字符思想：当匹配发生在 tj!=si时，且如果 si不出现在模式串 T 中，则将模式串右移至 ti右端再开始重新匹配。 如果 ti在模式串 T 中有若干出现， 则将模式中的 tj右移至模式串 T 中最后出现的位置。 具体的算法 2-3 如下：【算法描述】Bad_string(SString T, int m, int occ) () char a;int j;for (a=0; a=m; a+)occa=-1;for (j=0; j=m; j+)a= Tj;occa=j;算法 2-3 坏字符匹配好尾缀思想：当模式串 T 的后面 k 位和主串 S 中一致的部分有部分在 T 中其他部分出现，则可以将 T 向右移动直至这一部分与要求一致的部分尽可能长。其基本算法和 KMP 中的 next 比较相似，不作说明。 BM 算法在最好的情况下时间复杂度可以达到 O(n/m)。3 基于统计特征的模式匹配算法3.1 算法思想在每个模式串中，各个字符出现的频率是不一样的，同一个字符出现的位