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博文地址:

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180723G1YAPV00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券