BM算法

 

BM算法

在用于查找子字符串的算法当中，BM（Boyer-Moore）算法是目前相当有效又容易理解的一种，一般情况下，比KMP算法快3-5倍。

用一幅图说明BM算法的原理（来自，A Fast String Search Algorithm, Boyer and Moore）。

图中pat表示模式串AT-THAT,string是需要查找的串，我们就是要在string中找pat,即AT-THAT.

BM的第一个规则（图片上标识为1的地方）：

1、 从后向前匹配。我们看到指针是从pat的最后一个字符开始考虑的。至于为什么这么考虑，我想与英文的单词组成相关，英文单词很多都是采用相同前缀构造的， 还有就是一个单词的很多形式前缀也都是相同的，而后缀不同，所以这样可以尽快的排除不符合要求的单词，使指针在string中快速前移。

2、 如果当前指针指向的字符不在pat中，比如第一步，指针指向F，而F不在pat中，那么显然，pat不可能跟与F有关的任何strinig的字串匹配，于 是下一次，开始匹配位置被移动到F之后，也就是从I这个字符开始考虑，当然了，还是从后向前匹配，所以，我们看到第二步，指针向前移动了 strlen(pat)，指向了-，而pat的第一个字符与I对齐。这就是文章中说的

Since 'F' is known not to occur in pat, we can ....

3、 坏字符规则：我们看到string中指针指向的字符-和pat的最后一个字符T并不相等，这时候，我们将pat右移，但是右移多少呢？我们发现pat中其 实存在字符-，所以，我们就让pat中的字符和当前string中的-对其，这就是第3步上面我们看到的结果。为什么要这么移动？这个理解了就很容易，如 果不能理解一句话还真不能说清楚。你可以想象，如果string的当前字符-能够存在于最终和pat匹配string的子串中，那么显然，-需要和pat 中的某个字符匹配，和哪个呢？自然，-只能和pat中的-匹配，所以需要将它们对齐。

注意，对齐之后，不是从当前对齐的位置开始继续匹配，而是再次从pat的最后一个位置开始匹配，所以，牢记这个规则，只要string的指针发生了跳转，那么，每次总是从pat的最后一个指针开始匹配的。

4、 在图中数字4上面我们看到，string中的T跟pat的最后的字符T匹配，于是指针前移（从后向前），现在居然发现string指针指向的字符L不在 pat中，根据我们前面第一步的说法，L不可能所在的子串不可能跟pat匹配了，所以，pat继续后移，使得pat的第一个字符与L的后一个字符对齐。

5、好后缀规则：这一次很好，string指针指向的T与pat倒数第一个字符匹配，而且倒数第二个A也匹配，但是，倒数第三个就不行 了，string指针指向字符-，而pat指向H，现在我们说利用坏字符规则，在pat中找-，然后让他们对齐，对，这个规则的确可以用，不错，学习很 快。我们很快在pat中找到了-，于是我们说，pat向后移动2个位置（其实就等效于string的指针后移2个位置），使得pat的-和当前的-对齐， 然后继续寻找。

恩，别急。先停下来，让我们想象这样是否是最好的？当我们将pat中的-和当前string指针指向的-对齐的时候，他们的样子是这样的

pat：                             AT-THAT

string：.                   ....... --AT-TH

我 们可以看到，他们不会匹配。因为pat中-后面的字符是TH，而string中的是AT，所以，这时候将pat移动2位是没有用的。然后，我们在pat中 只有继续向前找-，但是，没有了，所以，此时，pat应该移动strlen(pat)才行（即string指针移动strlen（pat））。很好，显 然，后一次移动的幅度要大一些，如果每次我们都能尽可能大的移动string的指针，不是能加快匹配速度吗？

的确如此。

上面第五步中，我们说指针移动两个位置不能解决问题，我们如何知道？是不是一定得重新匹配一次？显然，如果需要重新匹配，我就不花时间研究了。

来看，第五步中，当string指针指向-的时候，此时，pat等待匹配的是倒数第三个字符H，这说明pat中H后面的AT已经匹配了，也就是说，如果将pat右移，那么右移之后必须保证该位置之后依然出现AT字符，才能符合我们已经匹配的目标要求。也就是说，如果

“某字符串”

跟 pat匹配的时候，在倒数第三个字符处出现了不匹配的现象，这时候，如果我们要移动pat的指针到一个新的位置，那么该位置之后的字符串必须保证得和 pat第三个字符之后的串保持一致。否则，就必须移动更大的步长。注意，我说某字符串，而没有说指这里的string，这就是说，在倒数第三个位置不能匹 配的时候，需要移动多少位，是事先可以计算好的。很好，这是关键。由此类推，在任何一个位置，当字符不能和pat中的字符匹配的时候哦，我们都能知道需要 移动多少步长才会可能找到最终的匹配串。解决了一个大问题。

那么，我们注意到了，根据坏字符规则，我们可以得到一个步长，而根据刚刚说的好后缀规则也可以得到一个，用哪个？用大的那个。

这 就是BM算法的精髓，但是我发现要很快理解也不是很容易，我在网站找了一些，都不太好理解，最后下载了A Fast String Search Algorithm, Boyer and Moore这篇文章才明白了一点，但是，如果你读他的叙述一样会头大，最好看看例子，再看表述。至于，那些公式，不必看了，那是为了发文章写的