原文链接：机器学习中的数值查找算法(4)——字符串查找算法(Knuth-Morris-Pratt) – 每天进步一点点 (longkui.site)

文本处理过程中，常常会在某个文本信息中查找某个词在其中的出现位置，比较直观的办法是将词在文本信息中依次比较。通过依次比较的方式虽然可以达到目的，但是在比较过程中会有过度匹配的问题。例如，在字符串中 “abcdcdef”中查找字符串“cde”,当依次比较第一个“cd”之后，由于后面的“c”不等于“e”，因此会将“abcdcdef”的下一个位与“cde”会重新进行比较，这是比较容易想到且易于实现的方式。

1.Knuth-Morris-Pratt算法

Knuth-Morris-Pratt算法简称KMP算法，它的名字是由著名的三位科学家名字组合而成。KMP算法是一种高效的字符串查找算法，它性能高效的原因在于它可以利用字符串匹配过程中失败的信息，从而减少字符串查找比较次数。

KMP算法借助了一个辅助的结构部分匹配表，部分匹配表是对搜索词分析产生的一个信息表，部分匹配值是某个字或者字母对应的“前缀”和“后缀”的最长共有元素的长度。

例如，对短文本“海棠小溪还行溪”构建部分匹配表，则将短文本拆成“海”、“棠”、“小”、“溪”、“海”、“棠”、“溪”后，按照如以下步骤进行匹配值分析。

（1）对于“海”，它的前缀和后缀均为空集，因此共有元素的长度为0，所以“海”的部分匹配值为0。

（2）对于“海棠”，它的前缀为“海”，后缀为“棠”，两者的共有元素长度为0。

（3）对于“海棠小”，它的前缀是“海”、”海棠“，后缀为”小“，”棠小“，两者的共有元素为0。

（4）对于”海棠小溪“，它的前缀是“海”、”海棠“、”海棠小“，后缀为“溪”、”小溪“、“棠小溪”，两者的共有元素长度为0。

（5）对于“海棠小溪海”，它的前缀是“海”、”海棠“、”海棠小“、“海棠小溪”，后缀为“海”、“溪海”、“小溪海”、“棠小溪海”，由于“海”是前缀和后缀的唯一公共元素，长度为0。

（6）对于“海棠小溪海棠”，它的前缀是“海”、”海棠“、”海棠小“、“海棠小溪”，“海棠小溪海”，后缀为后缀为“棠”、“海棠”、“溪海棠”、“小溪海棠”、“海棠”是前缀和后缀的公共元素，长度为2。

（7）对于“海棠小溪海棠溪”，它的前缀和是“海”、“海棠“、”海棠小“、”海棠小溪“、”海棠小溪海“、”海棠小溪海棠”，后缀是“溪”、“棠溪”、“海棠溪”、“溪海棠溪”、“小溪海棠溪”、“棠小溪海棠溪”，由于前缀和和后缀没有公共子元素，因此部分配置为0。

通过上述过程形成部分匹配值如下：

部分匹配表是KMP算法进行字符串查找的重要参考信息，因此当有了部分匹配值表之后，针对文本“他在海棠小溪海棠边写的小说《海棠小说海棠溪》”，在其中查找“海棠小溪海棠溪”的过程如以下步骤所示：

（1）从字符串“他在海棠小溪海棠边写的小说《海棠小溪海棠溪》”和搜索词“海棠小溪海棠溪”的首字进行比较。

（2）因为“他”和“海”字不相等，因此将被搜索的字符串后移一位，如下图所示：

（3）由于“在”和“海”字也不相等，因此继续后移被搜索的字符串，直到两个字符串首字母相等的位置。如下图所示：

（4）依次对后续的“棠”、“小”、“溪”进行比较，但是紧接着“边”和“海”并不相等。如下图1所示:

当遇上上述情况时，一般认为当前比较失败，需要将被搜索词从第一个相同的位置的下一个位置开始重新比较。如下图所示：

虽然采取这样的方式是可行的，也能解决问题，但是相对而言效率较差，因为当前被搜索字符串的”棠“是已经被优化比较过。此部分匹配值表则可以起到优化作用。

（5）当移动到图1时，前面的四个字符”海棠小溪海棠“是已经匹配的，因此根据最后一个匹配到字符”棠“，根据一开始的表格提供的部分匹配表，则”棠“对应的匹配值为2，则按照如下公式进行移位:

移动位数=当前已经匹配的字数-最后一个匹配字的匹配值

因此，当6-2=4，则意味着搜索词向后移动4位，如下图所示：

（6）当根据”棠“的匹配值移动后，发现”边“和”小“字依然不相等，因此同理在当前位置查询匹配值，得到的移动位数位2-0-2，因此将搜索词继续移位，如下图所示：

由于”边“与”海“依然不相等，而搜索词的”海“已经是第一个字，因此再依次进行比较，重复上述过程即可。最终匹配到的结果如图：

经过上述KMP算法的匹配过程，可以发现，对于被匹配的字符串不再存在重复匹配的问题，被搜索字符串都会被依次往下进行匹配，匹配性能会高于传统字符串一一对照的比较方式。不同点在于，需要将搜索词建立部分匹配表，建立部分匹配表的时间复杂度位为O(n)。匹配表的实质是搜索字符串中难免存在重复的情况，如字符串”芒果不是芒果“中存在两个”芒果“，那么，”芒果“的部分匹配值为2，在对搜索词进行移动时，第一个”芒果“向右移动4位（字符串长度6与部分匹配值2的差），就到达第二个”芒果“的位置。

KMP算法是一种典型的字符串模型匹配算法，在查找速度上比传统的字符串好，最坏的情况下时间复杂度位O(m+n),即被搜索字符串与搜索字符串的长度之和。此外，由于无须回溯访问被搜索的字符串，因此对于文件流中字符串查找可以达到较好的处理，可以一边读一边进行匹配。在编程时，很多时候都涉及字符串查找，尤其在批量的查找中更希望查找性能越高越好，如在信息检索中，需要快速地提取关键词在文件中的位置，采用KMP算法是一种较好的选择。