string - Boyer Moore 寻找小 key

Question

首先我对算法知之甚少，所以请多多包涵。

据我了解，使用长 key 时 Boyer Moore 算法最快。那么，如果我有一个非常短的键(例如 10 个字符)和大量要搜索的文本(超过 10,000 个字符)怎么办？Boyer Moore 会是这种情况下的最佳搜索算法吗？

如果不是会是什么？

Answer 1

根据 String searching algorithm , “Boyer–Moore 字符串搜索算法一直是实用字符串搜索文献的标准基准。”它并不总是最快的，但总的来说是可行的方法。

当您谈论像 10,000 个字符这样的小文本缓冲区时，Knuth-Morris-Pratt 和 Boyer-Moore 在运行时间上非常接近。在现代计算机上运行时，即使是简单的字符串搜索在 10K 缓冲区上也会快得令人眼花缭乱。我怀疑您会发现 KMP 和 Boyer-Moore 两者在 10,000 个字符的缓冲区中搜索 10 个字符的字符串之间的差异将在纳秒级。

这种情况下最好的搜索算法？这将取决于您需要调用它的频率。如果它每秒被调用几次(最多)，我可能会编写一个天真的搜索并将其保留在那里。与您的程序的运行时间相比，Boyer-Moore 搜索和在那个小缓冲区上的简单搜索之间的差异微不足道，您的优化工作最好花在其他地方。如果我必须每秒调用它数百或数千次，我会花时间编写优化的 Boyer-Moore 搜索。