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

Question

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

我知道KMP在X中搜索Y,尝试在Y中定义模式,并将模式保存在向量中.我也知道BM对于像DNA(ACTG)这样的小词更有效.

它们的工作方式有哪些主要区别？哪一个更快？哪一个不那么电脑贪心？在哪些情况下？

Answer 1

粗略解释

Boyer-Moore的方法是尝试匹配模式的最后一个字符而不是第一个字符,假设如果最后不匹配则不需要尝试在开头匹配.这允许"大跳跃"因此当您搜索的模式和文本类似于"自然文本"(即英语)时BM更好地工作

Knuth-Morris-Pratt通过观察当发生不匹配时,单词本身包含足够的信息来确定下一个匹配可以开始的位置,从而绕过re,从而在主"文本字符串"S中搜索"单词"W的出现. - 检查先前匹配的字符.(来源:维基)

这意味着KMP更适合像DNA这样的小型装置(ACTG)

Answer 2

Moore的UTexas网页以一步一步的方式介绍了这两种算法(他还提供了各种技术资源):

• 克努特莫里斯普拉特
• 博耶 - 穆尔

据该男子本人说,

经典的Boyer-Moore算法存在这样一种现象:它往往不能像DNA那样在小字母上如此有效地工作.跳过距离倾向于随着图案长度而停止增长,因为子串经常重新出现.通过记住已经匹配的更多内容,可以在文本中获得更大的跳过.人们甚至可以安排"完美的记忆",因此最多只查看一次每个字符,而Boyer-Moore算法虽然是线性的,但可以多次检查文本中的字符.其他人在文献中探讨了这种记忆更多的想法.它需要非常大的表或状态机.

然而,BM的一些修改使小字母搜索成为可能.

Answer 3

Boyer-Moore 技术从右到左匹配字符，适用于长图案。knuth moris pratt 从左到右匹配字符，在短模式上工作速度很快。