26
2017
09

字符串匹配的Boyer-Moore算法

公司内部培训我想讲一讲grep命令的使用,正好网上有一篇文章说GNU grep命令内部字符串匹配算法用的是Boyer-Moore算法,此算法比KMP算法快3到5倍.好,那我们看看Boyer-Moore算法是如何匹配字符串的。

Boyer-Moore算法

在用于查找子字符串的算法当中,BM(Boyer-Moore)算法是目前被认为最高效的字符串搜索算法,它由Bob Boyer和J Strother Moore设计于1977年。

一般情况下,比KMP算法快3-5倍。该算法常用于文本编辑器中的搜索匹配功能,比如大家所熟知的GNU grep命令使用的就是该算法,这也是GNU grep比BSD grep快的一个重要原因。

主要特征

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

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

算法基本思想

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

while(j <= strlen(text) - strlen(pattern)){
    for (i = 0; i < strlen(pattern) && pattern[i] == text[i + j]; ++i);

    if (i == strlen(pattern)) {
        Match;
        break;
    }
    else
        ++j;
}

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

while(j <= strlen(text) - strlen(pattern)){
    for (i = strlen(pattern); i >= 0 && pattern[i] == text[i + j]; --i);

    if (i < 0)) {
        Match;
        break;
    }
    else
        j += BM();
}

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

BM算法实际上包含两个并行的算法(也就是两个启发策略):

坏字符算法(bad-character shift)和好后缀算法(good-suffix shift)。

这两种算法的目的就是让模式串每次向右移动尽可能大的距离(即上面的BM()尽可能大)。

一些说明

假定字符串text为”HERE_IS_A_SIMPLE_EXAMPLE”,搜索词pattern为”EXAMPLE”。

HERE_IS_A_SIMPLE_EXAMPLE
EXAMPLE

首先,”字符串”与”搜索词”头部对齐,从尾部开始比较。

这是一个很聪明的想法,因为如果尾部字符不匹配,那么只要一次比较,就可以知道前7个字符(整体上)肯定不是要找的结果。

我们看到,”S”与”E”不匹配。这时,”S”就被称为”坏字符”(bad character),即不匹配的字符。

如果比较的字符串位置为如下所示:

HERE_IS_A_SIMPLE_EXAMPLE
         EXAMPLE

pattern中的”MPLE”与text完全匹配,我们把这种情况称为”好后缀”(good suffix),即所有尾部匹配的字符串。
注意,”MPLE”、”PLE”、”LE”、”E”都是好后缀。

BM算法理论探讨

坏字符算法

当出现一个坏字符时, BM算法向右移动模式串, 让模式串中最靠右的对应字符与坏字符相对,然后继续匹配。

坏字符算法有两种情况。

Case1:模式串中有对应的坏字符时,让模式串中最靠右的对应字符与坏字符相对(PS:BM不可能走回头路,因为若是回头路,则移动距离就是负数了,肯定不是最大移动步数了),如下图。

这里写图片描述

Case2:模式串中不存在坏字符,很好,直接右移整个模式串长度这么大步数,如下图。
这里写图片描述

好后缀算法

如果程序匹配了一个好后缀, 并且在模式中还有另外一个相同的后缀或后缀的部分, 那把下一个后缀或部分移动到当前后缀位置。

假如说,pattern的后u个字符和text都已经匹配了,但是接下来的一个字符不匹配,我需要移动才能匹配。

如果说后u个字符在pattern其他位置也出现过或部分出现,我们将pattern右移到前面的u个字符或部分和最后的u个字符或部分相同,

如果说后u个字符在pattern其他位置完全没有出现,很好,直接右移整个pattern。

这样,好后缀算法有三种情况,如下图所示:

Case1:模式串中有子串和好后缀完全匹配,则将最靠右的那个子串移动到好后缀的位置继续进行匹配。
这里写图片描述

Case2:如果不存在和好后缀完全匹配的子串,则在好后缀中找到具有如下特征的最长子串,使得P[m-s…m]=P[0…s]。
这里写图片描述

Case3:如果完全不存在和好后缀匹配的子串,则右移整个模式串。

移动规则

BM算法的移动规则是:
将3中算法基本框架中的j += BM(),换成j += MAX(shift(好后缀),shift(坏字符)),
即BM算法是每次向右移动模式串的距离是,按照好后缀算法和坏字符算法计算得到的最大值。

shift(好后缀)和shift(坏字符)通过模式串的预处理数组的简单计算得到。坏字符算法的预处理数组是bmBc[],好后缀算法的预处理数组是bmGs[]。

参考资料

1.字符串匹配的Boyer-Moore算法
http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html
2.grep之字符串搜索算法Boyer-Moore由浅入深(比KMP快3-5倍)
http://blog.jobbole.com/52830/
3.字符串搜索算法Boyer-Moore的Java实现
http://blog.csdn.net/nmgrd/article/details/51697567
4.Boyer-Moore算法学习
http://blog.csdn.net/sealyao/article/details/4568167
5.grep之字符串搜索算法Boyer-Moore由浅入深(比KMP快3-5倍)
http://www.cnblogs.com/lemon66/p/4858890.html

上一篇:聊聊SQLite - 基础篇 下一篇:Java中CyclicBarrier的用法和示例