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

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

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

Abstract

The difference to the traditional Algorithm of String-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. 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 Algorithm’s average complication of time reaches then best condition of these.
Keywords: string-matching; algorithm; statistic characteristic

目 录

引言 1
1绪论 2
1.1 基于统计特征的模式匹配算法提出原因 2
1.2 基本数据规定 2
2传统的模式匹配算法 2
2.1 BF算法 2
2.2 KMP算法 3
2.3 BM算法 5
3基于统计特征的模式匹配算法 5
3.1算法思想 5
3.2算法分析 7
结束语 9
参考文献 10

青海师范大学2010届本科生毕业论文
引言
字符串匹配是字符串的基本运算之一。串的模式匹配即子串定位，是一种重要的串运算。模式匹配就是在主串S= s1s2s3s4……中查找模式串T= t1t2t3t4……的所有出现，该技术在很多领域都发挥重要的作用，比如在情报检索、网络搜索、文本检索、拼写检查、语言翻译、数据压缩、网络入侵检测、计算机病毒特征码匹配以及DNA序列匹配等各个方面都有着很重要的应用。通过模式匹配，我们可以得到很多我们想要知道的信息，而这些是靠人工难以完成的。尤其是在以后的段落搜索，自然语言查询中，对模式匹配的速度、效率等要求会越来越高，而传统的BF、KMP和BM等算法并不能很高效的给出结果，因此我们有必要对模式匹配的算法进行进一步发展。本文主要在介绍了BF算法、KMP算法的基础上提出一种更好的算法—基于统计特征的模式匹配算法。
1
1绪论
我们在日常生活中经常以局部特征判定事物，而这种方式是普遍认可的，也是最佳的。一项将此技术应用于计算机科学领域的就是基于统计特征的模式匹配算法。
1.1 基于统计特征的模式匹配算法提出原因
对于KMP、BM等算法有一个共同的特征：顺序扫描—或者从左至右，或者从右至左。这样的好处是匹配时有顺序的规律可循，比较容易理解，操作起来比较方便， 缺点就是没有最大限度利用模式自身的一些统计特征—而只是利用了顺序的特征。如何利用统计特征呢？举个例子来证明。在街上我们遇到了一个似曾相识的人，我们判断那个人是不是我们认识的人的时候，我们是把遇到的那个人与我们记忆中的那个人的特征相比较，比如说秃顶，眼角有颗痔，身高，性别，胖瘦，脸型，肤色等等。我们比较是鲜明的特征，而不是从头到脚的扫描比较。也就是说我们在比较两个事物的时候是优先比较他们比较特殊的地方。对于模式匹配，这个优先级似的比较方式依然成立。
1.2 基本数据规定
传统的算法分析在有了模式匹配的需要后，出现了很多模式匹配的算法，在这里为后续内容分析而规定：主串S的长度为n，模式串T的长度为m，子串的定位操作Index(S,T,pos)，其中pos为某个字符在主串中的位置。
2传统的模式匹配算法
本章介绍三种典型的传统的模式匹配算法，并分别给出部分算法实现。
2.1 BF算法
BF（Brute-Force）算法即简单模式匹配算法，也称朴素串匹配算法算法，其算法思想：对主串S和模式串T进行从左至右顺序匹配比较，若主串S的第一个字符和模式串T的第一个字符进行比较，若相等则同时向后移动一位，继续逐个比较后续字符，否则如果在完全匹配结束前发生不匹配，那么模式串T回溯到模式首字符，而主串S则回溯到起始位置的下一个字符进行比较。依次类推，直至模式串T和主串S中的一个子串相等，此时称为匹配成功，否则，称为匹配失败。图2-1展示了pos=1时，模式串T=’abcac’和主串S=’ababcabcacbab’的匹配过程其中i和j指示主串S和模式串T中当前正待比较的字符位置。
串的简单模式匹配算法描述如算法2-1所示。
【算法描述】
int Index(SString S, SString T, int pos)
{
int i, j;
i=pos; j=1;
While (i<=S[0]&&j<=T[0])
{
if (S[i]== T[j]) { ++i; ++j; }
else { i=i-j+2; j=1; }
2
}
if (j>=T[0]) return (i- T[0]);
else return 0;
}
算法2-1 串的简单模式匹配

↓i=3
第1趟匹配 S a b a b c a b c a c b a b
T a b c a c
↑j=3

↓i=2
第2趟匹配 S a b a b c a b c a c b a b
T a b c a c
↑j=1

↓i=7
第3趟匹配 S a b a b c a b c a c b a b
T a b c a c
↑j=5

↓i=4
第4趟匹配 S a b a b c a b c a c b a b
T a b c a c
↑j=1

↓i=5
第5趟匹配 S a b a b c a b c a c b a b
T a b c a c
↑j=1

↓i=11
第6趟匹配 S a b a b c a b c a c b a b
T a b c a c
↑j=6

图2-1 串的简单模式匹配过程示意
这种算法看起来比较简单，但是效率比较低，最好的情况下为O(m+n)，在最坏情况下，每趟比较都在最后出现不等，最多要比较n-m-1趟，总比较次数为O((n-m+1)m)，算法的时间复杂度为O(m*n)。
2.2 KMP算法

3
青海师范大学2010届本科生毕业论文
2.2.1简述
KMP（无回溯的模式匹配）算法正是由D.EKnuth 、V.R.Pratt 和J.H.Morris同时发现的，因此称KMP算法。它是针对上述算法频繁回溯的不足做了实质性的改进。其基本思想是：某趟匹配中，主串字符si和模式串tj匹配失败后，指针i不回溯，而是让模式串T向右“滑动”至某个位置，假设这个位置是k，使得tj对准si继续向右进行比较。因此，KMP算法的关键就在于找到模式串向右“滑动的距离”。
若用数组元素next[j]来表示字符tj不匹配时的滑动距离，则next[j]的取值满足以下next函数的定义：

0

next[j]= max{k|11’=’tj-k+1t j-k+2…t j-1’} 此集合不空时，取相等串中最长字串

1 其他情况

2.2.2 KMP算法实现
KMP算法是在求得模式串的next函数值的基础上执行的，next函数值仅依赖于模式T本身，而和主串S无关。由2.2.1中next函数的定义实现可得到模式串’abcaabbabcab’的next函数值，如表2-1所示。
表2-1  模式串’abcaabbabcab’的next函数值
j
1
2
3
4
5
6
7
8
9
10
11
12
模式
a
b
c
a
a
b
b
a
b
c
a
b
next[j]
0
1
1
1
2
2
3
1
2
3
4
5
KMP算法如算法2-2所示，在形式上和算法2-1极为类似。假设模式串 T[1…m]中前 q 个字符已经匹配了主串 S[s…s+q-1]，那我们就可以避免一些重复匹配。找出最大的 k 使得 T[1…k]=T[(q-k+1)…q]，从而计算出 s’使得 T[1…k]=S[s’…s’+k-1].其中 s，+k-1=s+q-1。
【算法描述】
int Index_KMP(SString S, SString T, int pos)
{
int i, j;
i=pos; j=1;
while (i<=S[0]&&j<=T[0])
{
if (j==0||S[i]== T[j]) { ++i; ++j; }
else j = next[j];
4
}
if j>T[0]) return(i- T[0]);
else return 0;
}
算法2-2 KMP模式匹配
KMP算法最大限度的利用先前已经匹配成功的部分模式串，减少比较的次数，过滤掉那些多余的比较，进行最大限度的向前跳跃，再继续进行比较，从而提高模式匹配的效率。当模式中很少自我匹配的子串时，运行速度比较快，是O(m+n)。其在最坏情况下的运行时间仍然是Ο((n-m+1)m)。
2.3 BM算法
BM(Boyer Moore)算法可比KMP算法快上3至5倍。其与朴素匹配算法及KMP算法的不同点是在作S[k+1..k+m]与T[1..m]的匹配测试时是从后面往前面扫描，而不是从左到右。与KMP算法的相同点是在得到部分匹配时充分地利用部分匹配所隐含的、可帮助跳过不必要的测试、提高算法效率的信息。采用“坏字符”和“好尾缀”的启发式技术来修改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++)
  occ[a]=-1;
for (j=0; j<=m; j++)
       a= T[j];
occ[a]=j;
}
算法2-3 坏字符匹配
好尾缀思想：当模式串T的后面k位和主串S中一致的部分有部分在T中其他部分出现，则可以将T向右移动直至这一部分与要求一致的部分尽可能长。其基本算法和KMP中的 next比较相似，不作说明。
BM算法在最好的情况下时间复杂度可以达到O(n/m)。
3基于统计特征的模式匹配算法
3.1算法思想
在每个模式串中，各个字符出现的频率是不一样的，同一个字符出现的位置也是无法预测的。我们可以很好的利用这些无法预测性，因为越是特殊，那就
5
越不容易被匹配成功，这样，我们在模式匹配过程中就可以尽早的发现错误，尽早的调整匹配方案，从而达到最优的匹配结果。
整个算法的思想是：利用对模式的统计分析，将各个字符按照出现的频率、位置排序，出现次数最少的优先级越高，如果有频率相同的字符，则按照第一次出现的位置由大向小排。这样，就建立了一个新的序列，我们给它起个名字叫匹配序列。
3.1.1模式中相同字符的处理
针对模式中的相同字符需要记录下同一字符出现位置之间的距离序列。只有当某个字符的所有出现都匹配成功才转向下一个字符。当匹配不成功时，如果是第一个就不成功，将文本向后移一位重新匹配；如果是某个字符的第k次出现匹配不成功，则可以通过类似于KMP中的next方法来获取该跳过的位置，只是这个时候传给next方法的是某字符的距离序列。也就是说用匹配序列代替模式原来的匹配顺序与文本的进行匹配。下面以一个例子来具体的说明。假使在一随机模式串为’dfdacaijaitopaqay’则建立的匹配序列为’yqpotjcfiiddaaaaaa’如果在主串中，y匹配成功，如下表3-1。
表3-1
主串
a
g
c
f
q

y
t
m
a
p
c
k
模式

y

原模式中q的位置应该在y的前面第二位，而文本中对应的是f,所以此时匹配不成功，因此文本应该向左移动后重新开始比较，因为字符y在模式中仅仅出现一次，而且位置在第17位，所以移动后必须要保证文本对应着模式中字符y的位置的前面17个字符都没有y，也就是说，可以将文本直接向左移动17位。下面考虑更加一般的情况：
原模式中出现字符a的次数为6，出现的位置依次为：4，6，9，14，16，18 。可以得出字符a的距离序列为：2，3，5，2，2，利用前面KMP算法中的next方法，把字符a的距离序列当成是模式，可以算出：next[0]=0，next[1]=0，next[2]=0，next[3]=1，next[4]=1；这里的next数组值的意义和KMP中是next数组值的意义相同。如果就单单从这个序列来看，当第三个a不匹配时，我们就可以简单的将文本向左移动两位然后重新进行匹配；当第六个a不匹配时，将文本向左移动10位然后重新进行匹配。如果所有a都匹配时，如果另一个不同的字符(例如d)不匹配时，那么至少可以象右移动第一个a和第五个a之间的距离12。但是，这些仅仅是从字符的序列上来看，还要考虑一个比较重要的因素：第一个a在模式中的位置。以上例为主：当第三个a不匹配时，原本按照next的含义，可以移动第一个a到第二个a的位置。如下表3-2：
模式1为原先模式的位置，模式2，模式3为移动后模式的位置。
表3-2
主串

a
a
t

模式1
d
f
d
a
c
a
i
j
a
i
t
o
p
a
q
a
模式2

d
f
d
a
c
a
i
j
a
i
t
o
p
a
模式3

d
f
d
a
c
a
i
j
a
i

6
在这里可以发现，如果这样移动，那么文本中与模式2的第一个a前面第二位对应的是a，这是不合理的，文本中与模式第一个a匹配的位置的前三个字符应该都不是a才对。所以，可以跳过更多的字符，事实上，模式可以向右移动6个字符(如模式3所示)。也就是说，当按照求得的next值去移动的同时，用考虑所移动到的位置与前一个相同字符之间的距离是否大于等于第一个字符的位置k。那么有必要对next进行修正，即在求next[k]时，要加上一个条件:第next[k]位距离前面一个相同字符的距离要大于等于k。具体的算法如算法3-1。
【算法描述】
Void Next(SString T, int m, int k, int next[])
{
int t=0;
m=strlen(T);
next[1]=0;
for (int q=2; q<=m; q++)
{
while (t!=0)
{
while (t>0&&T[t+1]!=T[q])
{
t=next[t];
if (T[t+1]==T[q]&&p[t]>k)
t=t+1;break;
else t=next[t];
}
next[q]=t;
}
return (next);
}
}
算法3-1 基于统计特征的模式匹配
同理，对每个出现的字符都做一次这样的运算。可以得出当字符的某次出现没有匹配时，应该移动的最大数。
3.1.2模式中不同的字符的处理
对于模式中不同的字符，此时应该注意一点如果该字符不是优先级最高的字符，那么移动的位置还应该考虑到优先级比它高的字符最多能移动的距离，然后取最大值。以上例为主，假使字符y, q的匹配成功，p匹配不成功，对于q说，至少向右移动15位，而对于y来说至少向右移动17位，那么最终移动的位置要取最大值17位。 通过上面的例子会发现两个现象：
(1)y匹配成功后，只要模式没有完全匹配成功，模式至少可以向右移17位，这种效率在其他算法中是没有的。
(2)在y右移的17位中，有一些的字符根本就没有被比较过，也就是说，这个算法不一定要遍历所有主串S的字符。 这并不是一个特例，在实际运用上面，尤其是在模式比较长的时候，这种优势特别明显。

3.2算法分析
3.2.1算法应用举例
在分析算法之前，先看一个简单的例子：串’aabaaacaaddacac’，在KMP中，
7
每次不匹配可以右移的距离如下：
表3-3 表示在某一位字符上不匹配所对应的移动的位置
a
a
b
a
a
a
c
a
a
d
d
a
c
a
c
1
1
1
3
3
3
4
7
7
7
10
11
11
13
13
在本文介绍的算法中，由于是按照新的排序模式进行匹配，所以，匹配顺序与KMP中的顺序不同，每次不匹配时可以右移的距离如下：
表3-3 表示在某一位字符上不匹配所对应的移动的位置
b
d
d
c
c
c
a
a
a
a
a
a
a
a
a
1
3
11
11
11
13
15
15
15
15
15
15
15
15
15
相比之下可见，按照新的排序模式进行匹配的效率极高。此例并非特例，是各种算法的复杂度进行比较所得。
3.2.2算法比较
下面就KMP、BM两种算法和此算法做个简单的比较。
（1）KMP算法分析：KMP算法效率最高的时候应该对于模式串t1t2…tm中的任意t1t2…tk，都不存在一个j（1过k-1位，也就是说，每比较一位就可以向后移一位，比较次数最多为m。
（2）BM算法分析：BM算法如果在最后一位字符就匹配不成功，并且主串S中的那个字符不在模式中出现，那么也可以向后移n位，但是此时仍然用主串S中的那个字符与模式串T比较了n次，因此BM算法的最好情况也是比较m次。
（3）基于统计特征的模式匹配算法分析：对于匹配序列中的第一个字符（即优先级最高的字符），在模式中出现的位置是随机的，假使在每个位置上出现的概率都是相同的。对于长度为n的模式，匹配序列中第一个字符出现在第i位的概率为1/n，所以该字符出现位置的平均值为：pos=（1+2+3…+n）/n=(n+1)/2。所以当匹配序列中任一字符匹配不成功时跳过的位置d应该是：d>=(n+1)/2；在模式匹配过程中，假设在任一位匹配不成功的概率相等，则在第i位匹配不成功的概率为p=1/n，移动的位数为d>=(n+1)/2。所以每比较一位移动的位数为pos’=d/i>=[(n+1)/2]/[(1/n*n+2/n*n+……+n/n*n)/n]>=1 也就是说，每比较一位就相当于移动了一位，所以，KMP，BM算法最少都要比较m次，而基于统计特征的模式匹配算法最多只要匹配m次。所以通过比较发现该算法明显优于KMP，BM等传统的模式匹配算法的。

8
结束语

通过上面的阐述，可以清出的看出一个问题的提出经常半随着一个新算法的出现，且一个比一个优越、高效，使之更好的应用于实际生活当中。如随着互联网的日渐庞大，信息也是越来越多，如何在海量的信息中快速查找自己所要的信息是网络搜索研究的热点所在，在这其中，字符串匹配算法起着非常重要的作用，这是字符串匹配算法的应用领域之一，前面也提到了其他的应用领域。所以，一个高效的字符串匹配算法，可以极大的提高搜索的效率和质量。本文通过先介绍BF、KMP和BM字符串匹配算法，介绍了各个算法的特点，即原始的朴素字符串匹配算法平均性能很好，而且不需要预处理时间，KMP实现较为简单，BM虽然实现相对于KMP复杂些，但二者均比前者优秀，然而最坏情况下三者均没有多大改进。所以，经过适当的比较和分析，提出了一种新型、人性化的、更为有效的匹配算法—基于统计特征的模式匹配算法，并着重加以介绍，从比较和举例中反应出新算法的优越性和高效性。

9
参考文献

[1] 陈增武：电子计算机算法设计与分析[M]，浙江大学出版社，1986
[2] 娄定俊：算法与算法分析[M]，中山大学出版社，2005
[3] 李雪莹、刘宝旭、许榕生：字符串匹配技术研究[J]，计算机工程[M]，2004，30(20):24-26. [4] 严蔚敏、吴伟民：数据结构[M]，清华大学出版社，2001
[5] 傅清祥、王晓东：算法与数据结构[M]，电子工业出版社，1998
[6] D.Wood，DataStructures，AlgorithmsAndPerfomance，Reading，MA:AddisonWesley，1993
[7] 阮宏一、唐宏亮、杨鹤：数据结构（C/C++描述）[M]，中国水利水电出版社，2007

10