浅谈KMP模式匹配算法及研究

1、浅谈KMP模式匹配算法及研究               在计算机科学领域，串的模式匹配（以下简称为串匹配）算法一直都是研究焦点之一。在拼写检查、语言翻译、数据压缩、搜索引擎、网络入侵检测、计算机病毒特征码匹配以及DNA序列匹配等应用中，都需要进行串匹配。串匹配就是在主串中查找模式串的一个或所有出现。在本文中主串表示为S=s1s2s3sn，模式串表示为T=t1t2tm。串匹配从方式上可分为精确匹配、模糊匹配、并行匹配等，著名的匹配算法有BF算法、KMP算法

2、、BM算法及一些改进算法。本文主要在精确匹配方面对KMP算法进行了讨论并对它做一些改进以及利用改进的KMP来实现多次模式匹配。 1  KMP算法    最简单的朴素串匹配算法(BF算法)是从主串的第一个字符和模式串的第一个字符进行比较，若相等则继续逐个比较后续字符，否则从主串的第二个字符起再重新和模式串的第一个字符进行比较。依次类推，直至模式串和主串中的一个子串相等，此时称为匹配成功，否则称为匹配失败。朴素模式匹配算法匹配失败重新比较时只能向前移一个字符，若主串中存在和模式串只有部分匹配的多个子串，匹配指针将多次回溯，而回溯次数越多算法的效率越低，它的时

3、间复杂度一般情况下为O(n-m+1)m) （注：n和m分别为主串和模式串的长度），最坏的情况下为O(m*n)，最好的情况下为O(m+n)。KMP模式匹配算法正是针对上述算法的不足做了实质性的改进。其基本思想是：当一趟匹配过程中出现失配时，不需回溯主串，而是充分利用已经得到的部分匹配所隐含的若干个字符，过滤掉那些多余的比较，将模式串向右“滑动”尽可能远的一段距离后，继续进行比较，从而提高模式匹配的效率，该算法的时间复杂度为O(m+n)。     那么如何确定哪些是多余的比较？ 在KMP算法中通过引入前缀函数f(x)来确定每次匹配不需要比较的字符，保证了匹配始终向前进

4、行，无须回溯。假设主串为s1s2，sn.，模式串为t1t2，tm.，其中 mn，从si+1开始的子串遇到一个不完全的匹配，使得：               (1.1)     如果我们能确定一个最小的整数 ，使得：              (1.2)     其中 ，所以确定

5、i' 等价于确定k，这里的k值就是我们要求的前缀函数f(x)。由式1.1和1.2中K值与主串s无关，只与给定的模式串t中与主串匹配的q有关，即k=f(q)， f(q)=maxi|0 i q且t1.i是t1.q的后缀   (1.3)     确定KMP前缀函数的算法如下 ： #define MAXSIZE  100 Typedef unsigned char  stringMAXSIZE+1;/0号单元用来存放串的长度 void f(sstring  t, int *array)  

6、60;  m=t0;/m为当前模式串的长度     array=(int  *)malloc(m+1)*sizeof(int);/0号元不用     array1=0;k=0;     for(q=2;q<=m;q+)         while(k>0&&tk+1!=tq)k=arrayk;         

7、     if(tk+1=tq)k=k+1;             arrayq=k;              关于KMP算法的前缀函数f(x)的示例见表1。      表1  模式串abaabcac I12345678Tiabaabcacf(i)00112010 

8、        当模式串中有i个字符串匹配成功，第i+1个字符不匹配时，则从i-f(i)个字符重新开始比较，这样不仅无须回溯，而且一次可以向前滑动i-f(i)个字符，大大提高了模式匹配的效率。下面给出朴素匹配算法和KMP匹配算法的比较，见表2。 表2 朴素匹配算法和KMP匹配算法比较表  朴素算法KMP算法时间复杂度O(n-m+1)m)O(m+n)向前移动字符个数1q-f(q)回溯次数q-1无    其中：n为主串长度，m为模式串长度，q为匹配成功的字符个数。  &

9、#160; 2  KMP算法的改进     在KMP算法的实际应用中，发现该算法也存在着不足，结合下面的表一来论述KMP模式匹配算法的改进。假设模式串前4个字符与主串的第i+1.i+4匹配成功，第5个字符匹配失败，此时前缀函数f(4)=1，下一次匹配将从第i+4开始，并直接将模式串中的第2个字符与主串中的第i+5个字符进行比较，从表1中可知，匹配必将失败，此次比较是多余的。这说明此时的前缀函数f(x)并不是最优，需要对前缀函数进行改进。实质上，所谓对KMP算法的改进就是对其前缀函数的改进。     从表1可以看出，

10、当t5与主串中的si+5不匹配时，t4+1=tf(4)+1此时f(4)=1，即t5=t2，所以下一次匹配可以跳过i+4-f(f(4)=i+4个字符进行匹配，修改后的前缀函数记为         实现此前缀函数的算法是先调用f()函数，根据1.4式对前缀函数进行修改，算法如下： Void   ff(sstring  t, int *array)      m=t0;      f (t，a

11、rray);     for(q=1 ;q<=m;q+)                  k=fq;            while(k>0&&t k+1=tq+1)           

12、  k=fk;             fq=k            表3 模式串abaabcac关于改进KMP算法的前缀函数ff(x)的示例 I12345678Tiabaabcacff(i)00102010        两表做比较可以发现：f(4)=1>ff(4)=0  

13、60;  如果前4个字符匹配成功，而第5个字符匹配失败，那么改进后的重新匹配次数要减少一次，提高了效率。 3  利用改进算法实现多次模式匹配    在实际应用中，模式串与主串一般要进行多次匹配，以便找到在主串含有多少个这样的子串，典型的应用就是在数据库中的查找。例如输入某人的姓名，然后在姓名这一主串内查找有多少个这样的子串。下面结合前缀函数ff(x)的求解算法给出多次模式匹配的算法： void  match(string s，string t, int a)      n=s0;/主串的长度 &

14、#160;   m=t.0;/模式串的长度     ff(t，f)/求出模式串中各个字符的前缀函数ff(x)     d=0;/该变量用来统计与模式串匹配成功的子串的个数     q=0/该变量表示模式串中与主串匹配成功的字符的个数 for(i=1;i<=n;i+)         while(q>0&&tq+1!=si)       &#

15、160;q=fq;       if(tq+1=si)  q=q+1;       if(q=m) d=d+1;   ad=i-m+1;   4  结 语    本文给出的算法较朴素匹配算法在效率上有了较大的提高，尤其是对重复字符出现较少的数据段进行模式匹配可取得较高的查找效率。应用于大型数据库的数据查询，会更加有效地缩短查找时间。 参考文献1严蔚敏，吴伟民.数据结构M.清华大学出版社， 2001 2傅清祥，王晓东.

16、算法与数据结构M电子工业出版社，1998 3D.Wood，DataStructures，AlgorithmsAndPerfomance，Reading，MA:AddisonWesley，1993 4onnetGH.HandbookofAlgorithmsAndDataStructureM.Addison-WesleyPublishingCompany,1999   “浅谈KMP模式匹配算法及研究”版权归作者所有，转载请著名出处。    一、概述    本设计针对目前暖气泄漏检测的现状及其存在的主要问题，设计了一种基于AT89

17、C51单片机的多路温度巡检系统，采用DALLAS公司的单总线智能温度传感器DS18B20来采集温度采集，采用ATMEL公司生产的的低功耗CMOS串行EEPROM AT24C02来进行采集数据的保存，采用T6963C液晶控制器来进行采集温度的显示，并通过自定义的键盘对本系统进行控制。二、电路设计（一）测温电路的设计本设计是用七个 DS18B20 组成的测温电路，DS18B20 的主要特性：适应电压范围更宽，电压范围：3.05.5V，在寄生电源方式下可由数据线供电；独特的单线接口方式，DS18B20在与微处理器连接时仅需要一条口线即可实现微处理器与 DS18B20 的双向通讯；DS18B20支持多

18、点组网功能，多个 DS18B20可以并联在唯一的三线上，实现组网多点测温；DS18B20在使用中不需要任何外围元件，全部传感元件及转换电路集成在形如一只三极管的集成电路内；温度范围-55+125，在-10+85时精度为±0.5；可编程的分辨率为 912 位，对应的可分辨温度分别为 0.5、0.25、0.125和 0.0625，可实现高精度测温；在 9 位分辨率时最多在 93.75ms 内把温度转换为数字，12 位分辨率时最多在 750ms 内把温度值转换为数字，速度更快；测量结果直接输出数字温度信号，以“一线总线”串行传送给 CPU，同时可传送 CRC 校验码，具有极强的抗干扰纠错能

19、力；负压特性：电源极性接反时，芯片不会因发热而烧毁，但不能正常工作。（二）存储器电路的设计由于单片机内部的存储容量有限，又由于本设计所要储存的数据大于单片机内部的存储容量，所以说外扩一个存储器对本设计而言是非常必要的。本设计采用 ATMEL 公司生产的的低功耗CMOS串行EEPROM AT24C02来进行采集数据的保存，它内含256×8位存储空间，具有工作电压宽（2.55.5V）、擦写次数多（大于 10000 次）、写入速度快（小于 10ms）等2特点，24C02采用的 I C 总线，它通过 SDA（串行数据线）及 SCL（串行时钟线）两根线在连到总线上的器件之间传送信息，并根据地址

20、识别每个器件。（三）按键电路的设计 键盘是单片机应用系统中一个至关重要的部件。它能实现输入数据、传送命令等功能，是人工干预计算机的主要手段。键盘可分为编码键盘和非编码键盘两种。前者用软件来识别和产生代码，后者用硬件来识别。（四）显示电路的设计LCD显示器有分段式和点阵式两种结构。点阵式是在上下两个电极基板上喷上大小和间隔相等、上下对应的电极点阵。其中上电极基板上的每个电极对外均有引线，用于接驱动电压，而下电极基板上的所有电极均接到一个公共电极 COM 上，电极由二氧化锡透明导电材料组成。点阵式可用于文字、图形以及数字显示。分段式 LCD 显示器与 LED 显示器相似，也采用七段式显示。不同的是 LCD 显示器的结构除在上电极基板上喷上 ag 这七个