基于KMP算法的字符串查找匹配研究

陈天一 郑闻悦 邹健 邱修峰

摘   要：目前，有学者提出了一种特殊的符号语言，了解到其文字是由20个字母组成。目前已获得许多段由该语言写成的文本，但缺少标点符号与空格，导致无法理解其中的含义与规律。本文针对在不同段由特殊语言组成的文本中搜索在误差允许范围内相同的字母序列片段问题，建立了基于KMP算法的相似字符串搜索匹配算法模型，在特定的多个文本中找出符合题意的子串，依据已知条件自定义模型生成外星语文本段落对该算法进行检验，评判其优缺点并进一步优化分析。

关键词：KMP算法  字符串  查找匹配  主串  子串

中图分类号：TP31                                   文献标识码：A                       文章编号：1674-098X（2019）08（b）-0242-02

根据语言学家的猜测，在每段文本中都会出现的序列片段很可能具备某种固定的含义。因此，如何在不同段文本中搜索在误差允许范围内相同的字母序列片段，将对该未知语言的研究提供重要的理论依据。

在不同段文本中搜索相同的字母序列片段可以通过字符串匹配算法来实现。这里我们基于使用较为普遍且高效的算法模型——KMP算法创建了相似字符串搜索匹配算法。此算法针对的是已知的字符串序列在文本串中进行定位，而这里的序列片段是未知的。首先本文通过构词法组建出6000个包含15～21个字母的单词，将其作为词汇库，之后规定1500个为高频词汇，另外4500个为低频词汇，分别以80%和20%的概率随机抽选入30段文本中，形成我们所需的文本数据。在此基础上，再使用相似字符串搜索匹配算法进行主串与子串之间的匹配，得到分析结果。最后，我们对结果进行了检验，评估模型的准确度和高效性，同时针对算法中存在的问题提出了优化与改进措施。

1  原始KMP算法的过程

基于对不同段文本中相同的字母序列片段进行查找，采用原始的KMP字符串匹配算法对不同文本中的字符串进行匹配，具体流程如下。

假设现在文本串S（主串）匹配到i位置，模式串P（子串）匹配到j位置，即模式匹配过程执行到比较字符Si和Pj，其中0≤i≤n-1，0≤j≤m-1。

（l）若当前字符匹配成功，即Si=Pj，则继续往右匹配下一个字符，即对Si+1和Pj+1进行匹配检测。

（2）若当前字符匹配失败，即Si≠Pj，此时当j=0时，则对Si+1和Pj进行匹配检测，即把子串和主串向右移动一位再从子串的第一个字符进行匹配;当1≤j

经判断，KMP算法的时间复杂度为O（m+n），空间复杂度为O（m）。

2  建立相似字符串搜索匹配模型

我们首先采用KMP算法对生成的文本数据进行了匹配，发现符合条件的字母序列数量非常少，由此进行了相关分析，具体如下。

如图1，进行主串与字串的匹配，倘若目前主串匹配到2号位置，子串匹配到0号位置。假设容错为4个字母，则大方框标注出来的区域即是允许容错的范围。

如图2，基于对前面过程的理解，主串S[2，3，4，5]与字串P[0，1，2，3]在容错范围内可以进行相互匹配，但当主串i到达6号位置，字串j到达4号位置时，字母不匹配，超出容错范围，则匹配失败。

如图3，针对以上存在的问题，我们在KMP算法的基础上加入了变异的概念，提出了以KMP为基础的相似字符串搜索匹配模型以提高匹配的准确度。在上述情况下，当匹配失败时，主串i返回3，子串j返回0进行匹配，即令i=i-j+1。这样，算法的准确度会大大提高。

3  结果分析

我们定义了一个相似片段的概念，在这个相似片段中，我们匹配到的不是仅仅一个字符子串，而是一个字符片段。运行算法，我们得到匹配结果。图4内容为程序运行时匹配出来的一些相似片段，由于篇幅有限，未全部截取。通过这个相似片段我们可以发现在外星语中出现频率高的子串。

4  结语

在此基础上，本文更进一步分析发现由于容错性的存在，next數组不是解决相似字符串匹配问题的关键，由此提出了基于KMP的相似字符串搜索匹配模型，通过对主串进行一定程度的回溯缓解现有KMP模型在相似字符串匹配问题上的不适用性，大大提高了算法的精确度。相比于KMP算法，该模型虽然准确度得到了提高，但是由于主串回溯的原因提高了其时间复杂度。因此，在保证精确度的基础上提高其运行速度是该模型今后进行优化的关键。

参考文献

[1] 蔡婷，杨卫帅.一种改进的字符串模式匹配算法[J].物联网技术，2017，7（7）：89-91，95.

[2] 邵岚，唐永群，孔令顺.一种基于KMP算法思想的字符串匹配算法的研究与实现[J].网络安全技术与应用，2018（12）：61-67.

[3] 黄厚柱.相似字符串查找算法研究[D].安徽大学，2017.