前端之家

  1. 首页
  2. 问答

更好地理解和比较 Boyer-Moore 和 KMP 算法

• 问答

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

问题：

  1. 此 question 的最佳答案指出，如果字母表较小，则 KMP 效果很好。为什么会出现这种情况，为什么在这种情况下 Boyer 的算法不能比 KMP 表现得更好？
  2. KMP 和 Boyer 算法性能最差的示例分别是什么？ 我已经发现，对于像这个 Boyer 这样的例子，性能最差。是吗？

text='AAAAA....13 A'S'

pattern='AAA'

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

给定 document 中第 2 页的 4th Paragraph 谈到我们可以跳过文本的某些字符而不看它们。为什么我们可以忽略它们？

  1. 在外行的语言中，我们可以声称 KMP 和 Boyer 算法之间的区别在于 KMP 通过跳过已经匹配的字符来工作，而 Boyer 通过跳过不会产生任何区别的字符来工作，因为文本上窗口的当前位置已经有错过比赛。
xiazai1999 回答：更好地理解和比较 Boyer-Moore 和 KMP 算法

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

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

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

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

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

如果你坚持举例：

KMP 比 Boyer-Moore 更好的例子：

电话：AAAAAA.....

P：AAA

Boyer-Moore 比 KMP 更好的示例：

T:ABCDABCDABCD.....

P:ABCF

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

坏字符规则消除了所有字符不匹配的情况，甚至在实例中它跳到它做的地方/跳过它。

好的后缀规则可以消除所有情况，如果你已经找到的后缀不适合你的模式，如果你滑动你的模式，（更像是你滑动它存在的第一次出现......实际上真的很相似到 KMP，但带有后缀而不是前缀）。

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

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

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

algorithmboyer-mooreknuth-morris-prattstring-matching
本文链接：https://www.f2er.com/1088.html

大家都在问