c - 最快的子串搜索算法是什么？

Question

好的，所以我听起来不像个白痴，我将更明确地说明问题/要求:

Needle(模式)和 haystack(要搜索的文本)都是 C 风格的以空字符结尾的字符串。没有提供长度信息；如果需要，必须进行计算。

函数应该返回一个指向第一个匹配项的指针，或者 NULL如果没有找到匹配。

不允许出现故障情况。这意味着任何具有非常量(或大常数)存储要求的算法都需要有分配失败的回退情况(因此回退护理中的性能有助于最坏情况的性能)。

实现是用 C 语言实现的，尽管没有代码的算法(或指向此类的链接)的良好描述也很好。

...以及我所说的“最快”的意思:

确定性 O(n)哪里n = 干草堆长度。 (但是，如果将通常为 O(nm)(例如滚动哈希)的算法与更健壮的算法相结合以给出确定性的 O(n) 结果，则可以使用这些算法的想法)。

永远不会执行(可测量的；if (!needle[1]) 等的几个时钟都可以)比朴素的蛮力算法差，尤其是在很短的针上，这可能是最常见的情况。 (无条件的繁重预处理开销很糟糕，因为试图以牺牲可能的针为代价来提高病理针的线性系数也是如此。)

给定一个任意的针头和大海捞针，与任何其他广泛实现的算法相比，性能相当或更好(搜索时间不超过 50%)。

除了这些条件之外，我将“最快”的定义保持开放。一个好的答案应该解释为什么您认为您建议的方法是“最快的”。

我当前的实现运行速度大约比 glibc 的双向实现慢 10% 和快 8 倍(取决于输入)。

更新:我目前的最优算法如下:

对于长度为 1 的针，使用 strchr .

对于长度为 2-4 的针，使用机器字一次比较 2-4 个字节，如下所示:将针预加载到 16 位或 32 位整数中并进行位移，并在每次迭代时从干草堆中循环旧字节出/新字节. haystack 的每个字节都被精确读取一次，并针对 0(字符串结尾)和一个 16 位或 32 位比较进行检查。

对于长度 > 4 的针，使用带有错误移位表(如 Boyer-Moore)的双向算法，该算法仅应用于窗口的最后一个字节。为了避免初始化一个 1kb 表的开销，这对于许多中等长度的针来说是一个净损失，我保留了一个位数组(32 字节)来标记移位表中的哪些条目被初始化。未设置的位对应于从未出现在针中的字节值，对于这些值可以进行全针长移位。

留在我脑海中的大问题是:

有没有办法更好地利用坏类次表？ Boyer-Moore 通过向后扫描(从右到左)来充分利用它，但双向扫描需要从左到右扫描。

我为一般情况(没有内存不足或二次性能条件)找到的仅有的两个可行的候选算法是 Two-Way和 String Matching on Ordered Alphabets .但是，是否存在易于检测的情况，其中不同的算法是最佳的？肯定很多O(m) (其中 m 是针长)空间算法可用于 m<100左右。如果有一个简单的针测试，证明只需要线性时间，那么也可以使用最坏情况二次方的算法。

奖励积分:

您能否通过假设 Needle 和 haystack 都是格式良好的 UTF-8 来提高性能？ (对于不同字节长度的字符，格式良好在指针和 haystack 之间强加了一些字符串对齐要求，并在遇到不匹配的头字节时允许自动 2-4 个字节移位。但是这些限制是否会给你带来很多/超出什么？最大后缀计算、良好的后缀移位等已经为您提供了各种算法？)

注:我很清楚那里的大多数算法，只是不知道它们在实践中的表现如何。这是一个很好的引用，所以人们不会一直给我作为评论/答案的算法引用: http://www-igm.univ-mlv.fr/~lecroq/string/index.html

Answer 1

建立一个可能的针头和大海捞针的测试库。分析几种搜索算法的测试，包括蛮力。选择最适合您的数据的一种。

Boyer-Moore使用带有良好后缀表的坏字符表。

Boyer-Moore-Horspool使用坏字符表。

Knuth-Morris-Pratt使用部分匹配表。

Rabin-Karp使用运行哈希。

它们都以不同程度的减少比较来交换开销，因此现实世界的性能将取决于针和干草堆的平均长度。初始开销越多，输入越长越好。使用非常短的针头，蛮力可能会获胜。

编辑:

不同的算法可能最适合查找碱基对、英语短语或单个单词。如果所有输入都有一种最佳算法，它就会被公开。

想想下面的小 table 。每个问号可能有不同的最佳搜索算法。

                 short needle     long needle
short haystack         ?               ?
long haystack          ?               ?

这应该是一个图表，每个轴上都有一系列较短到较长的输入。如果在这样的图上绘制每个算法，每个算法都会有不同的签名。一些算法在模式中存在大量重复，这可能会影响搜索基因等用途。影响整体性能的其他一些因素是多次搜索相同的模式并同时搜索不同的模式。

如果我需要一个样本集，我想我会抓取像 google 或 wikipedia 这样的网站，然后从所有结果页面中删除 html。对于搜索站点，输入一个词，然后使用建议的搜索短语之一。如果适用，请选择几种不同的语言。使用网页，所有的文本都是短到中等的，所以合并足够多的页面以获得更长的文本。您还可以找到公共(public)领域的书籍、法律记录和其他大量文本。或者只是通过从字典中挑选单词来生成随机内容。但分析的重点是针对您将搜索的内容类型进行测试，因此如果可能，请使用真实世界的样本。

我留下了简短和长期的模糊。对于针，我认为短的是8个字符以下，中的是64个字符以下，长的是1k以下。对于干草堆，我认为短是在 2^10 以下，中是在 2^20 以下，最长是 2^30 个字符。