Knuth-Morris-Pratt搜索算法和Boyer-Moore搜索算法之间的主要区别是什么？
我知道KMP在 X 中搜索 Y，试图在 Y 中定义一个模式，并将该模式保存在一个向量中。我也知道BM更适合小词，比如 DNA (ACTG)。
它们在工作方式上的主要区别是什么？哪个更快？哪一个对计算机不那么贪婪？在哪些情况下？
问问题
27724 次
3 回答
42
粗略的解释
Boyer-Moore 的方法是尝试匹配模式的最后一个字符而不是第一个字符，并假设如果末尾不匹配，则无需尝试在开头匹配。这允许“大跳跃”，因此当您搜索的模式和文本类似于“自然文本”（即英语）时，BM效果更好
Knuth-Morris-Pratt通过以下观察在主要“文本字符串”S 中搜索“单词”W 的出现：当发生不匹配时，单词本身包含足够的信息来确定下一个匹配的开始位置，从而绕过 re - 检查以前匹配的字符。（来源：维基）
这意味着KMP更适合 DNA (ACTG) 等小型集
于 2012-09-29T20:27:51.093 回答
39
Moore 的 UTexas 网页逐步介绍了这两种算法（他还提供了各种技术资源）：
据该男子本人介绍，
经典的 Boyer-Moore 算法存在这样一个现象，即它在处理 DNA 等小字母时往往效率不高。跳跃距离趋于随着模式长度停止增长，因为子串频繁地重新出现。通过记住更多已经匹配的内容，可以在文本中获得更大的跳过。人们甚至可以安排“完美记忆”，从而最多查看每个字符一次，而 Boyer-Moore 算法虽然是线性的，但可能会多次检查文本中的字符。其他人在文献中探索了这种记住更多的想法。它需要非常大的表或状态机。
然而，对 BM进行了一些修改，使得小字母搜索变得可行。
于 2012-09-29T20:30:39.020 回答
3
Boyer-Moore 技术从右到左匹配字符，适用于长模式。knuth moris pratt 从左到右匹配字符，在短模式上快速工作。
于 2014-01-14T09:05:47.680 回答