模式匹配算法的原理及应用.

Presentation on theme: "模式匹配算法的原理及应用."— Presentation transcript:

1 模式匹配算法的原理及应用

2 引言 在计算机科学领域，串的模式匹配（算法一直都是研究焦点之一。在拼写检查、语言翻译、数据压缩、搜索引擎、网络入侵检测、计算机病毒特征码匹配以及DNA序列匹配等应用中，都需要进行串匹配。串匹配就是在主串中查找模式串的一个或所有出现。

3 1.朴素的模式匹配算法 朴素的模式匹配算法的核心思想是:一旦某个字符匹配失败,从头开 始(即从本次匹配起点后一个字符开始 ）.
主串 （S）a b a b c a b c a c b a b 子串 （T）a b c a c （子串又被称为模式串） 红色表示当前这趟比较指针所在位置，兰色表示当前这趟比较中匹配的部分 第一趟（详细过程） a b a b c a b c a c b a b a b c a c a b a b c a b c a c b a b a b c a c a b a b c a b c a c b a b a b c a c 遇到不匹配的地方时指针回朔，每次移动一位

4 1.朴素的模式匹配算法 假如串的长度为m,子串的长度为n的话，那么这个算法在最坏的情况下的时间复杂度为O(m*n) ,
第二趟 a b a b c a b c a c b a b a b c a c 第三趟 a b a b c a b c a c b a b a b c a c 第四趟 a b a b c a b c a c b a b a b c a c 第五趟 a b a b c a b c a c b a b a b c a c 第六趟 a b a b c a b c a c b a b a b c a c _ 完成匹配，跳出 假如串的长度为m,子串的长度为n的话，那么这个算法在最坏的情况下的时间复杂度为O(m*n) , 结论：朴素的模式匹配效率低，机械化地去重复匹配了已经比较过的内容。 问题:有没有办法降低它的时间复杂度呢？ 当然有！ ^_^

5 2.模式匹配算法的改进—KMP算法 由D.E.Knuth, J.H.Morris和V.R.Pratt同时发现的改进模式匹配算法，简称为KMP算法。 其基本思想是：每当匹配过程中出现字符串比较不等时，不需回溯主串，而是充分利用已经得到的“部分匹配”结果，过滤掉那些多余的比较，将模式串向右“滑动”尽可能远的一段距离后，继续进行比较，从而提高模式匹配的效率。 KMP算法核心之处在于：主串指针不用回溯，直接前进！不匹配时子串指针回退。 该算法的时间复杂度为O (m+n)。

6 2.模式匹配算法的改进—KMP算法 2.1Next的函数的引出:
分析：要想改进模式匹配的算法,必须减少无效比较,让起点自动移到当前认为的最理想的位置,而不是仅仅只移一位.但是,计算机怎么知道要移几位呢? 解决方法：设置一个next数组 那么next的函数到底是什么呢? next[j]表示当模式串中第j个字符与主串某个字符比较失败后,起点应该向后移几位. (j=next（j）)

7 2.模式匹配算法的改进—KMP算法 2.2Next的函数的定义和计算: 求next数组本质上就是一个模式串T和自己进行匹配的过程 。

8 2.模式匹配算法的改进—KMP算法 void getnext (SString t, int next[]) { int j=1,k=0;
while (j <= t.len) if (k==0 || t.date [j] == t.date [k]) j++; k++; next [j]=k; } else k=next [k]; // j不变（不回溯）,k回溯 } 时间复杂度为O(n)

9 2.模式匹配算法的改进—KMP算法 2.3主程序 int kmpindex ( SString s, SString t ) {
int next [ Maxlen ],i=1,j=1,v; getnext ( t,next ); while (i<= s.len && j <= t.len ) if (j==0 || s.date [i] == t.date [j]) i++; j++; } else j = next [j]; //避免多余比较，匹配串指针回退到next[j]的位置 if ( j > t.len ) v = i - t.len; // 若找到,返回主串的匹配首址 else v=-1; //若没找,返回-1 reture v; } 时间复杂度位O(m)

10 2.模式匹配算法的改进—KMP算法 主串S a b a b c a b c a c b a b 子串T a b c a c
next（j） 按照KMP算法，我们再来看看前面我们举的例子。 第一趟 a b a b c a b c a c b a b a b c a c 第二趟 a b a b c a b c a c b a b a b c a c 第三趟 a b a b c a b c a c b a b a b c a c _ 完成匹配，跳出

11 修正next [j] 我们看下面的序列 S: aabaabbaaaaaab T: aaaab next(j) 01234
这样求出来的next串还不一定最优必须找到更优的next数组。 T串中的‘a’和S串中的‘b’失配，而‘a’的next值指的还是‘a’，那同样的比较还是会失配，而这样的比较是多余的，如果事先设定，当T[i]==T[j]，那next[i]就设为next[j]，在求next值的时候就已经比较了，这样就可以去掉这样的多余的比较。于是稍加改进得到： T: aaaab nextval(j)

12 源代码：求修正的nextval[j] void getnextval(SString t, int nextval[]) {
int j=1,k=0; nextval[1]=0; while (j<=t.len) if (k==0|| t.date[j]==t.date[k]) j++;k++; if (t.date[j]!=t.date[k]) nextval[j]=k; else nextval[j]=nextval[k]; //消去多余的比较 } else k=nextval[k];

13 KMP算法的C#源代码 # include <stdio.h> # include <string.h>
//kmp algorithm //getNext 求模式串t[ ]的next[ ]---即滑动位置数组 int * getNext( int t[ ], int nextVal[ ] ) { int i = 1，j = 0; nextVal[1] = 0; while( i < t[0] ) if ( j == 0 || t[i] == t[j] ) i++;j++; if ( t[i] != t[j] ) nextVal[i] = j; else nextVal[i] = nextVal[j]; } else j = nextVal[j]; return nextVal;

14 KMP算法的C#源代码 //indexKMP ------kmp主程序
int indexKMP(char s[ ], int t[ ], int next[ ], int pos ) { int i = pos; //主串指针 int j = 1; //模式串指针 while( i < strlen(s) && j <= t[0] ) //t[0]: t[ ]的长度 if ( j == 0 || s[i] == t[j] ) i++; j++; } else j = next[j]; if (j > t[0] ) return i-t[0]; else return -1; //若没找,返回-1

15 谢谢！