0

我最近一直在了解不同的字符串搜索算法，例如Knuth-Morris-Pratt和Boyer Moore 算法，并且在这样做的过程中，我了解了一些关于它们的一些细节，我无法消化这些细节，或者对这些算法有了自己的理解，但是仍然不确定它们的正确性。

问题：

  1. 这个问题的最佳答案表明，如果字母表很小，KMP 效果很好。为什么会出现这种情况，为什么 Boyer 的算法在这种情况下不能比 KMP 表现得更好？
  2. KMP 和 Boyer 算法性能最差的每个例子是什么？我已经发现，对于像这样的例子 Boyer 会给出最差的性能。那正确吗？

文本=' AAAA....13 A'S '

模式='AAA'

3.我能够理解 KMP 的正确前缀方面，并且能够消化这样一个事实，即它在跳过文本的已经匹配部分时不会跳过可能的匹配项，但即使我确实得到了Bad Character Heuristic背后的直觉 和Good Suffix Heuristic of Boyer 算法，它专注于跳过字符，以便模式与未来可能的匹配一致，我仍然无法让自己理解这两种启发式如何保证跳过的字符无论如何都不会匹配。

给定文档第 2 页的第 4 段也谈到了相同的内容，即我们可以跳过文本的某些字符而不看它们。为什么我们可以忽略它们？

  1. 用 Layman 的语言，我们可以声称 KMP 和 Boyer 算法之间的区别在于 KMP 通过跳过已经匹配的字符来工作，而 Boyer 通过跳过不会产生任何区别的字符来工作，因为文本上窗口的当前位置已经有一个未匹配项.
4

1 回答 1

0

首先，您应该区分原始的 Boyer-Moore 和具有 Galil 规则实现的那个，因为它们在最坏的情况下具有不同类型的复杂性。让我们看看不同情况下的原始 Boyer-Moore 算法：

最坏情况下的性能 Θ(m) 预处理 + O(mn) 匹配。

最佳情况下的性能 Θ(m) 预处理 + Ω(n/m)。

您可以看到原始匹配中最差的演员阵容甚至不是线性的，这比 KMP (O(m+n)) 复杂度差得多。但另一方面，在最好的情况下，它可能会进入亚线性时间。这种情况可能取决于坏字符规则，如下所示：

假设您有 n 长模式，但在模式的末尾它有一个字符在 T 中根本不出现（或几乎不出现）。如果那样的话，你甚至不需要遍历整个 T 的大小，你可以在每次错过比赛时跳跃。这就是为什么对于更大的字母表更好的解决方案，因为您有更高的机会找到这些字符并进行这些跳跃。

如果你坚持举例：

KMP 比 Boyer-Moore 更好的示例：

T：啊啊啊啊……

P: AAA

Boyer-Moore 比 KMP 更好的例子：

T：ABCDABCDABCD.....

P:ABCF

关于您的第三个问题，您应该了解 Boyer-Moore 中的每条规则足以找到 T 中的所有重复，因为每条规则的作用是消除无法找到模式的情况：

坏字符规则消除了所有字符的情况，即使在实例中也没有，所以它会跳转到它所做的地方/越过它。

好的后缀规则消除所有情况，如果您滑动您的模式，您已经找到的后缀不适合您的模式，（更像是您滑动第一次出现的情况，如果它存在..实际上与 KMP 中的这个想法，但有后缀而不是前缀）。

你可以认为你会做检查所有 n*m 的幼稚解决方案，但是这两个规则都可以作为消除过程，所以你在这些规则之间取最大值并消除这些情况。

关于你的最后一个问题，我认为是的..这是 KMP 和 Boyer-Moore 想法的很好的概要

还要记住，使用 Galil 规则，在最坏情况和平均情况下，您可能在时间复杂度方面比 kmp 有更好的结果，但在空间复杂度方面却没有（也取决于实现）

于 2021-08-02T11:08:22.487 回答