字符串匹配-Boyer-Moore算法

Boyer-Moore算法

Boyer-Moore算法是由德克萨斯大学的Robert S. Boyer教授和J Strother Moore教授与1977年发明的。算法的主要思想包括以下两点：

坏字符规则 bad character
好后缀规则 good suffix

下面采用一个例子进行解释:

1 2	"字符串" HERE IS A SIMPLE EXAMPLE "模式串" EXAMPLE

2
1
2
HERE I`S` A SIMPLE EXAMPLE
EXAMPL`E`
可以发现头部对齐时，从尾部开始比较，发现尾部的字符不匹配，那么只要比较一次，就知道字符串的前七个字符不是我们要找的。 S和E不匹配，此时，S就被成为坏字符(bad character)。同时我们发现，S不在模式串EXAMPLE中，因此可以直接将模式串移动到S的后一位。只需比较一次就可以跳7个字符，也是该算法加速的原因之一。
3
1
2
"字符串" HERE IS A SIM`P`LE EXAMPLE
"模式串" EXAMPL`E`
依然从尾部开始比较，发现P与E不匹配，所以P是坏字符。但是， P包含在搜索词EXAMPLE之中。所以，将搜索词后移两位，两个P对齐。

1 2	HERE IS A SIM`P`LE EXAMPLE EXAM`P`LE

因此，我们可以总结出坏字符规则

1	后移动的位数 = 坏字符在模式串中的位置 - 模式串中的坏字符上一次出现的位置

如果坏字符在模式串中不出现，则上一次的位置为-1, 取值-1是因为字符串索引是0-based。

以3中的匹配为例，P是坏字符，出现在模式串的第6位(0-based), 由于模式串中存在该坏字符，且出现的位置为4，所以，后移动的位数为6-4 = 2位。
再以2中出现的S为例，该坏字符出现的位置是6位置，但是在模式串中上一次没有出现，因此，上一次出现的位置为-1, 则整个模式串后移的位数6 - (-1) = 7位。

1
2
3

HERE IS A SIMPL`E` EXAMPLE
         EXAMPL`E`

依然从尾部开始比较，E与E匹配

1
2
3

HERE IS A SIMP`L`E EXAMPLE
         EXAMP`L`E

LE与LE匹配

1
2
3

HERE IS A SIM`PLE` EXAMPLE
         EXAM`PLE`

PLE与PLE匹配

8
1
2
3
HERE IS A SI`MPLE` EXAMPLE
EXA`MPLE`
MPLE与MPLE匹配. 我们把E, LE, PLE, MPLE中出现的字符称为好后缀(good suffix)。
9
1
2
3
HERE IS A S`I`MPLE EXAMPLE
EX`A`MPLE
比较前一位，发现I和A不匹配，所以I是坏字符。
10
1
2
3
HERE IS A SI`M`PLE EXAMPLE
`E`XAMPLE
根据坏字符规则，后移的位数2-(-1) = 3位i, M与E对齐，但是此时，会有一个疑问，有没有更好的移法呢？比3更多呢？
11

1 2	HERE IS A SI`MPLE` EXAMPLE EXA`MPLE`

此时，存在好后缀MPLE，采用好后缀规则。

1	后移的位数 = 好后缀的位置 - 模式串中好后缀上一次出现的位置

好后缀规则的注意点:

12
1
2
HERE IS A SIMPLE EXAMPLE
EXAMPLE
此时的好后缀有E, LE, PLE, MPLE，在四个中间只有E出现，在模式串EXAMPLE中，且出现在头部，所以后移的位数6 - 0 = 6位，可以看到使用好后缀规则移动的更多，比坏字符多出3位。因此Boyer-Moore算法的思想就是每次后移选取两个规则中移动位数最多的。由于，两个规则只和模式串有关，与原字符串无关，因此可以预先制定 坏字符规则表和好后缀规则表，使用时，查表即可。
13
1
2
HERE IS A SIMPLE EXAM`P`LE
EXAMPL`E`
继续从尾部比较，P与E不匹配，因此P是坏字符，根据坏字符规则，后移的位数6 - 4 = 2位，此时没有好后缀。
14
1
2
3
HERE IS A SIMPLE EXAMPLE
EXAMPLE
继续从尾部开始比较，发现完全匹配上了，搜索结束。若还要继续匹配，则使用好后缀规则，使用的是好后缀E, 后移6 - 0 = 6位，继续匹配。

Python 实现

def bad_character():
    pass

def good_suffix():
    pass

def boyer_moore():
    pass

reference