Boyer-Moore字符串搜索算法

在计算机科学里，Boyer-Moore字符串搜索算法是一种非常高效的字符串搜索算法。它由Bob Boyer和J Strother Moore设计于1977年。此算法仅对搜索目标字符串（关键字）进行预处理，而非被搜索的字符串。虽然Boyer-Moore算法的执行时间同样线性依赖于被搜索字符串的大小，但是通常仅为其它算法的一小部分：它不需要对被搜索的字符串中的字符进行逐一比较，而会跳过其中某些部分。通常搜索关键字越长，算法速度越快。它的效率来自于这样的事实：对于每一次失败的匹配尝试，算法都能够使用这些信息来排除尽可能多的无法匹配的位置。

定义
  • S[i]为字符串S从1开始排列的第i个字符
  • S[i..j]为字符串S的一个子串，始于i，终于j。
  • S的前缀定义为S[1..i],1<i<n，n为字符串S的长度。
  • S的后缀定义为S[i..n],1<i<=n，小于字符串S的长度。
  • 检索的字符串称为pattern，用符号P表示。
  • 被检索字符称为text，用符号T表示。
  • P的长度为n
  • T的长度为m
  • k表示P的最后一个字符在T中的位置。
  • 当匹配发生时，P在T中的位置为T[(k-n+1)..k]。

原理

不同于朴素模式（brute-force search）的逐个字符对比，Boyer-Moore充分使用预处理P的信息来尽可能跳过更多的字符。通常，我们比较一个字符串都是从首字母开始，逐个比较下去。一旦发现有不同的字符，就需要从头开始进行下一次比较。这样，就需要将字串中的所有字符一一比较。Boyer-Moore算法的关键在于，当P的最后一个字符被比较完成后，我们可以决定跳过一个或更多个字符。如果最后一个字符不匹配，那么就没必要继续比较前一个字符。如果最后一个字符未在P中出现，那么我们可以直接跳过T的n个字符，比较接下来的n个字符，n为P的长度（见定义）。如果最后一个字符出现在P中，那么跳过的字符数需要进行计算（也就是将P整体往后移），然后继续前面的步骤来比较。通过这种字符的移动方式来代替逐个比较是这个算法如此高效的关键所在。

形式化的表述方式为，从k=n开始，也就是P从T的最开始进行比较。紧接着，P的第n个字符和T的第k个字符开始：字符串依次从P的最后一个字符到最开始的字符。结束条件是当比较到达P的最开始（此时匹配完成），或按照规则移动后的字符部匹配发生时。然后，在新的对齐位置重新开始比较，如此反复，直到到达T的结尾。

移动规则是一张间恒定的查找表，通过对P的预处理产生的。

移动规则

移动字符数是通过两条规则决定的：坏字符规则和好后缀规则。实际移动为通过这两条规则计算出的最大移动个数。

原理
----X--K---
ANPANMANAM-
-NNAAMAN---
---NNAAMAN-
Demonstration of bad character rule with pattern NNAAMAN.

当T中有字符不匹配时，如果T中的这个不匹配的字符出现在对应P中当前位置的左侧，那么P移动位置将这两个在字符对齐。如果T中这个不匹配字符不在P中当前位置的左侧，那么将当前位置左侧的所有字符均移到该不匹配字符后。右侧的例子中，X位置发生了不匹配，我们检查P中的不匹配字符N（对应T中字符A）在P当前位置（X）的左侧存在，因此，将最靠近该不匹配字符位置的N与P中的X位置的N对齐，也就是向右移动两位。

处理

当我们发现不匹配字符时，假设这个字符在T中为c，位置在T的i。字符c在P中出现的最靠近i位置，假设为j，j<i或j=-1（如果P不存在字符c）。那么移动位数为i - j，复杂度是O(1)。i，j的起点为P在T中位置的开始T[(k-n+1)..k]的(k-n+1)。 大多网站都只建立一个一维坏字符数组来保存，但事实这只能保存最靠左或最靠右的字符c，明显与英文的wikipedia里面要求一个二维数组来保存信息的不一样。

原理

好后缀规则要更复杂一点。

假设有P和T，T中字串t匹配到了P的一个后缀，但在比较位置i时发生不匹配。设匹配到的好后缀在T中为t，在P中为t'（t = t'）。

分两种情况来讨论：

1，在P中i位置的左侧最靠近i位置查找字串t'使得t'=t（此时t'不是P的后缀，实际上也就是查找匹配到的字串除了在P的后缀中存在，是否在P的其他位置存在），若存在，则移动相应的位数将找到的t'与T中的t对齐。

2，如果t'不存在，那我们继续查找t的某一个后缀是否为P的前缀，若存在，则移动相应的位将P的前缀与t的后缀位置对齐。否则，将P向后移动n个字符。

好后缀规则的实质是，将不匹配位置右侧匹配到的字符串t的所有字符后缀组合，用于查找它们在P的不匹配位置左侧是否存在。

通俗的理解是，最长的好后缀t是否存在于i的左侧（情况1），其他后缀组合中是否存在与P的前缀相同的情况（情况2）。

举例

假设被检索文字列是“1234567890”，檢索文字列是“MOORE”。简单的比较需要执行十次才得到结论不匹配。被检索文字列：1234567890

  第一次比较：M....         （M和1比较，不匹配）
  第二次比较： M....        （M和2比较，不匹配）
  第三次比较：  M....       （M和3比较，不匹配）
        ...
  第十次比较：         M....（M和0比较，不匹配）

※未参与比较的文字用【.】占位。

BM算法只需要2次比较。

被检索文字列：1234567890

  第一次比较：....E        （E和5比较，不匹配，并且5不是MOORE中任何文字）
  第二次比较：     ....E   （E和0比较，不匹配，并且0不是MOORE中任何文字）

第一次从检索文字的末尾开始，因为如果被检索文字的第5文字位置不是E，则无论前4个文字是什麽，都绝不可能匹配了。这一点比较容易理解。

而之所以不用E和6比较，则是因在E和5进行比较的时候不仅知道他们不相等，而且还知道了5不和检索文字MOORE中的任何一个文字相等，这使得下面这些比较都可以省略掉。

被检索文字列：....5......

不需要的比较： ...R.       （E和5比较时也同时发现5不等于R，于是这个比较是不必要的）
不需要的比较：  ..O..      （E和5比较时也同时发现5不等于O，于是这个比较是不必要的）
不需要的比较：   .O...     （E和5比较时也同时发现5不等于O，于是这个比较是不必要的）
不需要的比较：    M....    （E和5比较时也同时发现5不等于M，于是这个比较是不必要的）

另见

参考资料

    外部链接
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.