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

Question

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

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

如何才能使朴素搜索算法搜索算法比大多数其他算法更快？

用转换表实现的确定性有限状态机(执行时间总是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执行得很好。

Answer 2

从理论上讲，好的算法(较低的时间复杂度)通常具有较高的记账成本，对于小问题规模，这可能会压倒幼稚的算法。实现细节也很重要。通过优化实现，您有时可以将运行时提高2倍或更多。

Answer 3

对于随机输入数据，朴素的实现实际上具有线性的预期运行时间(与BM/KMP等相同)。我不能在这里写一个完整的证明，但它可以从算法，设计，技术和分析中获得。

大多数精确匹配算法都是朴素实现的优化版本，以防止被某些模式减慢。例如，假设我们正在搜索：

   aaaaaaaaaaaaaaaaaaaaaaaab

在一系列的：

   aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab

它在b上失败了很多次。KMP/BM的实现是为了防止重复比较a。然而，如果序列本身是随机的，这种情况几乎不可能出现，而且由于其较低的记账开销或可能更好的空间/时间局部性，朴素的实现可能会工作得更好。

是的，我不确定DNA序列是随机的。或者是它们中常见的重复。无论如何，如果没有代表性的数据，就没有办法仔细检查这一点。