algorithm - Boyer-Moore字符串搜索算法的移位规则是什么？

Question

我一直在尝试了解Boyer-Moore字符串搜索算法中的移位规则，但还不了解它们。我在wikipedia上阅读过，但这太复杂了!

如果有人以简单的方式列出规则，那将有很大的帮助。

Answer 1

在Boyer-Moore算法中，您将从样式末尾开始将样式字符与文本字符进行比较。如果发现不匹配，则具有以下类型的配置

....xyzabc....      <-text
  ....uabc          <- pattern
      ^
    mismatch

现在，不良字符转移意味着转移模式，以使不匹配的文本字符与该字符在模式的初始部分中的最后一次出现(模式减去最后一个模式字符)对齐(如果发生了这种情况)，或者如果不匹配的字符根本没有出现在图案的开始部分，则在图案之前一个位置。

如果情况是这样，那可能是向左移动

     v
...xyzazc...
 ....uazc
 ..uazc

因此，仅此一项并不能保证取得进展。

另一种移位是良好的后缀移位，它将文本的匹配部分 m与该字符序列在模式中最右边出现的方式相匹配，该模式以不同的字符开头(如果匹配的后缀也是的前缀，则不包括在内)模式)，而不是模式的匹配后缀 m-如果出现这种情况。

所以举个例子

           v
....abcdabceabcfabc...
    ...xabcfabcfabc
        ...xabcfabcfabc

由于匹配的部分 m = abcfabc出现在其后缀出现位置左后四个位置的模式中，并且前面的字符与后缀位置中的字符不同( x而不是 f)，因此会导致四个位置的后缀移位良好。

如果在模式中没有完全出现匹配的部分，其后跟一个不同于后缀的字符，则良好的后缀移位会将文本的匹配部分的后缀与模式的前缀对齐，选择最大的重叠度，例如

      v
...robocab....
    abacab
        abacab

良好的后缀移位总是将模式向右移位，因此可以保证进度。

然后，在每次不匹配时，比较不良字符转移和良好后缀转移的进展，并选择更大的转移。 Christian Charras和Thierry Lecroq here以及许多其他字符串搜索算法对它进行了更深入的解释。

对于您在评论中提到的示例，

SSIMPLE EXAMPLE
EXAMPLE
  ^

匹配的后缀为 MPLE，而不匹配的文本字符为 I。因此，不良字符转移会在模式的初始部分中寻找 I的最后一次出现。没有，因此不良的字符移位会改变模式，从而使不匹配的 I在模式开始之前为1

SSIMPLE EXAMPLE
   EXAMPLE

并且后缀移位好会寻找模式中最右端出现的 MPLE，而不是 A之前的前缀，或者最长的后缀 MPLE作为模式的前缀。在后缀之前，模式中没有完全出现匹配部分，因此，匹配部分的最长后缀(也是模式的前缀)决定了良好的后缀移位。在这种情况下，匹配部分的两个后缀(作为模式的前缀)是单字符字符串 E和空字符串。最长的显然是非空字符串，因此良好的后缀移位将文本的匹配部分中的一个字符后缀 E与该模式的一个字符前缀对齐

SSIMPLE EXAMPLE
      EXAMPLE

良好的后缀移位将模式向右移，这就是所选的移位。

然后在最后一个模式位置立即存在不匹配，然后错误的字符移位将文本中的 P与该模式中的 P对齐(并且如果在最后一个模式中发生不匹配，则根本不需要考虑好的后缀移位字符，因为在那种情况下，它永远不会产生比坏字符移位更大的移位)。

然后，我们有完整的比赛。

在带有 TXAMPLE模式的变体中，良好的后缀移位发现匹配部分的非空后缀不是该模式的前缀(并且在不以 A开头的模式中不存在完全匹配的部分)，因此良好的后缀移位将文本的匹配部分的空后缀( E和空格之间的边界)与模式的空前缀( T之前的空字符串)对齐，从而导致

SSIMPLE EXAMPLE
       TXAMPLE

(然后在下一步中，不良字符移位将两个 L对齐，并且此后步骤中的下一个不匹配发生在模式的初始 T处)。