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

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 here以及许多其他字符串搜索算法对此进行了更深入的解释 .

  ---

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

  SSIMPLE EXAMPLE
  EXAMPLE
    ^
  

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

  SSIMPLE EXAMPLE
     EXAMPLE
  

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

  SSIMPLE EXAMPLE
        EXAMPLE
  

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

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

  然后我们完全匹配 .

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

  SSIMPLE EXAMPLE
         TXAMPLE
  

  （然后在下一步中，坏的角色转换使两者对齐 L s，此后步骤中的下一个不匹配发生在模式的初始 T 处 .

  回复于 2024-04-30T17:39:45+08:00
• 7

  有一个很好的可视化here.

  （编辑：对于这两个示例以及如何实现预处理步骤here的示例，也有非常好的解释 . ）

  通用规则：

  • 我们正在寻找如何将图案与文本对齐，以使对齐的部分匹配 . 如果不存在此类对齐，则在文本中找不到该模式 .

  • 从右到左检查每个对齐 - 也就是说，首先检查图案的最后一个字符是否与当前对齐方式匹配 .

  • 当你碰到一个没有对齐的字符时，增加偏移量（移动模式），使模式中文本边字母的最后一次出现与文本边字母的出现一致，我们的效率会低一些）模式中每个字母存在的索引 .

  • 如果文本中考虑的字符未出现在图案中，则向前跳过图案的整个长度 .

  • 如果图案的末尾超出文本末尾（偏移长度（图案）>长度（文本）），则图案不会出现在文本中 .

  我完全有可能在没有良好后缀规则的情况下实现算法，但是一旦构建了索引，效率就会降低 .

  良好后缀规则要求您还知道在何处查找模式的每个多字符子字符串 . 当您遇到不匹配（一如既往地从右到左检查）时，良好后缀移动将模式移动到已经匹配的字母将再次执行此操作的点 . 或者，如果匹配的部分在模式中是唯一的，则您知道可以跳过它的所有方式，因为如果它与模式的任何其他部分对齐时可能不匹配't match when lined up with the sole occurrence, it can' .

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

  • 我的模式以"a dog"结尾 .

  • 我目前已将其与文本中以"s dog"结尾的部分对齐 .

  • 因此，坏字母是's'（它们停止匹配），好的后缀是" dog"（匹配的部分） .

  我有两个选择：

  • 移位，使模式中的第一个's'（从右到左）与文本中的's'对齐 . 如果模式中没有's'，则将模式的开头移到's'之后 .

  • Shift，以便下一个" dog"与文本中的" dog"对齐 . 如果模式中没有其他" dog"，则将模式的开头移到" dog"的末尾 .

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

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

  回复于 2024-04-30T17:39:45+08:00
• 1

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

  首先，你知道，针头比较从它的结束开始 . 因此，如果字符不匹配针移位，那么至少比较干草堆中的字符会匹配针 . E. g . 针是“ABRACADABRA”，干草堆中的当前字符是“B”，它与最后的“A”不匹配，也与先前的“R”不匹配，所以一个一个是无意义的，没有匹配 . 但是“B”在针的最后一个字符中匹配2 . 所以我们至少要换针2个位置 . 如果haystack中的当前字符与针中的任何字符都不匹配，则必须将针移动到当前字符之外 . 换句话说，我们移动模式直到大海捞针中的当前角色与针中的角色匹配，或者整个针移动超出 .

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

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

  其次，如果在干草堆中发现至少匹配“ABRA”（但没有完全匹配），则可以移动针，以便下一个“ABRA”匹配 .

  匹配部分的移位量也是预先计算的：e . G . ['A'] = 3，['RA'] = 11，['BRA'] = 11，['ABRA'] = 7，['DABRA'] = 7 ......

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

  这不是所有角落情况的完整解释，而是算法的主要思想 .

  回复于 2024-04-30T17:39:45+08:00