Rabin-Karp算法何时比KMP或Boyer-Moore算法更有效？

Question

Rabin-Karp算法何时比KMP或Boyer-Moore算法更有效？

string-searchknuth-morris-prattrabin-karpboyer-moore

15

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

那么，在什么情况下使用Rabin-Karp比其他算法更好呢？

- E.K

3个回答

4

Rabin-Karp 算法适用于查找多个模式匹配的大型文本，例如检测抄袭。

Boyer-Moore 算法适用于模式相对较大、字母表中等大小且词汇量较大的情况。但是它在处理二进制字符串或非常短的模式时效果不佳。

与此同时，KMP 算法适用于搜索较小的字母表，例如在生物信息学或二进制字符串中搜索。但如果字母表增加，它的执行速度将变慢。

- NIMISHAN

为什么如果字母表增加，KMP算法就不能快速运行？我从未见过这个引理的解释。 - zyc

2

KMP算法可以仅在O(n)的时间内遍历每个字符，Boyer-Moore算法则可以跳过一些字符序列，实现次线性运行时间。跳过字符序列的能力依赖于模式末尾处的不匹配位置，这在字母表较大时更有可能出现。 - CoronA

1

所有三种算法的时间复杂度（供参考）

m：模式的长度

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

k：字母表的大小

拉宾-卡普算法：

O(1) 辅助空间

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

Boyer-Moore算法：

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

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

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

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

Knuth Morris Pratt算法：

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

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

有关每个算法的更多详细信息，请在维基百科中查找。

- Rahul Saini

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

这些算法中有一些属性，在不同的情况下可能会使它们更具吸引力或不可取。以下是一个快速概述:

占用空间方面，Rabin-Karp更优

Rabin-Karp的一个主要优点是它使用O（1）辅助存储空间，这非常适合查找非常大的模式字符串。例如，如果您要在长度为10⁹的长字符串中查找长度为10⁷的字符串的所有出现，则不需要为故障函数或移位表分配10⁷个机器字的表格就是一个主要的优势。Boyer-Moore和KMP在长度为n的模式字符串上都使用Ω（n）内存，因此在这里，Rabin-Karp将获胜。

最坏情况单匹配效率方面，Boyer-Moore或KMP更好

Rabin-Karp存在两种潜在的最坏情况。首先，如果Rabin-Karp使用的特定质数已知于恶意攻击者，则该攻击者可能会创建一个输入，导致滚动哈希在每个时间点上匹配模式字符串的哈希值，从而导致算法的性能降至Ω((m - n + 1)n)，其中m是字符串长度，n是模式长度。如果您正在接受不受信任的字符串作为输入，则可能存在潜在问题。Boyer-Moore和KMP都没有这些弱点。

最坏情况多匹配效率方面，KMP更好

同样地，当你想在文本中查找出现大量次数的某个模式字符串时，Rabin-Karp算法速度较慢。例如，如果你想要在包含10⁹个字母a的文本字符串中用Rabin-Karp算法查找一个由10⁵个字母a组成的字符串，那么模式字符串会出现许多次，每次都需要进行线性扫描。这也可能导致Ω((m + n - 1)n)的运行时间。

许多Boyer-Moore实现在第二个规则上表现不佳，但在第一种情况下不会有糟糕的运行时间。而KMP没有这样的病态最坏情况。

最佳情况下，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是模式字符串的总长度。请注意，这里没有依赖于要搜索的不同模式字符串的数量！