Knuth-Morris-Pratt算法和Boyer-Moore算法的主要区别是什么？

Question

Knuth-Morris-Pratt（KMP）搜索算法和Boyer-Moore（BM）搜索算法有哪些主要区别？

我知道KMP在X中搜索Y，试图在Y中定义一个模式，并将该模式保存在向量中。我也知道BM对于像DNA（ACTG）这样的小词更有效。

它们的工作方式有什么主要区别？哪一个更快？哪一个占用计算机资源较少？在哪些情况下使用哪个更好？

- ghaschel

---

BM在处理“自然文本”方面比小数据集表现更好。 - gtgaxiola

Answer 1

简单来说，Boyer-Moore算法是从模式串的末尾开始匹配，通过假设如果在末尾没有匹配，则不需要在开头进行匹配。因此，这种算法可实现“大跨步”，因此适用于搜索类似于“自然文本”（例如英语）的文本。

Knuth-Morris-Pratt算法通过观察当出现不匹配时，可以利用“单词”W本身所包含的足够信息来确定下一个匹配位置，从而避免重新检查先前已匹配的字符。 (来源: 维基百科)

这意味着KMP算法更适用于小集合，例如DNA（ACTG）。

- gtgaxiola

---

我不明白为什么先匹配最后的字符会有所改进。如果匹配失败，你仍然需要向前移动一个字符，对吧？ - Thomas Ahle

@ThomasAhle 这是一个例子：单词：吉他 文本：我喜欢吉他。然后，您将尝试匹配吉他（第6个字符）与文本的第6个字符的“e”...由于它们不匹配...无需检查“I love”因为它们永远不会匹配...所以您可以跳过所有这些部分... - gtgaxiola

@ThomasAhle 可能这会有所帮助：http://www.utdallas.edu/~besp/demo/John2010/boyer-moore.htm 请尝试我的示例案例：文本：“我喜欢吉他” 模式：“吉他” - gtgaxiola

BM算法背后的思想很好，这个例子很棒。但是，实现有些问题。请用“HERE IS A SIMPIEXAMPLE”和“EXAMPLE”作为输入进行测试。尽管搜索字符串出现在搜索文本中，但结果却没有匹配成功。 - Olaf Dietsche

@gtgaxiola 不，Boyer-Moore算法不会像那样跳过。您需要移动对齐位置，以便在“吉他”中找到最接近左侧的'e'或'r'，并将该模式中的'e'与文本中导致不匹配的'e'对准（由于“吉他”中没有'e'，因此您要一直跳到下一个'e'字符）。观看这个惊人的视频。 - Escape0707

Answer 2

Moore的德克萨斯大学网页详细介绍了Knuth-Morris-Pratt和Boyer-Moore算法（他还提供了各种技术来源）：

• Knuth-Morris-Pratt
• Boyer-Moore

根据Moore自己的说法，

经典的Boyer-Moore算法在小字母表（如DNA）上的效率不高。由于子字符串经常重新出现，跳过的距离往往随着模式长度停止增长。通过记住已匹配的更多内容，可以在文本中获得更大的跳过。甚至可以安排“完美的记忆”，从而最多只查看每个字符一次，而Boyer-Moore算法虽然是线性的，但可能会多次检查来自文本的字符。其他人已经在文献中探讨过更多记忆的想法。它需要非常大的表或状态机。

然而，已经有一些修改的BM算法使小字母表搜索成为可能。

- David Titarenco

Answer 3

Boyer-Moore技术从右到左匹配字符，适用于长模式。Knuth Morris Pratt技术从左到右匹配字符，适用于短模式，并且速度较快。

- Sadaf Khursheed