string - 为什么朴素的字符串搜索算法更快？

Question

我正在测试这个网站的字符串搜索算法:EXACT STRING MATCHING ALGORITHMS. Christian Charras, Thierry Lecroq .测试文本是 1 GByte 大小的随机 DNA 碱基序列 (ACGT)。测试模式是随机大小(最大 1kB)的随机序列列表。测试系统是 AMD Phenom II x4 955，3.2 GHz，4 GB RAM 和 Windows 7 64 位。用 C 编写的代码，并使用带有 -O3 标志的 MinGW 编译。

朴素搜索算法对于短模式需要 4 秒，对于 1kB 模式需要 8 秒。确定性有限状态机对于短模式需要 2 秒，对于 1kB 模式需要 4 秒。 Boyer-Moore 算法对于非常短的模式需要 4 秒，对于短模式大约需要 1/2 秒，对于 1kB 模式需要 2 秒。其余算法性能比朴素搜索算法差。

naive search algorithm 搜索算法如何比大多数其他算法更快？

使用转换表(执行时间始终为 O(n))实现的确定性有限状态机如何比 Boyer-Moore 算法慢 2 到 8 倍？是的，BM最好的情况是O(n/m)，但是他的平均情况是O(n)，最坏的情况是O(nm)。

Answer 1

不存在适用于所有情况的完美字符串匹配算法。

Boyer-Moore(以及 Horspool、Sunday 等)通过创建跳转表(“当字符不匹配时，我可以将搜索指针移动多远？字符串中不同的字母越多，积极影响越好。您可以想象，只有 4 个不同字母的字符串会创建一个跳转表，每个不匹配最多有 3 个移位。而搜索区分大小写的英文单词可能会导致跳转表 (A-Z + a-z + 标点符号)每次不匹配最多约 55 次转换。

另一方面，这对准备工作(即计算跳转表)和循环本身都有负面影响。所以这些算法在短字符串(准备工作会产生开销)和只有几个不同字母的字符串(如前所述)上表现不佳

朴素搜索算法非常紧凑，循环内部的操作非常少，因此循环运行速度很快。由于没有开销，它在搜索短字符串时表现更好。

BM 算法的(与朴素搜索相比)相当复杂的循环操作每次循环运行需要更长的时间。这(部分)补偿了跳转表的积极性能影响。

因此，尽管您使用的是长字符串，但小字母表(=小跳转表)会使 BM 表现不佳。 KMP 在循环中的开销较小(跳转表通常较小，但类似于具有小字母的 BM)，因此 KMP 的性能非常好。