字符串匹配算法的研究-本科论文.docx

字符串匹配算法的研究及其程序实现计算机学院计算机科学与技术专业2007级 指导教师：滕云摘要：在字符串匹配算法之中，最古老和最著名的是由D. E. Knuth, J. h. Morris, V. R. Pratt 在1997年共同提出的KMP算法。直至今日，人们对字符串匹配问题还在进行着大量的研究，以寻求更简单，或者平均时间复杂度更优的算法;学者们在不同的研究方向上，设计出了很多有效的匹配算法。在现实生活中，串匹配技术的应用十分广泛，其主要领域包括：入侵检测，病毒检测，信息检索，信息过滤，计算生物学，金融检测等等。在许多应用系统中，串匹配所占的时间比重相当大，因此，串匹配算法的速度很大程度上影响着整个系统的性能。该论文重点分析了KMP算法的实现原理和C语言实现，并在此基础上提出了改进的KMP算法，使得该算法更方便实用。关键词：KMP算法；时间复杂度；串匹配；改进；方便使用；String matching algorithm and Implementation of the ProgramCollege of Computer Sciences, Computer Science and Technology Professional grade 2007, Instructor YunTengAbstractor: Among the string matching algorithm, the oldest and most famous is KMP algorithm co-sponsored by D.E Knuth, J. h. Morris, VR Pratt in 1997. As of today, a lot of research to String matching are still in progress, to seek a more simply or better average time complexity of the algorithm. In different research direction, scholars have designed a lot of valid matching. In real life, the string matching technique is widely used，The main areas include: intrusion detection, virus detection, information retrieval, information filtering, computational biology, financial inspection and so on. In many applications，a large percentage of the time was placed by the string matching, so the string matching algorithms significantly affect the speed performance of the whole system. The paper analyzes the implementation of the KMP algorithm theory and through the C language to achieve it. And we puts forward a modified KMP algorithm in order to makes the algorithm more convenient and practical.显示对应的拉丁字符的拼音字典1. 动词 1. improve2. better3. make betterKey words: KMP algorithm; Time complexity; String matching; Improved; Easy to use;显示对应的拉丁字符的拼音字典目录摘要 1ABSTRACT 1第一章 引 言 3第一节：字符串匹配研究的目的和意义3第二节：本文的内容和安排 3第二章 串匹配算法的概念与研究现状 4 第一节：字符串匹配的有关概念 4 第二节：字符串匹配算法的研究现状 4第三章KMP算法和BM算法及其改进算法的研究及实现5第一节：KMP算法的研究及实现5第二节：KMP算法改进及其程序实现8第四章 总结和展望12第一节：总结13第二节：展望13参考文献 14致谢 14第一章：引言第一节：字符串匹配研究的目的和意义字符串是计算机科学中常见的基本概念，搜索问题也是计算机科学中的基本问题。而且迄今为止文本信息仍然还是最主要的信息交换手段之一，因此作为文本处理中的一个重要领域字符串匹配，就显得尤其的重要，随着互联网的日渐庞大，信息也是越来越多，如何在海量的信息中快速查找自己所要的信息是网络搜索研究的热点所在；在这其中，字符串匹配算法起着非常重要的作用，一个高效的字符串匹配算法，可以极大的提高搜索的效率和质量。本文力图阐明字符串匹配算法的发展过程中的两个重要的算法KMP算法和BM算法，并且并介绍了各个算法的特点，并给予了适当的比较和分析，进而提出了新的字符串匹配算法希望能够在各方面有所改进。字符串匹配技术有着十分广泛的应用领域，它的最直接的应用领域是构建数据的全文检索系统和图书文献目录摘要的查询系统。尤其在近年来，网络技术马不停蹄的快速发展，网络带宽不断增加，随之出现的问题也越来越多，加之随着网络技术和生物技术的不断发展，串模式匹配技术又在网络安全，网络信息检索和生物计算等领域中发挥着重要作用，并不断发展。而且在对大量黄色信息，反动言论和国家机密的过滤方面以及入侵检测技术和内容过滤技术方面字符串匹配算法也扮演者一个不可或缺的角色。随着生命科学技术的发展，人们对生命物质的微观结构的认识越来越清晰。而且人类基因组序列的绘制工作目前己经完成。计算生物学中的一个最基本问题是，寻找一个或一组基因片断在一个基因序列中的出现位置，以比较基因的相似性和遗传关系；或者根据己知的蛋白质样本去匹配未知的蛋白质序列，来确定这种未知的蛋白质序列所属蛋白质的种类和功能。由于蛋白质和基因都可以使用建立在一定字符集上的符号序列来表示，因而传统的字符串匹配技术又有了新的发挥之地。尤其是近些年来的发展，科学家们对基因发生的突变和进化等变化进行研究，来描述同一物种的基因序列可能存在一定的差别，所以这就促进了“近似匹配”技术的又一提高和发展。综上所述，字符串匹配技术在众多的领域中发挥着基础的核心作用，对字符串匹配算法作进一步的研究和改进，对于提高执行的效率、增加应用系统的性能、节约硬件成本等有着重要的现实意义。第二节：本文的内容和安排本文通过对经典字符串匹配算法的深入理解和分析，在KMP算法的基础上提出了两种改进算法，并且给出了程序实现代码，经过分析和测试确定其性能得到提高，在某些方面都达到了较高的水平。本文的后续的章节安排为：第二章将对字符串匹配算法的概念进行归纳并总结其研究现状；第三章详细分析字符串匹配算法：KMP算法，并提出相应的新的改进算法，而且深入分析所涉及到的经典算法的思想以及程序的实现方法，并且将改进后的算法与之比较，得出改进后算法的优点。最后第四章进行总结和展望。第二章 串匹配算法的概念与研究现状第一节：字符串匹配的有关概念字符串是n ( 0 ) 个字符的有限序列，记作 S : “c0c1c2cn-1”。其中，S是串名字；“c0c1c2cn-1”是串值；ci是串中字符；n是串的长度。 如：“Welcome to Linux world !”模式匹配是串的基本运算之一。它是指在串中寻找子串（第一个字符）在串中的位置。有两个字符串T和，字符串T称为正文，字符串S称为模式，要求找出模式S在正文T中的首次出现的位置。一旦模式S在正文T中找到，就说发生一次匹配。有些应用可能会要求找出所有的匹配位置。算法复杂度分为时间复杂度和空间复杂度。其作用： 时间复杂度是度量算法执行的时间长短；而空间复杂度是度量算法所需存储空间的大小。KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法的时间复杂度为O(m+n). 第二节：字符串匹配算法的研究现状近年来，学术界的兴趣与日俱增，特别在生物信息学和信息检索两个领域中，需要处理的文本规模越来越大，而且需要在文本中进行越来越复杂的搜索。因此，出现了一种非标准的模式匹配问题,该问题涵盖的内容包括通配符、近似匹配等等。近期，学术界最活跃的问题之一就是研究带有通配符的串匹配问题。即带有dont care或wildcard字符。然而，通配符的引入会让问题定义更加灵活，却也带来了复杂性。算法的设计有时不仅仅考虑时空效率，保证匹配结果的完备性很可能成为算法设计更重要的问题。在串匹配研究领域中，一个人所共知的事实是“算法的思想越简单，实际应用的效果越好”。另外，随着新一代计算机的产生，会出现一些新技术，例如位并行等。然而KMP算法依然占据着不可替代的作用，尤其是他们的优化版更是应用广泛。第三章：KMP算法和BM算法及其改进算法的研究及实现第一节：KMP算法的研究及实现KMP算法是一种线性时间复杂的字符串匹配算法，它是对BF算法（Brute-Force，最基本的字符串匹配算法的）改进。由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此人们称它为克努特莫里斯普拉特操作（简称KMP算法）。KMP算法的关键是根据给定的模式串W1,m,定义一个next函数。next函数包含了模式串本身局部匹配的信息。首先，我们引入一个叫失败链接值(faillink)的概念，就是说“每当一趟匹配过程中出现字符比较不等时，不需回溯i指针，而是利用已经得到的部分匹配结果（匹配串的每个字符的失败链接值）将模式（匹配子串）向右滑动尽可能远的一段距离，继续进行比较。”其实质失败链接值就是一个和主串完全无关只和子串相关的值。当子串某一位和主串“失配”了（其实这句话还应该理解为到子串这一位前面的都和主串“相配”），则跳到失败链接值的那一位上去（简称失败链接位），使得失败链接位上的那个字符继续和主串当前字符进行比较，如果不匹配再跳到失败链接位的失败链接位上去，如果还不匹配就接着往前跳，一直跳到某一位和主串目前位置上的字符相同或者跳到子串最开头为止。而这个失败链接位是怎么求出来的呢，举个例子来说，子串为aac，我们现在要求的是c这一位(j=2)所对应的失败链接值，也就是说，c前面部分即aa已经和主串相配了，而c没能和主串相配，那么要跳到前面的哪一位上去呢，假设主串是aaab(绿色部分的aa已经确定)，那么，子串只要向右移动1位即做到如下对应即可:主串：a a a b a a a b字串：a a c a a c 位置：0 1 2 也就是在0j-1之间(在这儿是01之间)找到一个数k(在这里是1)，使得c前面k位字符串和子串的第k位前面k位字符串相等, 这么一来就能保证在子串向右移动（也就是k指针向子串左边的错误链接位跳）了之后仍然有k指针指向的那一位前面的k长度部分的字符串和j指针指向的那一位前面的k长度部分的字符串即主串i指针指向的那一位前面的k长度部分的字符串相同,这也正是移动后(即j跳到k所指位置后)仍能保证j前面部分和主串i前面相同长度部分字符串相同的必要条件。这个k的值也就成为了j的失败链接值(即flinkj=k)，k所对应的位置就成了j所对应位置的失败链接位.。如果错误链接位上字符和当前位上字符相同的话，可以直接让当前位的错误链接值等于错误链接位的错误链接值(当然都是就子串来说的)，这样可以将程序更加优化。求s的各字符的失败链接值算法： 引入数组next，元素个数为S的长度，依次存放S各字符的失败链接值。先置next0 = -1，在已求得next0，nextj-1的情况下，求nextj.如nextj-1=k,又有sk=sj-1，那末置nextj为nextj-1+1;如果sksj-1，令k1=nextk,如有sk1=sj-1,则置nextj为k1+1;如果sk1sj-1,则按sk1的失败链接值再继续寻找，直至找到一个失败链接值kn,使得skn=sj-1，或者kn = -1，这时就置nextj = kn+1。 寻找模式各字符失败链接值的函数： void faillink(char *s, int next) int j, k; next0 = -1; for(j = 1;sj != 0;j+) k = nextj-1; while (k != -1 & sk+1 != sj) k = nextk; if(sj=sk+1) nextj = k+1; else nextj = -1; 具体的KMP算法C语言实现代码如下:假设又两个随机的字符串S和T，例如主串S=acdfgawedgawekmah和子串T=gawek，则由此可知其其匹配的起始下标为10。#include#include#define N 50void GetNext(char t,int next)next1=0;int j=1,k=0,h;h=strlen(t);while(jh)if(k=0)|(tj=tk)j+;k+;nextj=k;break;else k=nextk;void main() printf(姓名 李春豹 学号 200713140114n);char sN,tN;int nextN=0;printf(请输入主串s:n);gets(s);printf(请输入模式串t:n);gets(t);int i=1,j=1,k=strlen(s)-1,h=strlen(t)-1;while(i=k)&(jh)printf(匹配的起始下表为:%dn,i-j+1);elseprintf(匹配失败n);执行结果见下面的截图：第二节：KMP算法改进及其程序实现根据上一节的学习，我们知道KMP算法是在一直串模式的next函数值的基础上执行的，那么如何求得模式串的next函数值呢？首先我们来了解下next数组的含义：令原始串为: Si，其中0=i=n；模式串为: Tj，其中0=j=m。假设目前匹配到如下位置S0,S1,S2,.,Si-j,Si-j+1.,Si-1,Si,Si+1,.,SnT0,T1,.,Tj-1,Tj, .S和T的红色部分匹配成功，恰好到Si和Tj的时候失配（粉红色），如果要保持i不变，同时达到让模式串T相对于原始串S右移的话，可以更新j的值，让Si和新的Tj进行匹配，假设新的j用nextj表示，即让Si和nextj匹配，显然新的j值要小于之前的j值，模式串才会是右移的效果，也就是说应该有nextj = j -1。那新的j值也就是nextj应该是多少呢？我们观察如下的匹配：（1）.如果模式串右移1位，即nextj = j - 1，即让绿色的Si和Tj-1匹配(注：省略号为未匹配部分)S0,S1,S2,.,Si-j,Si-j+1.,Si-1, Si, Si+1,.,Sn T0,T1,.,.Tj-1, Tj, .(T的划线部分和S划线部分相等) T0,T1,.Tj-2,Tj-1,.(移动后的T的划线部分和S的划线部分相等)根据可以知道当nextj =j -1，即模式串右移一位的时候，有T0 j-2 = T1 j-1。而这两部分恰好是字符串T0 j-1的前缀和后缀，也就是说nextj的值取决于模式串T中j前面部分的前缀和后缀相等部分的长度。(2).如果模式串右移2位，即nextj = j - 2，即让绿色的Si和Tj-2匹配S0,S1,.,Si-j,Si-j+1,Si-j+2.,Si-1, Si, Si+1,.,Sn T0,T1,T2,.,Tj-1, Tj, .(T的划线部分和S划线部分相等) T0,T1,.,Tj-3,Tj-2,.(移动后的T的划线部分和S的划线部分相等)同样根据可以知道当nextj =j -2，即模式串右移两位的时候，有T0 j-3 = T2 j-1。而这两部分也恰好是字符串T0 j-1的前缀和后缀，也就是说nextj的值取决于模式串T中j前面部分的前缀和后缀相等部分的长度。（3）.依次类推，可以得到如下结论当发生失配的情况下，j的新值nextj取决于模式串中T0 j-1中前缀和后缀相等部分的长度，并且恰好nextj等于这个最大长度。因而我们进而得到求出该数组的算法为：void get_nextval(SString T ,int nextval )/将模式串T的next函数值并存入数组nextval中int i= 1; nextval1= 0; j= 0;while(iT0)if(j=0|Ti=Tj) +i; +j;If(Ti!=Tj)nextvali=j;elsenextvali= nextvalj; elsej=nextvalj;/get_nextval进而我们得到KMP算法的匹配函数如下：Char *kmpMatch(char *t, char *s, int next) int k, j; k = j = 0; while(sj != 0 & tk != 0) if (sj = tk) k+; j+; else if(j = 0)k+; else j = nextj-1+1; if (sj = 0) return t + k - j; return NULL; 我们研究的目的是经过对KMP算法的改进可以实现对主字符串中的所有字串出现的匹配点都找出来，并且统计其各自的匹配的起始下标。具体的改进后的KMP算法C语言实现的源代码如下：假设又两个随机的字符串S和T，例如主串S=acdfgawedgawekmagawekacdgege gawekbmahbn和子串T=gawek;#include #include #include#define N 50void faillink(char *t, int *flink) int j, k = -1; int lent = strlen(t); flink0 = -1; for (j=0; jlent-1; j+) while (k!=-1) & (tj!=tk) k = flinkk; flinkj+1 = k+1; k+; int index(char *s, char *t, int *p) int i, j = 0, tot = 0; int *flink = new intstrlen(t); faillink(t, flink); int lens = strlen(s); int lent = strlen(t); for (i=0; ilens;) while (j!=-1) & (si!=tj) j = flinkj; j+; i+; if (j=lent) ptot = i-j; tot+; i-; j-; j = flinkj; delete flink; return(tot);int main() printf(姓名 李春豹 学号 200713140114n);char aN,bN;int nextN=0;printf(请输入主串a:n);gets(a);printf(请输入模式串b:n);gets(b); int p50; int tot; tot = index(a, b, p); cout主串：aendl; cout子串：bendlendl; cout匹配数目：totendl; if (tot!=0) cout匹配位置：; for(int i=0; itot; i+) coutpit; coutendl; coutendl; return(0);执行结果见下面的截图：通过以上改进使我们的KMP算法的功能更复杂更强大，能够在一个字符串中轻易的找到你想查找的字符串，更方便、更实用。例如给我一个主串和其他多字符串，问哪些字符串是这个主串的子串，这些问题在以后的软件开发中用到的话就可以直接拿去用，实在是很方便。因为我想windows中的搜索引擎的查找功能是不是也运用了这种算法呢，只要输入某篇文章中的几个关键字，就能很快的搜索出它是什么文章，这不是和我们的简单的字符串查找很相似嘛。第四章：总结与展望第一节：总结KMP算法，即Knuth-Morris-Pratt算法，是一种典型的基于前缀的搜索的字符串匹配算法。KMP算法的搜索思路应该算是比较简单的：模式和文件进行前缀匹配，一旦发现不匹配的现象，则通过一个精心构造的数组索引模式向前滑动的距离。这个算法相对于常规的逐个字符匹配的方法的优越之处在于，它可以通过数组索引，减少匹配的次数，从而提高运行效率。掌握了KMP算法就明白了各个搜索引擎工作的工作原理，都是通过字符串匹配来实现迅速查找的，迅速、准确。我不会忘记这难忘的几个月的时间。毕业论文的制作给了我难忘的回忆。在我徜徉书海查找资料的日子里，面对无数书本的罗列，最难忘的是每次找到资料时的激动和兴奋在整个过程中，我学到了新知识，增长了见识。在今后的日子里，我仍然要不断地充实自己，争取在所学领域有所作为。脚踏实地，认真严谨，实事求是的学习态度，不怕困难、坚持不懈、吃苦耐劳的精神是我在这次设计中最大的收益。我