Boyer-Moore字符串搜索算法的转换规则是什么？

Question

我一直试图理解Boyer-Moore字符串搜索算法中的移位规则,但还没有理解它们.我在这里阅读维基百科,但这太复杂了!

如果有人以简单的方式列出规则,那将是非常有帮助的.

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 在此更深入地解释了这一点,以及许多其他字符串搜索算法.

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

SSIMPLE EXAMPLE
EXAMPLE
  ^

匹配的后缀是MPLE,不匹配的文本字符是I.因此,错误的字符移位会查找I模式初始部分的最后一次出现.没有,所以不良的字符移位会改变模式,使得I在模式开始之前不匹配是一个

SSIMPLE EXAMPLE
   EXAMPLE

和良好的后缀移位查找最右边出现MPLE在图案不通过之前A,或的最长后缀MPLE即图案的前缀.在后缀之前的模式中没有完全出现匹配的部分,因此匹配部分的最长后缀(也是模式的前缀)决定了良好的后缀移位.在这种情况下,作为模式前缀的匹配部分的两个后缀是单字符串E和空字符串.最长的显然是非空字符串,因此良好的后缀移位将E文本的匹配部分中的单字符后缀与模式的单字符前缀对齐

SSIMPLE EXAMPLE
      EXAMPLE

良好的后缀移动将模式向右移动,因此这是所选择的移位.

然后在最后一个模式位置立即出现不匹配,然后坏的字符移位P使文本与P模式中的对齐(如果在最后一个模式字符处发生不匹配,则根本不需要考虑好的后缀移位,因为在那种情况下,它永远不会产生比不良角色转换更大的转变.

然后我们完全匹配.

与图案的变体TXAMPLE,良好的后缀移发现匹配的部分的不非空后缀是图案的前缀(并且不存在该图案中的完整的匹配部分的发生不通过之前A),所以良好后缀shift将文本匹配部分的空后缀(E空间和空间之间的边界)与模式的空前缀(前面的空字符串T)对齐,从而产生

SSIMPLE EXAMPLE
       TXAMPLE

(然后在下一步中,坏的字符移位使两个Ls 对齐,并且此后的步骤中的下一个不匹配发生在T模式的初始处).

Answer 2

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

(编辑:对于这两个示例以及如何在此处实现预处理步骤的示例,还有一个非常好的解释.)

通用规则:

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

我刚刚描述的是"坏人物"规则."良好后缀"规则提供了另一种转移选择; 你应该采取的更远的转移.完全有可能在没有良好后缀规则的情况下实现算法,但是一旦构建了索引,效率就会降低.

良好后缀规则要求您还知道在何处查找模式的每个多字符子字符串.当你打一个不匹配(检查一如既往,从右到左),良好的后缀移移动模式到一个地步,那封情书都已经比赛将再次这样做.或者,如果匹配的部分在模式中是唯一的,您知道可以跳过它的所有方式,因为如果它与单独的事件对齐时不匹配,则在排列任何一个时都不可能匹配模式的其他部分.

例如,让我们考虑以下情况:

• 我的模式以"狗"结尾.
• 我目前将它与以"s dog"结尾的部分文本对齐.
• 因此,坏字母是's'(它们停止匹配),好的后缀是"dog"(匹配的部分).

我有两个选择:

1. 移动,使模式中的第一个's'(从右到左)与文本中的's'对齐.如果模式中没有's',则将模式的开头移到刚过's'.
2. 移动,以便下一个"狗"与文本中的"狗"对齐.如果模式中没有另一个"狗",则将模式的开头移到"狗"的末尾.

我应该拿任何一个让我转移得更远的人.

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