string-search - Rabin Karp 什么时候比 KMP 或 Boyer-Moore 更有效？

Question

我正在学习字符串搜索算法并了解它们的工作原理，但还没有找到足够好的答案来说明在哪些情况下 Rabin-Karp 算法会比 KMP 或 Boyer-Moore 更有效。我看到它更容易实现并且不需要相同的开销，但除此之外，我不知道。

那么，Rabin-Karp 什么时候比其他方法更好用呢？

Answer 1

这些算法中的每一个都具有一些属性，这些属性可能使它们在不同的情况下是可取的或不可取的。这是一个快速的纲要：

空间利用有利于拉宾-卡普

Rabin-Karp 的一个主要优点是它使用 O(1) 辅助存储空间，如果您要查找的模式字符串非常大，这非常有用。例如，如果您要在长度为 10 ⁹的较长字符串中查找长度为 10 ⁷的字符串的所有出现，则不必为故障函数或移位表分配 10 ^{7 个}机器字的表是一个重大胜利。Boyer-Moore 和 KMP 都在长度为 n 的模式字符串上使用 Ω(n) 内存，因此 Rabin-Karp 在这里将是一个明显的胜利。

最坏情况的单场比赛效率有利于 Boyer-Moore 或 KMP

Rabin-Karp 有两个潜在的最坏情况。首先，如果恶意对手知道 Rabin-Karp 使用的特定素数，那么该对手可能会制作一个输入，使滚动散列在每个时间点与模式字符串的散列相匹配，从而导致算法的性能下降。在长度为 m 的字符串和长度为 n 的模式上降级为 Ω((m - n + 1)n)。如果您将不受信任的字符串作为输入，这可能是一个问题。Boyer-Moore 和 KMP 都没有这些弱点。

最坏情况多重匹配效率有利于 KMP。

类似地，Rabin-Karp 在要查找模式字符串的所有匹配项的情况下会很慢，而该模式会出现很多次。例如，如果您正在使用 Rabin-Karp 查找由 10 ⁹个字母的副本组成的文本字符串中的 10 ⁵个字母的字符串，那么模式字符串出现的位置会有很多，每个位置都会出现需要线性扫描。这也可能导致 Ω((m + n - 1)n) 的运行时间。aa

许多 Boyer-Moore 实现都受到第二条规则的影响，但在第一种情况下不会有糟糕的运行时。KMP 没有像这样的病态最坏情况。

最佳案例表现有利于 Boyer-Moore

Boyer-Moore 算法的一个优点是它不必扫描输入字符串的所有字符。具体来说，坏字符规则可用于在不匹配的情况下跳过输入字符串的大块区域。更具体地说，Boyer-Moore 的最佳运行时间是 O(m / n)，这比 Rabin-Karp 或 KMP 所能提供的要快得多。

多字符串的泛化支持 KMP

假设您有一组固定的要搜索的多个文本字符串，而不仅仅是一个。如果您愿意，您可以在字符串上运行多次 Rabin-Karp、KMP 或 Boyer-Moore 以查找所有匹配项。但是，这种方法的运行时间不是很好，因为它与要搜索的字符串的数量呈线性关系。另一方面，KMP 很好地推广到 Aho-Corasick 字符串匹配算法，该算法在 O(m + n + z) 时间内运行，其中 z 是找到的匹配数，n 是模式字符串的组合长度。请注意，这里不依赖于正在搜索的不同模式字符串的数量！

Answer 2

Rabin-Karp算法在搜索查找多个模式匹配的大文本时更好，例如检测抄袭。

当模式相对较大且字母大小适中且词汇量较大时，Boyer-Moore效果更好。它不适用于二进制字符串或非常短的模式。

同时，KMP非常适合在较小的字母表中进行搜索，例如在生物信息学中或在二进制字符串中进行搜索。如果字母表增加，它不会运行得很快。

Answer 3

所有三个的时空复杂性（供参考）（用于查找模式的所有出现）

m : 模式的长度

n ：我们在其中搜索模式的字符串的长度

k : 字母的大小

拉宾·卡普：

O(1) 辅助空间

使用散列来查找文本中模式字符串的完全匹配。它使用滚动散列快速过滤掉与模式不匹配的文本位置，然后检查剩余位置是否匹配

博耶摩尔：

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

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

最坏情况空间复杂度：Θ(k)。

可用于类似“grep”的搜索。 https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm#Performance

克努斯·莫里斯·普拉特：

最坏情况性能：Θ(m) 预处理 + Θ(n) 匹配

最坏情况空间复杂度：Θ(m)

有关每种算法的更多详细信息，请在 Wikipedia 中查找。