Boyer-Moore字符串搜索算法

蔚落 2022-06-18 00:55 244阅读 0赞

该算法的主要观点是：如果将模式的结尾与文本进行比较，则可以进行文本跳转而不是检查文本的每个字符。这样做的原因是将文本排列在图案中，将图案的最后一个字符与文本中的字符进行比较。如果字符不匹配，则不需要沿着模式继续向后搜索。如果文本中的字符与模式中的任何字符不匹配，则要检查的文本中的下一个字符沿着文本位于n个更远的位置，其中n是模式的长度。如果文本的字符是在图案，然后沿着文本的图形的局部移做是为了沿着匹配字符排队，并重复该过程。

*注释：摘自维基百科[Boyer-Moore字符串搜索算法][Boyer-Moore]*

--------------------

Boyer-Moore算法很有效率，来我们用发明者的一个例子说明下原因：

待匹配字符串：EXAMPLE
    待搜索词：HERE IS A SIMPLE EXAMPLE

### 第一次比较： ###

![这里写图片描述][SouthEast]

根据算法思想比较待匹配字符串最后一位和待搜索词 **S** 和 **E** 不匹配，则 **S** 前面的字符肯定不包括待匹配字符串，将待匹配字符串后移7位。

### 第二次比较： ###

![这里写图片描述][SouthEast 1]

**P** 和 **E** 不匹配，但是P在待匹配字符串里面，根据**坏字符规则**，应该将待匹配字符串后移至两个 **P** 对齐：

![这里写图片描述][SouthEast 2]

到这里可以总结下**坏字符规则**：

*  像第一次比较中的 **S** 一样，不存在于待匹配字符串中的，直接将待匹配字符串后移到底。
 *  像第二次比较中的 **P** 一样，存在于待匹配字符串中的，将待匹配字符串移动至相同字母的位置。

*我看到阮一峰总结的公式了，但是我觉得非要套公式很烦哟。*

### 第三次比较： ###

![这里写图片描述][SouthEast 3]

依然从末尾开始比较，**E** 匹配成功，接着匹配上一位。

### 第四次匹配： ###

![这里写图片描述][SouthEast 4]

**LE** 匹配成功，接着匹配上一位。

### 第五次匹配： ###

![这里写图片描述][SouthEast 5]

**PLE** 匹配成功，接着匹配上一位。

### 第六次匹配： ###

![这里写图片描述][SouthEast 6]

**MPLE** 匹配成功，接着匹配上一位。

### 第七次匹配： ###

![这里写图片描述][SouthEast 7]

**I** 和 **A** 不匹配，这个时候根据**坏字符规则**我们应该后移2位

![这里写图片描述][SouthEast 8]

然而这个时候我们要想啊，直接将待匹配字符串移动至两个 **E** 对齐的地方接着比较岂不是更好？如果你这么想那你很棒哟，这属于Boyer-Moore算法中的**好后缀规则**，这一段的规则直接摘自阮一峰自己总结不来，一会用白话翻译下。

**公式：　后移位数 = 好后缀的位置 - 在待匹配字符串中上一次出现位置**

举例来说，如果字符串”ABCDAB”的后一个”AB”是”好后缀”。那么它的位置是5（从0开始计算，取最后的”B”的值），在”搜索词中的上一次出现位置”是1（第一个”B”的位置），所以后移 5 - 1 = 4位，前一个”AB”移到后一个”AB”的位置。

再举一个例子，如果字符串”ABCDEF”的”EF”是好后缀，则”EF”的位置是5 ，上一次出现的位置是 -1（即未出现），所以后移 5 - (-1) = 6位，即整个字符串移到”F”的后一位。

**这个规则有三个注意点：**

1.  “好后缀”的位置以最后一个字符为准。假定”ABCDEF”的”EF”是好后缀，则它的位置以”F”为准，即5（从0开始计算）。
2.  如果”好后缀”在搜索词中只出现一次，则它的上一次出现位置为 -1。比如，”EF”在”ABCDEF”之中只出现一次，则它的上一次出现位置为-1（即未出现）。
3.  如果”好后缀”有多个，则除了最长的那个”好后缀”，其他”好后缀”的上一次出现位置必须在头部。比如，假定”BABCDAB”的”好后缀”是”DAB”、”AB”、”B”，请问这时”好后缀”的上一次出现位置是什么？回答是，此时采用的好后缀是”B”，它的上一次出现位置是头部，即第0位。这个规则也可以这样表达：如果最长的那个”好后缀”只出现一次，则可以把搜索词改写成如下形式进行位置计算”(DA)BABCDAB”，即虚拟加入最前面的”DA”。

回到上文的这个例子。此时，所有的”好后缀”（MPLE、PLE、LE、E）之中，只有”E”在”EXAMPLE”还出现在头部，所以后移 6 - 0 = 6位。

![这里写图片描述][SouthEast 9]

*这段话简洁翻译一下，所谓的好后缀规则指的是让待比较字符串移动到待匹配字符串和待搜索词有相同的后缀的地方，当然要考虑和坏字符规则哪个后移的多选取哪一个*

### 第八次匹配： ###

![这里写图片描述][SouthEast 10]

**P** 和 **E** 不匹配，且 **P** 存在于待匹配字符串中，这个时候根据**坏字符规则**我们应该后移2位

![这里写图片描述][SouthEast 11]

接下来一直匹配…

--------------------

总结下来一共匹配15次，效率确实很高。

--------------------

*说明：本文的图是来自阮一峰的博文，感觉这个图做的非常好，很能突出重点，就放弃了自己动手画*

参考链接：[阮一峰的Boyer-Moore算法博客链接][Boyer-Moore 1]

[Boyer-Moore]: https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm
[SouthEast]: /images/20220618/f78cf4acfc864384a275a23dbb8dd4ae.png
[SouthEast 1]: /images/20220618/1e810b161c5a43228db019815c808984.png
[SouthEast 2]: /images/20220618/c8d261e21c59438d888d2fe4fd4b153d.png
[SouthEast 3]: /images/20220618/f1c0cab370834a5689295092005949f9.png
[SouthEast 4]: /images/20220618/28f92ab61aa84fe6b4ad2452896634cb.png
[SouthEast 5]: /images/20220618/55fa6f0d39644f7c871e81e0870b0ef7.png
[SouthEast 6]: /images/20220618/3d40f0e4e3e547bda62a444e484caa84.png
[SouthEast 7]: /images/20220618/6d34c04874b047a09bfc7cd329557ba8.png
[SouthEast 8]: /images/20220618/1b482d530d9a44d29baae460635a2dce.png
[SouthEast 9]: /images/20220618/d5f6d06d9f624da986874f4990a915c2.png
[SouthEast 10]: /images/20220618/fda86fcda42a4938ae0e3bbbc0433b7a.png
[SouthEast 11]: /images/20220618/bfeec654428b4b20b6466443a6c396dc.png
[Boyer-Moore 1]: http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html