转自：http://blog.csdn.net/joylnwang/article/details/6785743
1977年，Robert S.Boyer和J Strother Moore提出了另一种在O(n)时间复杂度内，完成字符串匹配的算法，其在绝大多数场合的性能表现，比KMP算法还要出色，下面我们就来详细了解一下这一出色的单模式匹配算法，在此之前推荐读者读一下我的另一篇文章《KMP算法详解》，对于透彻理解BM算法大有裨益。
在讲解Boyer-Moore算法之前，我们还是要提一提KMP算法的老例子，当模式串与目标串匹配至如下位置时：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 |
| b | a | b | c | b | a | b | c | a | b | c | a | a | b | c | a | b | c | a | b | c | a | c | a | b | c |
| a | b | c | a | b | c | a | c | a | b |
BM算法之所以能够在单模式匹配中有更加出色的表现，主要是其使用了两个跳转表，一个是坏字符表（论文中称为delta1），一个是好后缀表（论文中称为delta2），下面我们以BM算法对目标串的一次匹配操作，来讲解这两个表的具体跳转策略，这里模式串为"AT-THAT"，目标串为"WHICH-FINALLY-HALTS.--AT-THAT-POINT"。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | |
| W | H | I | C | H | - | F | I | N | A | L | L | Y | - | H | A | L | T | S | . | - | - | A | T | - | T | H | A | T | - | P | O | I | N | T | |
| 1 | A | T | - | T | H | A | T | ||||||||||||||||||||||||||||
| 2 | A | T | - | T | H | A | T | ||||||||||||||||||||||||||||
| 3 | A | T | - | T | H | A | T | ||||||||||||||||||||||||||||
| 4 | A | T | - | T | H | A | T | ||||||||||||||||||||||||||||
| 5 | A | T | - | T | H | A | T |
第一次，pattern[1]与target[1]对齐，从pattern[7]向前依次与target执行比较，但是第1次比较就发现，target[7]='F'，而'F'不是pattern串中的字符，所以target中包含target[7]的任何子串都不可能与pattern匹配，此时我们可以直接将pattern串滑动到target[7]之后，让pattern[1]与target[8]对齐，然后再由target[14]依次向前执行比较。
第二次，target[14]='-'，虽然'-'是模式串中的字符，但是如果要target串中包含target[14]的字串与pattern串匹配，则至少target[14]需与pattern中最后一个'-'对齐。而pattern中只有一个'-'pattern[3]，所以将target[14]，与pattern[3]对齐，然后再由target[18]向前依次执行比较。
第三次，虽然target[18]=pattern[7]='T'，但是target[17]='L'，'L'不是pattern中的字符，所以包含target[17]的任何字串都不可能与pattern匹配，所以pattern[1]直接与target[18]对齐再执行匹配。
第四次，target[23...24]=pattern[6...7]，target[22]!=pattern[5]，我们注意到，pattern[6...7]=pattern[1...2]所以pattern[1...2]也是模式串的一个自包含后缀（下文详述），所以我们可以令pattern[1]与target[23]对齐再向后执行匹配，此时我们就发现了满足条件的匹配串target[23...29]。
该示例使用到了BM算法中的所有跳转优化，大幅加速了模式串的向后滑动过程，实现了模式的快速匹配，其中第1，2，3次滑动使用的是算法中的坏字符移动规则，第4次滑动使用的是好后缀移动规则，那么什么是所谓的坏字符和好后缀规则呢。
所谓的坏字符移动规则，就是一个表，其以输入字符集的所有字符作为索引，每个输入字符c对应着一个值，表示如果目标串的当前位置字符c与模式串匹配失败，那么目标串当前位置应该可以向前滑动的步数。假设字符集为"ABCDEFGHIJKLMNOPQRSTUVWXYZ-"，那么他对应模式串"AT-THAT"的坏字符表为。
| A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | - | |
| delta1 | 1 | 7 | 7 | 7 | 7 | 7 | 7 | 2 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 0 | 7 | 7 | 7 | 7 | 7 | 7 | 4 |
坏字符表的定义为，对于输入字符集合中的字符c，如果c不在模式串中，则delta1[c]= patlen（模式串的长度），如果c在模式串中，则delta1[c]=j-i，其中，j是模式串最末元素的索引值，i是字符c在模式串中最右出现的位置（这里与Boyer-Morre两人的论文略有差别，主要是因为BM的论文中，字符串的索引从1开始，其最末元素的索引值，就等于模式串的长度，而在实际计算模式串中含有字符的坏字符滑动值时，使用到的是模式串最末元素的索引值，这个值与模式串的长度不一定相等）。下面就是用于生成坏字符表的代码，为了简单起见，这里没有使用字典结构，而是假设输入的字符只能是A-Z，然后将这26个字符映射到一个数组中。
- inline void BuildBadC(const char* pattern, size_t pattern_length, unsigned int* badc, size_t alphabet_size)
- {
- unsigned int i;
- for(i = 0; i < alphabet_size; ++i)
- {
- badc[i] = pattern_length;
- }
- for(i = 0; i < pattern_length; ++i)
- {
- badc[pattern[i] - 'A'] = pattern_length - 1 - i;
- }
- }
所谓的好后缀移动规则，是BM算法的核心部分，下面详细说明。在KMP算法中，我们知道了所谓的前缀自包含问题，也就是模式串的前缀也可能是模式串的非前缀子串。在BM算法中，有一个与其非常相似的概念，叫后缀自包含。对于pattern[1...j]，存在长度为k的子串，满足pattern[m+1...m+k]=pattern[j-k+1...j]，其中k<j，0<m<j-k。以字符串"BCDBCDABCDABCD"为例，pattern[7...10]就是一个包含后缀，因为pattern[7...10]=pattern[11...14]。
我们定义数组pre[]，与pattern中的元素一一对应，对于pattern中的元素，pattern[i]，pre[i]是使得pattern[k+1...j-i]=pattern[i+1...j]，且pattern[k]!=pattern[i]的k的最大值，如果不存在这样的k，pre[i]=patlen。对于对于模式串的后缀k pattern[j-k+1...j]，满足条件的包含后缀可能不止一个，这里我们需要关注所有满足条件的pattern[m+1...m+k]中，满足pattern[m] != pattern[j-k]的m的最大值。对于上例的模式串，其后缀3 pattern[12...14]，其包含后缀有pattern[8...10]，pattern[4...6]，pattern[1...3]，在这3个包含后缀中，pattern[7]=pattern[11]，所以pattern[8...10]不是我们想要的包含后缀。pattern[0] != pattern[11]（这里面我们假设pattern[0]不等于任何可输入字符），pattern[3]!=pattern[11]，在这两个备选子串中，pattern[4...6]的m值(3)大于pattern[1...3]的m值(0)，所以pattern[4...6]就是我们需要的pre值。对于为什么要满足pattern[m]!=pattern[j-k]，请参考我的《KMP算法详解》一文中对于next[j]与f(j)不同之处的解释，以及本文后面算法正确性方面的说明。
现在我们发现了pattern[12...14]在模式串中的包含后缀pattern[4...6]，此时如果我们发现目标串target[n]与模式串pattern[11]比较失败，我们就直接可以将pattern[3]与target[n]对齐，然后再从target[n+11]处向前依次与模式串进行匹配。目标串当前位置的跳转距离goods[i]=j-pre[i]。
这里我们需要解释一下如此大幅跳转的正确性。还是以上述模式串为例，当target[n]与pattern[11]匹配失败时，我们需要找到一个适当的位置，令target[n+1...n+3]与pattern[k+1...k+3]相同，才有可能找到匹配结果，这里target[n+1...n+3]=pattern[12...14]。根据pre[i]的定义，只有当k=3时，才能保证pattern[12...14] = pattern[4...6]，对于任何k>3都有pattern[12...14] != pattern[k+1...k+3]，因为如果存在k>3使得pattern[12...14] = pattern[k+1...k+3]，那么pre[11]必然大于3。所以这一对齐方式不会漏过中间可能的匹配。
这里读者可能会有疑问，你说的实际是错的，对于k=7，有target[n+1...n+3]=pattern[8...10]，为什么不让target[n]与pattern[7]对齐，然后从target[n+7]位置开始依次向前比较呢？这个问题和KMP算法中next[j]和f(j)的不同之处一样。虽然有pattern[8...10]=pattern[12...14]，但是pattern[7]=pattern[11]。因为target[n] != target[11]，所以target[n]!=pattern[7]所以将target[n]与pattern[7]对齐所执行匹配尝试必然失败，所以target[n]可以直接跳过pattern[7]直接与pattern[3]对齐。
另一方面，如果target[n]与pattern[k]对齐，但是pattern[k+1...j]在模式串中不存在包含后缀，我们该如何决定模式串向后的滑动距离呢。此时target[n+1...n+j-k] = pattern[k+1...j]，因为pattern[k+1...j]不存在包含后缀，所以对于任何m(0<=m<k)，pattern[m+1...m+j-k]!=pattern[k+1...j]（m<k+1），所以将target[n]与pattern[m]对齐，相当于执行pattern[k+1...j]与pattern[m+1...m+j-k]的匹配，结果必然失败。
此时可以考虑pattern[1]与target[n+1]对齐。pattern[1]与target[n+1]对齐后，pattern[1...j-k]是模式的前缀j-k，target[n+1...n+j-k]相当于pattern[k+1...j]，因为pattern[k+1...j]不存在包含子串，所以此次匹配也会失败。继续移动pattern[1]，pattern[1]与target[n+2]对齐，此时target[n+2...n+j-k]相当于pattern[1...j-k-1]，与pattern[k+2...j]比较，此时两者是否相等依赖于我们之前计算pre表的结果，能够使这个匹配成立的是使pattern[1...m]=pattern[j-m+1...j]的m的最大值，将pattern[1]与target[n+j-k-m+1]对齐，如果这样的m不存在，则pattern[1]可以直接与target[n+j-k+1]对齐，再执行匹配。如下例，当在target[4]处发生匹配失败，根据之前的介绍，pattern[1]与2，3，4，5，6对齐也都会失败，这里j=9,k=4,m=3,n=4。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | |
| target | A | B | C | D | X | X | A | B | C | . | . | . | . | . | . |
| A | B | C | X | X | X | A | B | C | |||||||
| A | B | C | D | X | X | A | B | C | |||||||
| A | B | C | D | X | X | A | B | C |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | |
| B | C | D | B | C | D | A | B | C | D | A | B | C | D | |
| pre[i] | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 3 | 14 | 14 | |
| goods[i] | 24 | 23 | 22 | 21 | 20 | 19 | 18 | 17 | 16 | 15 | 11 | 13 | 12 | 1 |
- inline void BuildGoodS(const char* pattern, size_t pattern_length, unsigned int* goods)
- {
- unsigned int i, j, c;
- for(i = 0; i < pattern_length - 1; ++i)
- {
- goods[i] = pattern_length;
- }
- //初始化pattern最末元素的好后缀值
- goods[pattern_length - 1] = 1;
- //此循环找出pattern中各元素的pre值，这里goods数组先当作pre数组使用
- for(i = pattern_length -1, c = 0; i != 0; --i)
- {
- for(j = 0; j < i; ++j)
- {
- if(memcmp(pattern + i, pattern + j, (pattern_length - i) * sizeof(char)) == 0)
- {
- if(j == 0)
- {
- c = pattern_length - i;
- }
- else
- {
- if(pattern[i - 1] != pattern[j - 1])
- {
- goods[i - 1] = j - 1;
- }
- }
- }
- }
- }
- //根据pattern中个元素的pre值，计算goods值
- for(i = 0; i < pattern_length - 1; ++i)
- {
- if(goods[i] != pattern_length)
- {
- goods[i] = pattern_length - 1 - goods[i];
- }
- else
- {
- goods[i] = pattern_length - 1 - i + goods[i];
- if(c != 0 && pattern_length - 1 - i >= c)
- {
- goods[i] -= c;
- }
- }
- }
- }
现在BM算法的两个基本工具坏字符，好后缀都已具备，我们如何在目标串target[1...n]中飞快的找到我们想要的模式pattern[1..j]呢。
首先，我们将pattern[1]与target[1]对齐，然后从target[j]向前依次执行匹配操作。如果在pattern[i]位置发现匹配失败，则在好前缀表里用i查找滑动距离goods[i]，在坏字符表中用target[i]做索引，查找滑动距离badc[target[i]]，假设前者返回的值为p，后者返回的值为q，这时我们取其中的较大者（假设为p），然后将pattern[j]与target[i+p]对齐，然后依次向前匹配，直到发现匹配，或者遍历整个target串没有找到目标模式为止。下面是BM算法的实现代码，该算法与之前KMP算法一样，都进行了扩展，可以找到目标串中的所有匹配模式，相比之下，BM扩展为找到目标序列中的所有匹配模式串要比KMP简单，不需要引入任何新的东西，只需要在发现匹配模式之后，仍然按照goods[0]移动目标串游标即可。
- unsigned int BM(const char* text, size_t text_length, const char* pattern, size_t pattern_length, unsigned int* matches)
- {
- unsigned int i, j, m;
- unsigned int badc[ALPHABET_SIZE];
- unsigned int goods[pattern_length];
- i = j = pattern_length - 1;
- m = 0;
- //构建好后缀和坏字符表
- BuildBadC(pattern, pattern_length, badc, ALPHABET_SIZE);
- BuildGoodS(pattern, pattern_length, goods);
- while(j < text_length)
- {
- //发现目标传与模式传从后向前第1个不匹配的位置
- while((i != 0) && (pattern[i] == text[j]))
- {
- --i;
- --j;
- }
- //找到一个匹配的情况
- if(i == 0 && pattern[i] == text[j])
- {
- matches[m++] = j;
- j += goods[0];
- }
- else
- {
- //坏字符表用字典构建比较合适
- j += goods[i] > badc[text[j]-'A'] ? goods[i] : badc[text[j]-'A'];
- }
- i = pattern_length - 1;
- }
- return m;
- }
后记：
- 对于进阶的单模式匹配算法而言，子串（前缀/后缀）的自包含，是至关重要的概念，是加速模式匹配效率的金钥匙，而将其发扬光大的无疑是KMP算法，BM算法使用后缀自包含，从后向前匹配模式串的灵感，也源于此，只有透彻理解KMP算法，才可能透彻理解BM算法。
- 坏字符表，可以用于加速任何的单模式匹配算法，而不仅限于BM算法，对于KMP算法，坏字符表同样可以起到大幅增加匹配速度的效果。对于大字符集的文字，我们需要改变坏字符表的使用思路，用字典来保存模式串中的字符的跳转步数，对于在字典中没有查到的字符，说明其不在模式串中，目标串当前字符直接滑动patlen个字符。