首先我对算法知之甚少,所以请多多包涵。
据我了解,使用长 key 时 Boyer Moore 算法最快。那么,如果我有一个非常短的键(例如 10 个字符)和大量要搜索的文本(超过 10,000 个字符)怎么办? Boyer Moore 会是这种情况下的最佳搜索算法吗?
如果不是会是什么?
最佳答案
根据 String searching algorithm , “Boyer–Moore 字符串搜索算法一直是实用字符串搜索文献的标准基准。”它并不总是最快的,但总的来说是可行的方法。
当您谈论像 10,000 个字符这样的小文本缓冲区时,Knuth-Morris-Pratt 和 Boyer-Moore 在运行时间上非常接近。在现代计算机上运行时,即使是简单的字符串搜索在 10K 缓冲区上也会快得令人眼花缭乱。我怀疑您会发现 KMP 和 Boyer-Moore 两者在 10,000 个字符的缓冲区中搜索 10 个字符的字符串之间的差异将在纳秒级。
这种情况下最好的搜索算法?这将取决于您需要调用它的频率。如果它每秒被调用几次(最多),我可能会编写一个天真的搜索并将其保留在那里。与您的程序的运行时间相比,Boyer-Moore 搜索和在那个小缓冲区上的简单搜索之间的差异微不足道,您的优化工作最好花在其他地方。如果我必须每秒调用它数百或数千次,我会花时间编写优化的 Boyer-Moore 搜索。
关于string - Boyer Moore 寻找小 key ,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7585597/