什么是高德纳 - 莫里斯 - 普拉特和博耶 - 穆尔搜索算法之间的主要区别是什么？ [英] What are the main differences between the Knuth-Morris-Pratt and Boyer-Moore search algorithms?
问题描述
什么是克努特 - 莫里斯 - 普拉特搜索算法和博耶 - 穆尔搜索算法之间的主要区别是什么？
What are the main differences between the Knuth-Morris-Pratt search algorithm and the Boyer-Moore search algorithm?
我知道 KMP x中搜索Y，试图确定Y中的模式，并保存在向量模式。我也知道， BM 适用于小型的话，像DNA（ACTG）。
I know KMP searches for Y in X, trying to define a pattern in Y, and saves the pattern in a vector. I also know that BM works better for small words, like DNA (ACTG).
什么是他们是如何工作的主要区别是什么？哪一个是更快？哪一个是较少的计算机贪婪？在什么情况下？
What are the main differences in how they work? Which one is faster? Which one is less computer-greedy? In which cases?
推荐答案
摩尔定律UTexas网页通过这两种算法在一步一步的方式走（他还提供了各种技术资源）：
Moore's UTexas webpage walks through both algorithms in a step-by-step fashion (he also provides various technical sources):
- <一个href="http://www.cs.utexas.edu/~moore/best-ideas/string-searching/kpm-example.html">Knuth-Morris-Pratt
- <一个href="http://www.cs.utexas.edu/~moore/best-ideas/string-searching/fstrpos-example.html">Boyer-Moore
- Knuth-Morris-Pratt
- Boyer-Moore
据他本人，
经典博耶 - 穆尔算法的现象，它受到 往往不那么有效地开展工作的小字母类似DNA。跳跃 距离趋于停止与图案长度，因为越来越多 子再频频发生。通过记住更多的东西都有 已经匹配，可以通过文字变大跳跃。一 甚至可以安排``完美的记忆'，从而看看每个字符 最多一次，而博耶 - 穆尔算法，而线性的，可 检查从文本多次的字符。这个想法 记住以上已探索在文献中被他人。它 患有需要非常大的表格或状态机。
The classic Boyer-Moore algorithm suffers from the phenomenon that it tends not to work so efficiently on small alphabets like DNA. The skip distance tends to stop growing with the pattern length because substrings re-occur frequently. By remembering more of what has already been matched, one can get larger skips through the text. One can even arrange ``perfect memory'' and thus look at each character at most once, whereas the Boyer-Moore algorithm, while linear, may inspect a character from the text multiple times. This idea of remembering more has been explored in the literature by others. It suffers from the need for very large tables or state machines.
不过，也出现了BM ，都使得一些小型修改字母表寻找可行的。
However, there have been some modifications of BM that have made small-alphabet searching viable.
这篇关于什么是高德纳 - 莫里斯 - 普拉特和博耶 - 穆尔搜索算法之间的主要区别是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
