BoyerMoore 算法分析

匹配方向从右向左开始匹配从 ^ 的位置开始向左匹配

aaaaaFaaaaaaaaaaaaaa
aaaaaaa
      ^

一、坏字符匹配

坏字符源串中第一个不匹配的字符就是坏字符F 是坏字符

aaaaaFaaaaaaaaaaaaa
aaaaaaa
     ^

指针移动方式1

如果坏字符不在模式串中则将指针向右移动“模式串长度”个字符重新开始比较

aaaaaFaaaaaFaaaaaaa
      aaaaaaa
     -------^

解释当前模式串为 7 个 a所以指针向右移动 7 个字符目的是把 F 排除于下次比较的范围如果移动不足 7 个字符那么 F 就进入了下次比较的范围由于 F 不在模式串中让它进入比较范围没有意义。

重新比较之后再次遇到坏字符 F

aaaaaFaaaaaFaaaaaaa
      aaaaaaa
           ^

指针继续向右移动 7 个字符

aaaaaFaaaaaFaaaaaaa
            aaaaaaa
           -------^

完成匹配。

指针移动方式2

如果坏字符在模式串中则需要在开始搜索之前先找出模式串中各个字符最后出现的位置然后记下该位置之后还有多少个字符。

aaaaabaaaaabccbcaaa
aabccbc

不看源串只看模式串
最右边的 a 之后有 5 个字符
最右边的 b 之后有 1 个字符
最右边的 c 之后有 0 个字符

记录该数据的目的是为了让指针能够跳转指定的长度但是字符 c 所记录的数据 0 却没有使指针产生移动所以最后一个字符不应该被记录这样我们就需要使用前一个 c 的位置来记录也就是 c 之后有 2 个字符于是有了下面的跳转表

如果遇到坏字符 a则指针向右移动 5 个字符
如果遇到坏字符 b则指针向右移动 1 个字符
如果遇到坏字符 c则指针向右移动 2 个字符
如果遇到其它坏字符则指针向右移动“模式串长度”个字符

开始比较

aaaaabaaaaabccbcaaa
aabccbc
      ^

遇到坏字符 a指针向右移动 5 个字符

aaaaabaaaaabccbcaaa
     aabccbc
      -----^

解释跳转表中记录的遇到 a 应该跳转 5 个字符目的是为了让源串中的坏字符 a 与模式串中的字符 a 对齐如果跳转不足 5 个字符则模式串中没有任何字符可以与源串中的 a 匹配上因为 5 就是 a 在模式串中最后一次出现的位置再往后就没有 a 了。

重新比较之后再次遇到坏字符 b

aaaaabaaaaabccbcaaa
     aabccbc
           ^

根据跳转表中的记录遇到 b 应该使指针向右移动 1 个字符

aaaaabaaaaabccbcaaa
      aabccbc
           -^

重新比较之后再次遇到坏字符 a

aaaaabaaaaabccbcaaa
      aabccbc
          ^

指针向右移动 5 个字符

aaaaabaaaaabccbcaaa
         aabccbc
          -----^

完成匹配。

前面提到的跳转表叫做“坏字符跳转表”使用该表已经可以实现字符串快速查找。

二、好后缀匹配

为了进一步提高速度BoyerMoore 算法还提出了另一种匹配方式叫做“好后缀”匹配。

好后缀匹配过程中已经匹配的部分就是好后缀ba 是好后缀

aaFbaaaaaba
aaaba
  ^

指针移动方式1

如果好后缀在模式串中没有重复的部分比如 ababa 中后缀 ba 就与前一个 ba 重复这就不符合当前的情况则将指针向右移动“模式串长度+已匹配长度”个字符重新开始比较

aaFbaaaaaba
-----aaaba
  -------^

说明模式串刚好移动到源串上次匹配的 ba 之后因为模式串向右移动的原则是“使源串中上次匹配的 ba 与模式串中离好后缀 ba 最近的某个 ba 对齐”可是好后缀左边没有重复的 ba所以无法与源串中的 ba 对齐那就只能将模式串整个移动到源串的 ba 之后。

重新比较之后没有出现好后缀

aaFbaaaaaba
     aaaba
         ^

只能向右移动一个字符

aaFbaaaaaba
     -aaaba
         -^

完成匹配。

指针移动方式2

如果好后缀在模式串中有重复的部分则将指针向右移动“好后缀到最后一个重复部分之间的距离+已匹配的长度”个字符重新开始比较

aaaaaaFbabaCbaCba
abaCbaCba
      ^

因为好后缀 ba 前面有重复的 ba所以需要将离好后缀最近的 ba 与源串中上次匹配的 ba 对齐

aaaaaaFbabaCbaCba
---abaCbaCba
      -----^

此时没有匹配的后缀只能将模式串向右移动一个字符

aaaaaaFbabaCbaCba
   -abaCbaCba
           -^

此时仍然没有匹配的后缀只能将模式串向右移动一个字符

aaaaaaFbabaCbaCba
    -abaCbaCba
            -^

此时出现好后缀 baCba

aaaaaaFbabaCbaCba
     abaCbaCba
        ^

这个好后缀比较特殊它是有重复部分的只不过前后重叠在一起

aaaaaaFbabaCbaCba
     abaCbaCba
        ^
         ^^^^^
      ^^^^^

此时需要将重复部分移动到源串中上次匹配的 baCba 位置

aaaaaaFbabaCbaCba
     ---abaCbaCba
        --------^

完成匹配。

如果有多个连续的重复部分则可以一次跳过所有这些重复部分例如

aaaaaaaFbababababa
bababababa
        ^

按照一般思路应该将离好后缀最近的一个 ba 与源串中上次匹配的 ba 对齐但是因为这些重复 ba 是相连的既然 F 与好后缀 ba 之前的 a 不匹配那么所有相连的 ba 前一个字符都是 a都不可能与 F 匹配所以可以一次跳过所有相连的 ba将最左边的重复 ba 与源串中上次匹配的 ba 对齐即可

aaaaaaaFbababababa
--------bababababa
        ---------^

完成匹配。

好后缀也有一个跳转表只需要在搜索之前计算好就可以实现快速搜索好后缀的跳转表计算起来要比坏字符复杂一些。

BoyerMoore 算法同时使用“坏字符”和“好后缀”两种跳转方式每次遇到坏字符时也会出现好后缀然后选择两种跳转方式中跳转距离更远的作为本次跳转长度。

在 FPC 的 StrUtils 单元中有 BoyerMoore 算法的实现可以参考。