KMP、BM、Sunday、Horspool、strstr字符串匹配算法的性能比较

KMP、BM、Sunday、Horspool、strstr字符串匹配算法的性能比较

一、简介

简介:字符串匹配算法,顾名思义，在一个给定的字符文本内搜寻出自己想要找的一个字符串，平常所用的各种文本编辑器里的ctrl+F大多就是使用的这些字符匹配算法。本文通过用c语言实现4种比较受欢迎的字符匹配算法，在同一文本下搜寻同一关键字符串，用来和c库函数strstr作时间上的性能比较，同时也对实现的4种算法做对应比较。各个算法名称如下：（对各个算法详细原理感兴趣的伙伴自行去查询，下面只做简要介绍，文中的T都代表文本串,即要搜索的范围，P代表要搜索的目标串，红色代表失配，黄色代表一些P串和T串中相同的字符）

1、strstr():c语言的库函数

函数原型：char* strstr(char* str1,char* str2);//包含在中

原理简述：暴力匹配，从左到右依次匹配。

2、KMP(Knuth-Morris-Pratt)算法:

原理简述：KMP相对strstr做了一些改进，它和strstr一样，都是从左到右依次匹配，当出现失配时，比如，文本串T是“ABCGHABDHKLOEM,”，模式串P是“ABCGHABCF”，当匹配到第八个字符“C”时失配，因为第一、二字符是“AB”，与当前失配字符“C”（第八个）的前两个字符刚好是一样的，于是将整个P串向右移动5个位置，使得第一、二个字符“AB”与文本串T中的"AB"相对，然后继续从P串的第三个字符“C”往后匹配（注意，与当前失配字符的前1个以上字符相等的字符必须是从P串第一个字符开始的，否则不算是满足规则，当不存在时，与strstr一样，只往前移动一个位置）。

实现代码如下：

总结：原理不难理解，但是我们也发现了，KMP的匹配规则是和模式串P的内容有关系的，特别是对那种有大量重复字符的字符串有很大帮助，基于这个匹配规则，每次匹配一个模式串P时，都要相应生成一个辅助数组（人们都习惯成为next数组），这个数组记录着与模式串P中每个字符失配时需要移动的位置数有关的值。具体计算在此不做详细介绍，需要了解的伙伴自行查询。所有的实现代码在上面已给出。

3、BM(Boyer-Moore)算法：

原理简述：BM算法有两个匹配规则，一个是坏字符规则，另一个是好后缀规则。匹配顺序是从右向左（即从模式串p的最后一个字符开始匹配，然后依次向左匹配）。

（1）、坏字符规则：当失配时，若模式串p中当前失配字符的左半部分存在文本串T当前失配字符时，则将模式串整体向右移动，使两个串的相等字符对应匹配，然后又开始从右向左匹配，若模式串p中存在多个该字符时，使用最靠右的一个字符。

如下表a，从右向左匹配，即从P串的最后一个字符"D"开始匹配，由于P串的"D"和T串的"F"不相等，故在P串中找"F",刚好P中有"F",取最靠右的字符"F"，所以P串整体向右移动两个位置，使得P中的"F"和T中的"F"对上，然后又从最后一个字符开始匹配。

a、当失配字符在P串的最右端时

b、当失配字符在P串的中部位置时，

c、若失配时，不存在相同字符,则P串向右移动strlen（P）个位置。

实现代码如下：

（2）、好后缀规则：当已经有部分字符匹配通过，然后遇到失配时，处理方法将会有变化。

若P串中当前失配位置的左半部分（前缀）存在与右半部分相等的子串（即以当前失配字符为边界的右半后缀）或者后缀的子串时，P串将整体向右移动，使得最靠右的该子串(可能存在多个)和T串的相应子串相对，然后重新从最右的字符开始匹配。若左半前缀不存与后缀相同的字符串或者后缀的子串时，P串整体向右移动strlen(P)个位置。(注：若只存在子串时必须是从最左第一个字符往后才算是后缀的子串，如AFCDAF中，第一、二个字符“AF”算是以C为分界的后缀“DAF”的子串，但是对于KAFCDAF来说，同样以C为边界时，前缀中不存在后缀DAF的子串，第二、三个字符AF并不算它的子串，因为第一个字符K和D都不相等了，自然和T串中的已经匹配的“D”也不等，故不用做多余的比较操作了，应该直接跳过)。

a、存在与后缀相同的前缀时；（可在最左）

存在与后缀相同的前缀时；（也可不在最左）

b、存在与后缀子串相同的前缀时；（下表中P串以"D"为边界，后缀为"FAF","AF"属于子串，必须从最左开始）

c、与后缀子串相同的前缀为啥要在最左；

代码如下：

最终的匹配函数如下：

总结：坏字符规则和好后缀规则是独立计算的，最后P串具体按那个规则走，是通过对比两个规则计算出来需要往后移动的位置数的大小，取其中最大的。从原理可看出，BM每次匹配前也需要做预处理，需要针对模式串P分别生成一个坏字符辅助数组和好后缀辅助数组，它们分别存放着各自规则下模式串P的字符发生失配时，需要相应地向右移动的位置数，在此也不做介绍。实现代码如上。

4、Sunday算法：

原理简述：Sunday的处理方式与BM不同的是，它只关注文本串T中当前与模式串P最后一个字符相对应的字符的下一个字符（我说的清楚了吗？），直接上图吧。sunday只关心下图标绿色的“L”。当P串和T串匹配过程中出现失配时，若在P串中当前的失配字符"K"的左半部分（无）不存在T中当前与模式串P最后一个字符"F"相对应的字符"D"的下一个字符"L"时，P串整体向右移动strlen(p)+1个位置。（匹配时从左向右依次匹配）

a、不存在时，整体向右移动strlen(p)+1；

b、当存在时，则和BM的坏字符规则一样，将P串右移使得P串中最右的“L”和T中的“L”相对。

代码如下：

总结：sunday匹配前也需要做一个预处理，生成一个辅助数组，它也是存放着，当发生失配时，模式串P需要向右移动的位置数。

5、Horspool算法：

原理简述：Horspool也是一种改进匹配的算法，它的匹配规则有点像BM的坏字符规则，但是却也不一样，BM的坏字符规则关注当前失配的字符（失配字符可能是在最后一个，也有可能是在中间，也可能在开头），然而当发生失配时，Horspool都只关注T串中与P串最后一个字符相对应的字符（匹配时从右向左依次匹配），如图：

a、失配时(最后一个字符失配)，只关注最后一个字符；

b、失配时(中间字符失配),只关注最后一个字符；

代码如下：

总结：很明显，Horspool也需要一个预处理操作，需要一个辅助数组。

二、测试

1、测试准备工作：

运行环境：

系统：centos6.4

语言：Linux c

（1）、构建一个稍微大一点的文本串，本测试构造的文本串如下图（在程序中赋值给char*型变量，下图是用双引号将文本串用多行显示）；

（2）、选一个关键字符串，本测试选了“MY_TEST_string”作为要匹配的关键字符串；

（3）、 4种自己实现的算法在匹配前都需要一些预处理工作，本文比较中不将这些预处理时间计入运行时间；

2、测试开始：

测试的关键代码如下：（其余四种算法也是相同的处理方式，感兴趣的看官可到GitHub上下载完整代码。

https://github.com/scu-igroup/string_match）

（1）、将关键字符串放文本串开头，然后测试各个算法程序匹配所花时间：

总结：结果很明显，当我们要匹配的字符串在文本串开头时，strstr()远远落后于其他四种算法，而sunday与horspool优于BM、KMP，BM匹配速度相当于KMP的三倍。

（2）、将关键字符串放文本串中间位置，然后测试各个算法程序匹配所花时间：

总结：当我们将匹配的字符串放在文本串中部时，sunday继续保持着优势，horspool也仍然优于BM、KMP，除开让人很惊讶的KMP，strstr相对于其他三种算法来说仍然是垫底（讲道理，KMP不应该表现得如此菜，它应该比strstr快速才对。所以可能是本人的实现代码有问题，在上面已给出实现代码，供各位看官找找错，我实在是汗颜，未能发现问题）。

(3)将关键字符串放文本串末尾，然后测试各个算法程序匹配所花时间：

总结：当我们要匹配的字符串在文本串尾部时，sunday依然一路在秀，可谓是“一枝独秀”，依然完胜其余四种算法。horspool显然被strstr毙掉了，不过它仍然压着BM和KMP。差点让我掉下下巴的KMP，再次成功让我怀疑自己的实现代码有严重的BUG。strstr这次反而“翻身”做老二了，又让小伙伴惊呆了（这时应该有很多看官开始嘲笑了，“Are you fucking kidding me!!!!!”,BM、KMP、Horspool怎么会比strstr慢呢？，这也是我疑惑的地方。。。）

三、总结

从测试结果来看，五种算法中，只有sunday没让我们失望，在三种情境下依然保持着自己的强势匹配速度，而Horspool也不差，一直都领先于BM和KMP。strstr是很多人都在用的函数，毕竟c把它封装好了，用起来方便，它的表现还是相对可以的，毕竟它是暴力匹配，总要多花时间。最让人想不通的就是KMP的表现了，从原理上来说，最次也是和strstr一样（本文测试都把KMP的nxet数组求解过程在预处理阶段给单独处理了，不计入运行时间），毕竟它每一次匹配的跳跃是大于等于1的，而strstr每次都只移动一位。当匹配串在文本串尾部时，BM也没有比strstr快，这也是很出人意外。

四、不足之处

1、样本串的选择没有尽可能覆盖多种情景；

2、strstr是c语言的库函数，它的实现方式应该经过了开发者无数次推敲优化，而自己实现的另外四种算法可能不够优化，多了一些冗余计算，导致没把算法优势最大化，因为strstr是系统内部函数，运行多次可能也会有自动优化；

3、测试方式不够全面，得出的结论有些偏差，仅供大家做参考；

所有完整代码请移步到：

https://github.com/scu-igroup/string_match

CSDN博文地址：