有关KMP模式匹配算法的探索

摘 要：通过改进的KMP算法对字符串模式匹配算法与传统的KMP算法进行研究，在改进之后，平均比较次数下降明显，能够快速提高字符串模式匹配的工作效率，在应用方面更加节约成本，提高效益。

关键词：KMP；改进；模式匹配算法；字符；分析；算法

中图分类号：TP309

随着计算机技术的不断发展，需要处理的数据内容不断呈现出大量化的特点。近年来，在计算机研究领域内模式匹配问题受到了极大的关注。在串处理系统中，子串在主串中的定位操作是一种重要的过程中，称之为串的模式匹配。随着计算机网络搜索引擎技术的发展、病毒技术的进步以及数据压缩方面的不断发展，模式匹配算法在计算机应用系统中得到了广泛的应用。目前主要的匹配算法有BF算法、KMP算法与一些改进的算法，从方式上，可以分为精确匹配、模糊匹配、并行匹配等。本文重点对KMP算法进行分析，另外对于改进的KMP算法进行研究与展望。

1 简单的模式匹配算法

现代计算机技术不断发展，人们的工作、生活与互联网有着密切的联系，同时网络内容也不断丰富，每一个终端几乎都有可能会上传与下载数据，造成网络上的类似相信也非常多，如何能够从大量的信息中进行查找同样的信息，则需要经过一定的算法。[1]这种典型的应用系统将会使用到匹配算法。简单的模式匹配算法主要是一种查找过程，给出一个特定的字符串P，在一大型的文本中进行查找，从而确定出P是否在大型文本中出现过，如果存在，同时给出相应的出现位置。在以上的算法定义中，为了对数学模式进行简单描述，进行以下符号定义。模式串为P，需要匹配的大型文本主串为T，模式串的长度为m，需要匹配的大型文本主串长度为n，在模式串中首字符与末字符分别为P1与Pm，而需要匹配的主串文本首字符与末字符分别为T1与Tn。文本字符串T与模式字符串P分别是由字符组成的一种集合，强行搜索模式实质上就是把模式P与文本T进行自左向右的挨个搜索，如果模式字符串P在某一点的匹配失败，则立即将T向右移动一个字符的位置，继续从模式字符串P的第一位向右来搜索。[2]这种算法基本上是最符合原理的，但同时它的工作量十分巨大，体现出的效率并不高，需要进行m（n-m+1）次的字母匹配运算，往往给过程浪费大量的时间。现代社会是高效社会，一旦在网络搜索中速度过慢，用户将会失去耐心。目前更多的手持设备在应用搜索时一般是即时搜索，对时间的要求较高，运算量太大的低效搜索模式已经不再满足现代需求。每个网站的用户数量都在不断增大，形成的用户名与密码都需要进行数据储存，利用模式匹配法可以对账户与密码进行匹配，从而判断是否可以登入，否则就进行拒绝，有效提高时间，保护网站利用与用户隐私。这是模式算法的典型应用，随着算法的不断进步，将会在多个网络领域内得以广泛应用。[3]

2 KMP算法

KMP算法目前已经经过了多年的发展，最早是由克努特、莫里斯与普照拉特同时发现，是一种改进的字符串匹配算法，在这种算法中，对主串指针回溯进行了消除，利用已经得到的部分匹配结果把模式串右行一段较远的距离，再次进行比较与匹配，从而使算法的效率得到大幅地提升。这主要是因为在前期的匹配过程经验总结中，一旦某字符不符合模式串的匹配要求，在附近的一段文本中也将不会出现匹配的对象。[4]

KMP的算法思想是当Ti与Pj匹配完成时，主串的指针i与模式的串指针j将会分别加1，不断向后面进行再次匹配，如果Ti与Pj匹配不成功时，主串的指针i保持不动，模式的串指针j将不会回到第一个位置，而是回到一个合适的位置，一旦j回到了第一个位置，将有可能会对需要匹配的文本字符进行错过。主串的指针i保持不动时，算法的关键就在于模式的串指针j指回到了哪一个位置。模式的串指针j不可右移太大的距离，避免错过有效匹配，同时也要右移尽可能地大，以提高匹配效率。在某次字符匹配时，一旦不匹配，模式的前j-1个字符能够匹配，则在下一次匹配时，可以把模式串向右移动j-s-1个字符位置，从而使P1与Tj-s对齐，需要从P3+1开始进行匹配情况检查。为了避免遗漏问题，在以上的首字串必须是最长的，自匹配的部分字串是唯一的，与模式自身结构有关。当模式的第j个字条与主串里的该字符进行比较位置时，它的值主要是取决于模式本身，与主串无关。这时关键是要选择模式的适当位置。

3 改进的KMP算法

模式匹配的KMP算法有效地避免了BM算法中频繁回溯的问题，极大地提高了模式匹配的效率，但这种算法并不是最优秀的。经过长时间的探索与分析，KMP算法中的扫描部分仍然可以进一步改进。[5]

在改进的KMP算法中，当某一次匹配失败时，i指针不需要进行回溯，而是使用已经匹配到的结果，查看是否对i的调整进行必要性评估，之后再决定与向右滑动的位置模式进行比较。主串指针i的有效变化可以有效提高匹配的效率。在进行第一次匹配结束时，j=6处，无法进行匹配时，i指针将会定为6，j指针为6，当模式串向右移动三个位置时，开始进行第二次的匹配，i的指针为9，而j的指针值为3，也就是说从主串的第九位开始进行比较，i值的不断增加也就加快了模式匹配的进度，提高了工作效率。

4 利用改进算法进行多次模式匹配

与单模式匹配算法相比，多模式匹配算法的优势在于一趟遍历可以对多个模式进行匹配，从而大大提高了匹配效率。对于单模式匹配算法，如果要匹配多个模式，那么有几个模式就需要几趟遍历。当然多模式匹配算法也适用于单模式的情况。在入侵检测系统中，一条入侵特征可能匹配或部分匹配很多条规则，如果采用单模式匹配，在匹配每条规则时都需要重新运行匹配算法，效率很低。然而，日益增多的网络攻击使得入侵检测的规则数目仍在不断增长。

在实际的应用中，模式串与主串一般需要多次的匹配，才能找到主串中是否有多次存在相同的子串，如在数据库中进行查找。[6]通过多次模式的匹配可以实现多个子串在文本中的位置，同时可以进行标记，有利于现代计算机庞大数据量的数理与分析。我国人口众多，网民数量庞大，姓名与用户名很可能会出现重复的情况，所以需要提前在数据库中进行查找，以确定是否可用，另外对匹配但其他特性不符的对象进行排除。

5 结束语

随着现代计算机技术的不断发展，越来越多的新技术得以应用与改进。网络安全发展形势也要求提高网络入侵检测系统的性能。模式匹配的效率问题引起了足够的重视。通过对传统的KMP模式匹配算法与其发展状况进行分析，明确未来发展思路，为其实践应用奠定理论基础。

参考文献：

[1]李桂玲.一种改进的KMP模式匹配算法[J].吉林工程技术师范学院学报，2009（10）：75-77.

[2]杨战海.KMP模式匹配算法的研究分析[J].计算机与数字工程，2010（05）：38-41.

[3]陈冬文，张帆，王斌，周启海.模式匹配算法――KMP算法的改进[A].2008中国信息技术与应用学术论坛论文集（一）[C].成都：西南财经大学信息技术应用研究所，2008.

[4]明廷堂.BF与KMP模式匹配算法的实现与应用[J].电脑编程技巧与维护，2013（23）：24-28+34.

[5]范洪博.快速精确字符串匹配算法研究[D].哈尔滨：哈尔滨工程大学，2011.

[6]赵森严，黄伟，李阳铭.一种改进的KMP入侵检测的模式匹配算法[J].井冈山大学学报（自然科学版），2013（01）：55-57.

作者简介：张燕飞（1992-），男，江苏泰兴人，本科，计算机科学与技术专业；李亚琼（1992-），女，贵州凯里人，本科，计算机科学与技术专业。

作者单位：河南大学国际教育学院，河南开封 475001