8

我一直试图理解Boyer–Moore 字符串搜索算法中的移位规则，但还没有理解它们。我在维基百科上读到这里，但这太复杂了！

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

4

3 回答 3

16

在 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在这里更深入地解释了它，以及许多其他字符串搜索算法。

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

SSIMPLE EXAMPLE
EXAMPLE
  ^

匹配的后缀是MPLE，不匹配的文本字符是I。因此，坏字符移位会I在模式的初始部分查找最后一次出现的 。没有，因此错误的字符移位会改变模式，因此不匹配I的位置在模式开始之前

SSIMPLE EXAMPLE
   EXAMPLE

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

SSIMPLE EXAMPLE
      EXAMPLE

好的后缀移位将模式向右移动，所以这是选择的移位。

然后在最后一个模式位置立即出现不匹配，然后坏字符移位将P文本P中的 与模式中的对齐（如果不匹配发生在最后一个模式字符，则根本不需要考虑好的后缀移位，因为在这种情况下，它永远不会产生比坏字符偏移更大的偏移）。

然后我们就有了完整的比赛。

在带有模式的变体中TXAMPLE，good后缀移位发现没有匹配部分的非空后缀是模式的前缀（并且没有出现完全匹配的部分在前面没有A的模式中），所以good后缀移位将文本匹配部分的空后缀（theE和空格之间的边界）与模式的空前缀（the 之前的空字符串T）对齐，从而导致

SSIMPLE EXAMPLE
       TXAMPLE

（然后在下一步中，坏字符移位将两个Ls 对齐，之后该步骤中的下一个不匹配发生在T模式的初始位置）。

于 2012-11-01T12:09:54.817 回答
7

这里有一个很好的可视化。

（编辑：这两个示例和如何在此处实现预处理步骤的示例也有很好的解释。）

一般规则：

  • 我们正在寻找如何将模式与文本对齐，以便对齐的部分匹配。如果不存在这样的对齐方式，则在文本中找不到该模式。
  • 从右到左检查每个对齐方式——也就是说，首先检查模式的最后一个字符是否与其当前对齐方式匹配。
  • 当你碰到一个不对齐的字符时，增加偏移量（移动模式），以便模式中最后一次出现的文本侧字母与我们当前正在查看的文本侧字母的出现对齐. 这需要预先构建（或每次搜索，但效率较低）每个字母在模式中的位置的索引。
  • 如果文本中考虑的字符没有出现在模式中，则向前跳过模式的全长。
  • 如果图案的结尾超出文本的结尾（偏移量 + 长度（图案）> 长度（文本）），则图案不会出现在文本中。

我刚才描述的是“坏性格”规则。“好后缀”规则为移位提供了另一种选择；无论哪个更远，你应该采取的那个。完全有可能在没有好的后缀规则的情况下实现该算法，但是一旦建立了索引，它的效率就会降低。

good-suffix 规则要求您还知道在哪里可以找到模式的每个多字符子字符串。当您遇到不匹配时（检查，一如既往，从右到左），好的后缀移位将模式移动到已经匹配的字母将再次匹配的位置。或者，如果匹配的部分在模式中是唯一的，您知道您可以一直跳过它，因为如果它在与唯一匹配项对齐时不匹配，则在与任何匹配项对齐时可能无法匹配图案的其他部分。

例如，让我们考虑以下情况：

  • 我的模式以“一条狗”结尾。
  • 我目前将它与以“s dog”结尾的部分文本对齐。
  • 因此，坏字母是“s”（它们停止匹配的地方），好后缀是“狗”（匹配的部分）。

我在这里有两个选择：

  1. 移动以使模式中的第一个“s”（从右到左）与文本中的“s”对齐。如果模式中没有“s”，则将模式的开头移到刚刚过去的“s”。
  2. Shift 使下一个“dog”与文本中的“dog”对齐。如果模式中没有另一个“狗”，则将模式的开头移到“狗”的结尾。

我应该选择让我移动更远的那个。

如果您仍然感到困惑，请尝试提出更具体的问题；当我们不知道你被困在哪里时，很难说清楚。

于 2012-11-01T12:08:49.177 回答
1

有两种启发式：蝙蝠符号启发式和良好模式启发式。

首先，你知道，针比较从它的末端开始。因此，如果字符不匹配针移位，那么至少在 haystack 中比较的字符将匹配针。例如。needle 是“ABRACADABRA”，而 haystack 中的当前字符是“B”，它不匹配最后一个“A”，也不匹配前面的“R”，因此移位一个是没有意义的，不会匹配。但是“B”匹配针中末尾字符的第 2 个字符。因此，我们将针至少移动 2 个位置。如果 haystack 中的当前字符与 needle 中的任何字符都不匹配，则必须将 needle 移到当前字符之外。换句话说，我们移动模式直到 haystack 中的当前字符匹配针中的字符，或者整个针被移动。

计算移位量并将其存储在数组中，因此对于“ABRACADABRA”，它将是：['R'] = 1、['B'] = 2、['D'] = 4 等。

haystack: XYABRACADABRA...
                    |
needle:   ABRACADABRA
           ABRACADABRA <-- pointless shift: R will not match B
            ABRACADABRA

其次，如果在 haystack 中找到至少“ABRA”的匹配项（但没有完全匹配），可以移动针，以便下一个“ABRA”将匹配。

匹配部分的偏移量也已预先计算：例如 ['A'] = 3, ['RA'] = 11, ['BRA'] = 11, ['ABRA'] = 7, ['DABRA'] = 7 ...

haystack: XYZYXADABRACADABRA...
needle:   ABRACADABRA           (shift to ABRA from matched ADABRA)
          ~~~~   ~~~~
                 ABRACADABRA

这不是对所有极端情况的完整解释，而是算法的主要思想。

于 2012-11-01T12:17:13.240 回答