KMP算法范文
KMP算法范文（精选3篇）
KMP算法 第1篇
关键词：查找搜索,字符串匹配,KMP算法
文本,一直是计算机这一领域中最基本的元素,无论是计算机刚诞生的年代,还是如今多媒体技术绚烂夺目的时代,文本一直都作为奠基性质的元老角色而存在着。
在对文本的编辑中,会遇到需要查找匹配特定模式的情况。比如,在一个文本文件中查找“ABC”这一小段,或者查找“不知道”这一词语。当文本的内容比较少时,人们可以通过简单的逐行查找来找到匹配的特定模式,然而,当文本具备一定的规模后,在其中查找特定的模式就足以令人抓狂了。
在当下这个信息大爆炸的时代,拥有大规模内容的文本实在不在少数,无论是金融界、文学界、政界还是计算机专业界,每天面对大量的文字信息实在令人欲罢不能,在其中寻找重要的关键词、关键句或者关键段落时,更是令人痛不欲生,即使是交给计算机去做,也需耗费大量的开销。因此,设计出一种好的算法,以高效地查找大容量文本文件中的特定匹配模式,不仅可以大大提高文本编辑的响应性能,还能改善人类的生活。
此外,随着学科之间交叉性的提高,很多领域也需要在大量的信息中查找某些特定模式及其出现的位置,例如DNA测序定位、海洋数据查询、高效搜索引擎等。
幸运的是,目前已经有了高效的字符串匹配算法,并且,此类算法仍在不断发展进化,向着更高的效率进发。
在本文中,作者研究分析了效率高超的KMP字符串匹配算法,并使用C语言对其进行了实现。
1 KMP算法研究与分析
历史上人们通过对字符串的研究而得出的字符串匹配问题的算法很多,其中很重要的一类匹配算法分为两步:第一步先对要匹配的模式进行一些预处理,第二步再寻找模式在全文本中的所有有效位移(即匹配)。KMP算法即是其中最高效的算法之一。
KMP字符串匹配算法,是由Knuth、Morris和Pratt三人设计的线性时间字符串匹配算法。假设要搜寻的模式有m个字符单位,整个文本有n个字符单位(一般来说n>m),则KMP算法所用时间花销在n+m这个数量级上,比起很多其他的算法要快不少。
KPM算法简单来说,可以从以下的事实获得灵感:对于在文本中搜寻特殊模式的情形来说,文本所包含的的信息毫无疑问比起特定模式要多得多,其不确定信息也更多。比如,在很长的文本中,下一个出现的字符可能是任何字符,变化可能会很大,然而,对于较短的确定的特定模式来说,在模式中出现的字符却基本上是确定的,因为模式是特别选出的,而且模式比起文本要短得多。一个最常见的例子就是在谷歌中搜寻“平板电脑”这一关键词,很明显,我们对“平板电脑”这四个字中所包含的信息可以说几乎完全确定,而对于在互联网中会出现什么样的网站能匹配这次搜索却包含着极大的不确定性。
因此,可以先对特定模式进行分析,得出所需要的信息,从而利用这些信息来加快匹配速度。
KMP的核心思想,便是充分利用特定模式本身所包含的信息,通过对特定模式的预处理而得出一个前缀函数,从而能够在对文本的匹配搜索中避免一般搜索所花费的无用功。
首先,让我们来看一下什么是前缀函数。
一个字符串的前缀相信不难理解,比如“abc”的前缀可以是“a”也可以是“ab”。在这里,前缀都指的是严格意义上的前缀,比如在刚刚的例子中,“abc”就不是字符串“abc”的前缀。
KMP的前缀函数则是包含有模式与其自身的位移进行匹配的信息的函数。通过前缀函数的生成,我们可以获得特定模式中以每一位字符所引领的前缀匹配原来特定模式的位移,并且通过这个位移,我们可以充分利用特定模式中先前已经与文本比较过的前缀所包含的信息,从而能快速准确地递归得出下一个最大匹配字符数。
以上的描述可以通过以下这个简单的例子来说明:
假设我们的特定模式为“abcabcde”,可以看出,若此模式在搜索匹配时,已经有“abcabc”与文本中的信息匹配上了,却在其后一位不匹配,此时,我们可以充分利用其本身所包含的信息,即“abc”这一前缀可以匹配“abcabc”的后三位,因此,我们可以立即将原模式“abcabcde”在此时文本中进行匹配的位置向文本结尾处移三位,从而以“abc”已经匹配的事实继续检验下一位是否匹配,因为事实上在搜索中文本的下一位是不确定的,所以以“abc”作为新的已经匹配的字符串是完全合理的。
由于在KMP算法中前缀的定义为严格前缀,因此,最终能够递归地完成匹配任务。
由上述描述,可以对KMP前缀函数进行更深入的研究。
现在假设有一特定模式P,且有一文本T,P有q个字符,可以用P[1,2,3q]来表示。现在,已知P[1,2,,y]与T[g+1,g+2,g+3,,g+y]匹配(y
于是,从特定模式的角度来说,可以利用模式与其自身进行比较,以预先计算出需要的信息。由此,现在可以来正式的介绍前缀函数。还是以特定模式“abcabcde”来说明,假设前缀函数为h(i),i为第几个字符的位置,h(i)代表了第i位匹配而第i+1位不匹配时最大的匹配其本身的前缀字符数。例如,在“abcabcde”中,若已经匹配了“abcabc”,其后一位不匹配,可以看出,“abc”是匹配“abcabc”的最长的前缀,因此可以直接将模式向后移三位,即h(6)=3,同时,可知h(1)=0,因为光是一个“a”字符匹配并且下一位不匹配并不能说明什么,没有严格上的前缀子字符串可以使用,只能继续用“a”来与文本的下一个字符进行比较看是否匹配,同理,光是“ab”或者“abc”匹配也无法得到什么,因为当下一位不匹配时这两个字符串都得完全从“a”开始重新匹配,因此,h(1)=h(2)=h(3)=0。在上个例子中,h(i)的全部数值如下:h(1)=h(2)=h(3)=0,h(4)=1,h(5)=2,h(6)=3,h(7)=0。
KMP的前缀函数是整个KMP字符匹配算法的核心,当通过对特定模式的分析而得出前缀函数后,一切就手到擒来了,剩下的只是将特定模式与文本进行比较并使用这个前缀函数。
在与文本匹配时,一开始就像一般的比较字符一样,看开头是否相等,然后比较下一位,若最终整个模式,都被匹配,那则是很幸运的取得了开门红,可以继续比较文本的下一个词;倘若不是整个字符串都能匹配的上,那便可以利用前缀函数所透露的信息,将模式向后移动,直到移到最长的前缀被匹配,然后在比较下一位,相同则继续比较,否则再看前缀函数,再移动直到最长的前缀被匹配。
以上便是KMP字符匹配算法的所有步骤。
KMP这一算法经过无数能人志士的推导和检验,早已证明其是一个高效且易实现的算法,正如前文所述,其所用时间花销在m+n这一数量级上,是各种同类算法中耗时最少的。
下面,作者根据对KMP算法的分析,使用C语言对算法进行了实现。
2 KMP算法实现
根据上文的分析,作者首先写出了KMP算法的伪代码,其中,前缀函数为next(),P为特定模式,T为要匹配的文本,如下所示:
计算前缀函数:
以上便是KMP匹配算法的伪代码,其中,伪代码分为两部分,第一步首先先对特定模式进行分析,生成需要的前缀函数next(),然后第二步再使用生成的前缀函数来配合特定模式与文本进行匹配。
根据如上的分析,作者首先实现了生成前缀函数的C语言源代码:
以上便是使用C语言实现的KMP匹配算法。
可以看到,在程序中,作者首先用getnext()函数生成得到前缀函数的对应于特定模式每一位的数值,然后在kmp()函数中再使用特定模式的字符数组m[]和储存前缀函数相应位数值的next[]数组来对文本中的内容进行匹配查找过程,当获得一处匹配时便返回匹配处在文本中的位置,若整个文本没有内容能匹配特定模式,则kmp()函数最终返回-1。
3 总结
本文探究分析了著名字符串匹配算法KMP算法。在文中,作者分析了KMP算法的思想和原理,并通过简单的例子进行了演示,最后使用C语言对其进行了实现。
KMP算法可以说是字符串匹配算法中运行速度最快的算法之一,相对于同类别的RK算法和有限自动机算法,其速度有可观的提高,并且,算法中充分利用已知信息的思想,也启发着日后算法的发展,相信在不久的将来,会有更高效的算法出现!
参考文献
[1]Mark Allen Weiss.数据结构与算法分析[M].人民邮电出版社,2005.
[2]George F.Luger.Artificial intelligence.China Machine Press,2010.
[3]Robert Sedgewick算法.C语言实现[M].机械工业出版社,2009.
[4]Sedgewick,R&Wayne,K.算法[M].人民邮电出版社,2012.
KMP算法 第2篇
1.1 选题目的及意义
随着网络突飞猛进的发展, 网络媒体已发展为继报纸、广播、电视之后的“第四媒体”, 08年初中国网民数量更是超过了美国成为世界第一。如此惊人的发展速度使得网络已经成为信息的主要载体, 每天都会有大量良莠不齐的信息产生于网络并广泛传播, 网络也成为一些不法分子用来实施犯罪行为或者传播违法信息的重要工具。在此背景下, 公安部门对于网络信息的掌握显得尤为重要。随着公安部门“实施科技强警战略、建立公安情报信息系统”的目标提出, 公安网络信息分析系统的建设需求空前迫切。本文在分析公安部门对网络信息分析系统需求和相关技术的基础上, 结合公安部门已有的“公安情报信息综合平台”探讨研究了网页信息分析系统的设计与实现。
1.2 本课题的研究方向及创新点
1.2.1 本文的研究方向:
本文以互联网信息过滤与定位系统的设计和实现为目标, 深入分析了一个高效的互联网敏感信息审查系统的系统架构和基本工作流程等方面的问题。本文的主要工作如下: (1) 结合国内外有关搜索与模式匹配的技术, 设计了互联网信息审查系统的整体架构; (2) 介绍并分析了系统中三个重要的系统子模块:信息收集模块, 信息预处理模块和关键词发现模块的设计实现; (3) 通过实验证明了该设计中系统架构的可行性及高效性。
1.2.2 本论文的创新点:
(1) 采用KMP快速匹配算法对网页内容进行定位, 效率相对于其他一般模式匹配算法大幅提高; (2) 运用爬虫思想及算法从网络获取信息源, 较人工查找方式实现了工作自动化及高效化。
2 系统的设计与实现
2.1 设计目标与思路
根据《计算机信息网络国际联网安全保护管理办法》中的第五条规定:任何单位和个人不得利用国际联网制作、复制、查阅和传播下列信息:煽动抗拒、破坏宪法和法律、行政法规实施的;煽动颠覆国家政权, 推翻社会主义制度的;煽动分裂国家、破坏国家统一的;煽动民族仇恨、民族歧视, 破坏民族团结的;捏造或者歪曲事实, 散布谣言, 扰乱社会秩序的;宣扬封建迷信、淫秽、色情、赌博、暴力、凶杀、恐怖, 教唆犯罪的;公然侮辱他人或者捏造事实诽谤他人的;损害国家机关信誉的;其他违反宪法和法律、行政法规的。
因此, 开发敏感信息过滤系统旨在实现网络安全监察人员在虚拟复杂的网络世界中及时有效地发现有关情报信息与违法犯罪信息, 为打击网络违法犯罪及时提供有力的依据和线索, 推动监控网络违法犯罪的信息化与自动化。
该敏感信息过滤系统主要实现以下功能。
(1) 多级网页链接获取
一个网站一般包含了多级目录, 即拥有多个超链接, 呈树形结构。而本系统中网页链接获取子系统针对该结构, 采用“网络爬虫”。“网络爬虫”是一个自动提取网页的程序, 是搜索引擎的重要组成。本系统中, 网页链接获取子系统, 根据一定的网页分析算法过滤并保留指定类型的链接, 并将其放入等待抓取的URL队列。然后, 它将根据广度优先的搜索策略, 从队列中的上级站点页面逐级往该站点的下级页面抓取网页URL, 并可根据用户的需求重复上述过程, 直到达到系统中设定的某一条件时停止。
(2) 网页内容分析
1) 网页编码格式分析
在当今网页设计中, 包含中文的编码格式主要有四种, 其分别是:GB2312、BIG5、GBK以及UTF-8格式。其中GB2312是简体中文编码, 其一个汉字占用2字节, 是大陆的主要编码方式。但当网页中包含繁体中文、日文、韩文等等时, 这些内容可能无法被正确编码;
很多国内网页指定的编码都是GB2312的, 它是对ASCII的一种扩展, 而ASCIIGB2312GBK之间是向下兼容的, 但Unicode中的UTF-8与ASCII、GB2312、GBK之间并不兼容, 如果用UTF-8处理其他格式或者其他格式处理UTF-8的中文字符均会出现乱码。因此, 对页面关键字分析之前需要对网页编码格式进行检测与转换。
在UTF-8格式的页面中, 一般包含如下标记:
其中HTTP-EQUIV类似于HTTP的头部协议, 它回应给浏览器一些有用的信息, 以帮助正确和精确地显示网页内容。该标记即在发送文档前通知浏览器该网页采用UTF-8格式的编码, 提前进行编码以实现正常的浏览。该网页内容分析子系统通过分析如上标记中的编码格式, 并提前通过Wide Char To Multi Byt () 函数进行转换, 以达到关键词准确搜索的目的。
2) 基于KMP算法的敏感信息关键词分析
关键词的搜索操作, 即字符串的模式匹配, 是各种串处理系统中最重要的操作之一。其定位函数为Index (S, T, pos) , 其中S为目标串, T为模式串, pos表示第N个字符开始匹配。KMP算法是一种改进的字符串匹配算法, 其关键是根据给定的模式串定义一个next函数, next函数包含了模式串局部匹配的信息。此算法可以在O (m+n) 的时间数量级上完成串的模式匹配操作, 其改进在于:每当一趟匹配过程中出现的字符比较不相等时, 不需要回溯i指针, 而是利用已经得到的“部分匹配”的结果将模式串向右“滑动”尽可能远的一段距离后, 继续进行比较, 极大的缩短的对复杂网页的搜索时间。KMP算法的匹配过程如下:
2.2 基于KMP算法的敏感信息过滤系统软件的实现
软件在VC++6.0集成开发环境中编写实现。其主要由用户界面进程以及负责下载与分析的工作者线程组成。其包含了以下子系统:
(1) 网页获取子系统:其对指定URL的缓存文件进行读取分析, 由于一般的HTML网页中, 标签的href属性用于指定超链接目标的URL, 因此, 获取
摘要：现阶段, 网监部门在对网站进行审查时仍然是以人工方式为主。审查有着海量数据和快速更新的网页信息时, 使用传统统计方法不仅耗费大量人力物力, 而且很容易造成对重要敏感网页信息的遗漏, 无法在较短时间内完成对网站的审查和评估。因此, 作者针对目前公安部门对网络信息分析系统的需求, 开发出高效的网页敏感信息审查软件, 该软件能从海量数据中抽取有价值的潜在信息, 极大地协助网监民警对网页不良和违法犯罪信息进行更加快捷、精准地审查, 在网监工作中有很大的应用前景。
关键词：网页信息过滤,网络爬虫,KMP算法
参考文献
[1]孙鑫.VC++深入详解[M].北京:电子工业出版社, 2012
[2]吴伟民, 严蔚敏[M].北京:清华大学出版社, 2009
KMP算法 第3篇
1 KMP算法思想分析
首先假设主串为s1s2sn’, 模式串为p1p2pm’, 我们从主串的第1个字符起开始匹配, 当主串中第i个字符与模式串中第j个字符“失配” (即比较不等) 时, 主串中第i个字符 (i指针不回溯) 应与模式串中哪个字符再比较?
假设此时应与模式串中第k (k
反之, 若模式串中存在满足式 (3) 的两个子串, 则当匹配过程中, 主串第i个字符与模式串中第j个字符比较不等时, 仅需将模式串向右滑动至模式串中第k个字符和主串中第i个字符对齐, 此时, 模式串前k-1个字符的字串p1p2pk-1’必定与主串中第i个字符之前长度为k-1的子串si-k+1si-k+2si-1’相等, 匹配仅需从模式串中第k个字符与主串中第i个字符比较继续进行。
若令next[j]=k, 则next[j]表明当模式中第j个字符与主串中相应字符不相等时, 在模式中需重新和主串中该字符进行比较的字符的位置, 这一位置只与模式串本身有关而与主串中的字符无关。由此模式串的next函数的定义为:
2 next函数的求解推理及实例设计
对任何模式串p, 只要确定next[i] (i=1, , m) 的值, 当pi≠tj时, 直接右移inext[i]个字符, 使pk (即pnext[i]) 与tj比较, 或使p0与tj+1比较。显然, 不论主串是什么, 在进行字符串匹配之前首先要求得next数组的值。
求next数组第i个元素的值, 实际上就是模式串p中最大相同的前缀与后缀的长度k, 其过程也是一个推理的过程, 分析如下:
根据next函数的定义 (式4) , next[1]的值为0;
假设:next[j]=k;又模式串p的第j个字符与第k个字符相等, 则next[j+1]=k+1;
若:pj≠pk, 则需往前回溯, 检查模式串p的第j个字符与第几个字符相等?这实际上也是一个匹配的过程, 不同在于:主串和模式串是同一个串;
此时, 已有p1p2pk-1’=pj-k+1pj-k+2pj-1’, 当pj≠pk时应将模式向右滑动至以模式中的第next[k]个字符和主串 (实际上也是模式串本身) 中的第j个字符相比较。若next[k]=h, 且pj=ph, 则说明在主串中第j+1个字符之前存在一个长度为h (即next[k]) 的最长子串, 和模式串中从首字符其长度为h的子串相等, 即p1p2ph’=pj-h+1pj-k+2pj-1’ (1
同理, 若pj≠ph, 这将模式继续向右滑动直至将模式中第next[h]个字符和pj对齐, , 以此类推, 直至pj和模式中某个字符匹配成功或者不存在任何h (1
例如, 有模式串p=ababcabababc’, 其对应的next函数值如表1。
根据以上分析, 显然next[1]=0;
而所有next[j]>1的字符均说明在该字符前分别存在有长度为next[j]-1的前缀子串和后缀子串, 比如next[9]=4, 说明在模式串的第9个字符b’之前存在两个长度为3的子串相等, 即p1p2p3’=p6p7p8’, 均为aba’;
所有next[j]=1的字符意味着在该字符之前不存在任何长度的两个子串相等, 比如next[6]=1, 即说明在模式串的第6个字符a’之前不存在任何长度的前缀和后缀相等。
3 结语
字符串匹配的KMP算法本身确实比较难懂, , 大大部部分分学学生生仅仅通通过过读读算算法法和和程程序序很很
摘要：KMP算法是字符串模式匹配算法中效率较高且比较难懂的算法;本文从分析算法思想入手, 设计相关例题以期掌握手工算法, 进而全面掌握算法本身。
关键词：字符串模式匹配,KMP算法,教学设计
参考文献
[1]严蔚敏, 吴伟民.数据结构[M].北京:清华大学出版社, 2002.
KMP算法范文
声明：除非特别标注，否则均为本站原创文章，转载时请以链接形式注明文章出处。如若本站内容侵犯了原著者的合法权益，可联系本站删除。
