grep之字符串搜索算法Boyer-Moore由浅入深(比KMP快3-5倍)

这篇长文历时近两天终于完成了,前些天帮伯乐在线翻译一篇文章《为什么GNU grep如此之快?》,里面提及到grep速度快的一个重要原因是使用了Boyer-Moore算法作为字符串搜索算法,兴趣之下就想了解这个算法,发现这个算法一开始还挺难理解的,也许是我理解能力不是很好吧,花了小半天才看懂,看懂了过后就想分享下,因为觉得这个算法真的挺不错的,以前一直以为字符串搜索算法中KMP算很不错的了,没想到还有更好的,Boyer-Moore算法平均要比KMP快3-5倍。

下面是我对该算法的理解,参考了一些关于该算法的介绍,里面每一张图都画的很认真,希望能讲清楚问题,有什么错误、疑问或不懂的地方麻烦大家一定要提出来,共同学习进步!下面正文开始。

 

1. 简单介绍

在用于查找子字符串的算法当中,BM(Boyer-Moore)算法是目前被认为最高效的字符串搜索算法,它由Bob Boyer和J Strother Moore设计于1977年。 一般情况下,比KMP算法快3-5倍。该算法常用于文本编辑器中的搜索匹配功能,比如大家所熟知的GNU grep命令使用的就是该算法,这也是GNU grep比BSD grep快的一个重要原因,具体推荐看下我最近的一篇译文“为什么GNU grep如此之快?”作者是GNU grep的编写者Mike Haertel。

 

2. 主要特征

假设文本串text长度为n,模式串pattern长度为m,BM算法的主要特征为:

  • 从右往左进行比较匹配(一般的字符串搜索算法如KMP都是从从左往右进行匹配);
  • 算法分为两个阶段:预处理阶段和搜索阶段;
  • 预处理阶段时间和空间复杂度都是是O(m+sigma),sigma是字符集大小,一般为256;
  • 搜索阶段时间复杂度是O(mn);
  • 当模式串是非周期性的,在最坏的情况下算法需要进行3n次字符比较操作;
  • 算法在最好的情况下达到O(n / m),比如在文本串bn中搜索模式串am-1b ,只需要n/m次比较。

这些特征先让大家对该算法有个基本的了解,等看懂了算法再来看这些特征又会有些额外的收获。

 

3.算法基本思想

常规的匹配算法移动模式串的时候是从左到右,而进行比较的时候也是从左到右的,基本框架是:

而BM算法在移动模式串的时候是从左到右,而进行比较的时候是从右到左的,基本框架是:

BM算法的精华就在于BM(text, pattern),也就是BM算法当不匹配的时候一次性可以跳过不止一个字符。即它不需要对被搜索的字符串中的字符进行逐一比较,而会跳过其中某些部分。通常搜索关键字越长,算法速度越快。它的效率来自于这样的事实:对于每一次失败的匹配尝试,算法都能够使用这些信息来排除尽可能多的无法匹配的位置。即它充分利用待搜索字符串的一些特征,加快了搜索的步骤。

BM算法实际上包含两个并行的算法(也就是两个启发策略):坏字符算法(bad-character shift)和好后缀算法(good-suffix shift)。这两种算法的目的就是让模式串每次向右移动尽可能大的距离(即上面的BM()尽可能大)。

下面不直接书面解释这两个算法,为了更加通俗易懂,先用实例说明吧,这是最容易接受的方式。

 

4. 字符串搜索头脑风暴

大家来头脑风暴下:如何加快字符串搜索?举个很简单的例子,如下图所示,navie表示一般做法,逐个进行比对,从右向左,最后一个字符c与text中的d不匹配,pattern右移一位。但大家看一下这个d有什么特征?pattern中没有d,因此你不管右移1、2、3、4位肯定还是不匹配,何必花这个功夫呢?直接右移5(strlen(pattern))位再进行比对不是更好吗?好,就这样做,右移5位后