比BMH (Boyer-Moore-Horspool)搜索更快的算法
你会使用哪种算法来搜索短文本中的短子字符串？简而言之，我的意思是5-10个字符的子串和255个字符的字符串。我在考虑根据输入数据长度来选择算法。对于较长的输入，哪种算法更好？
回答 5
Stack Overflow用户
发布于 2009-05-25 10:07:07
试试Turbo-BM。然而，对于如此短的字符串，IMO通常的线性扫描就足够了。
Stack Overflow用户
发布于 2011-07-17 18:07:54
如果你正在寻找一种比Boyer Moore更好的算法，那么你就需要一个混合的答案。
据我所知，只有后缀树在文本搜索中胜过Boyer Moore。然而，它使用更多的时间来创建索引，并使用更多的磁盘空间。
附加信息:速度明智，后缀树或后缀数组胜过任何版本的Boyer Moore，因为后缀树基本上实现了树状数据结构中所有可能的搜索。
然而，后缀树具有较高的ram内存成本，并且索引文本(创建树数据结构)的速度较慢。
Boyer Moore与后缀树的速度差异: Boyer Moore在搜索文本上是线性的。后缀树在搜索模式上是线性的。
如果要在200个字符的文本中搜索5个字母单词，boyer moore将执行200个操作，后缀树将执行5个操作。
尽管它可能会更快，但它很难实现。就数据结构的难度而言，它可能是最难的。一旦建成，它就可以在空间和速度上进行极大的优化。
这就是说，在接下来的几年里寻找后缀树。通常，后缀树用于DNA索引和网络搜索引擎优化。
Boyer Moore到处都在使用，例如常规程序(文本搜索功能)，并在网络搜索引擎中广泛使用。
Stack Overflow用户
发布于 2012-01-19 03:24:48
@anon @Anton Gogolev
用一个词来回答你的问题: Railgun_Quadruplet
这个C函数在短小的2,3,4模式与160个字符的字符串上进行了如此严格的测试，以至于在这个表http://www.sanmayce.com/Railgun/index.html#Heavy-Search-Hustle上你可以自己决定。
另一篇文章请访问：http://www.codeproject.com/KB/cpp/Railgun_Quadruplet.aspx
https://stackoverflow.com/questions/906130
复制相似问题
腾讯云开发者
