什么是最快的子stringsearchalgorithm？

好的，所以我不会听起来像一个白痴，我会更明确地陈述问题/要求：

• Needle（pattern）和haystack（text to search）都是C样式的以null结尾的string。 没有提供长度信息; 如果需要，它必须被计算。
• 函数应返回指向第一个匹配的指针，如果找不到匹配项，则返回NULL 。
• 故障情况是不允许的。 这意味着任何具有非恒定（或大的恒定）存储要求的algorithm都需要具有分配失败的回退情况（并且后备处理中的性能因此导致最坏情况的性能）。
• 实现是用C语言编写的，但是没有代码的algorithm（或者链接到这个）的一个很好的描述也不错。

…以及我所说的“最快”的意思是：

• 确定性O(n)其中n =干草堆长度。 （但是，如果将它们与更稳健的algorithm结合以提供确定性O(n)结果），则可以使用通常为O(nm)algorithm（例如滚动哈希）的想法。
• 从来没有执行过（可测量的; if (!needle[1])等几个时钟是可以的），比天真的蛮力algorithm更糟糕，特别是在非常短的针头上，这可能是最常见的情况。 （无条件繁重的预处理开销是不好的，因为试图以牺牲可能的针头为代价来提高病态针头的线性系数）。
• 给定一个任意的针和干草堆，相比或更好的性能（不比其他任何其他广泛实施的algorithm更长的search时间50％）。
• 除了这些条件之外，我将离开“最快”的开放式的定义。 一个好的答案应该解释为什么你考虑你build议“最快”的方法。

我目前的实现比glibc的双向实现运行速度大概慢10％到8倍（取决于input）。

更新：我目前的最优algorithm如下：

• 对于长度为1的针，请使用strchr 。
• 对于长度为2-4的针，使用机器字一次比较2-4个字节：预加载一个16位或32位整数的移位，并在每次迭代时从干草堆中循环旧字节输出/新字节。 干草堆的每个字节都只读一次，并对0（string结尾）和一个16位或32位比较进行检查。
• 对于长度大于4的针头，使用双向algorithm和一个仅适用于窗口最后一个字节的错误移位表（如Boyer-Moore）。 为了避免初始化一个1kb表的开销（这对于许多中等长度的针来说是一个净损失），我保留一个位数组（32字节）来标记移位表中的哪些入口被初始化。 未设置的位对应于从不出现在针中的字节值，可以进行全针长度的移位。

我脑海中留下的大问题是：

• 有没有办法更好地使用坏class表？ Boyer-Moore通过向后扫描（从右到左）充分利用它，但是双向需要从左到右的扫描。
• 在一般情况下，我发现的唯一两个可行的候选algorithm（没有内存不足或二次性能条件）是有序字母上 的双向和string匹配 。 但是，在那里容易检测到不同的algorithm是最优的？ 当然，空间algorithm中的许多O(m) （其中m是针长）可用于m<100左右。 如果有一个简单的testing针可能只需要线性时间，那么也可以使用最差二次方法。

奖励积分为：

• 你可以通过假设针和干草堆都是格式良好的UTF-8来提高性能吗？ （使用字节长度不同的字符时，良好的结构会在针头和干草堆之间施加一些stringalignment要求，并且在遇到不匹配的头字节时允许自动2-4字节的移位。最大的后缀计算，好的后缀转换等已经给你各种algorithm？）

注意：我很清楚大部分的algorithm，只是没有在实践中performance如何。 这里有一个很好的参考，所以人们不会给我algorithm的参考作为评论/答案： http : //www-igm.univ-mlv.fr/~lecroq/string/index.html

Answer 1

build立一个可能的针和干草堆testing库。 在几种searchalgorithm上进行testing，包括蛮力。 select一个性能最好的数据。

Boyer-Moore使用一个坏字符表和一个好的后缀表。

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

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

拉宾卡普使用运行哈希。

它们都是为了减less比较而进行交易，所以真实世界的performance将取决于针和干草堆的平均长度。 初始开销越大，input越长越好。 用很短的针，蛮力可能会赢。

编辑：

一个不同的algorithm可能是最好的查找碱基对，英语短语，或单个单词。 如果对于所有的input有一个最好的algorithm，它将被公布。

想想下面的小桌子。 每个问号可能有不同的最佳searchalgorithm。

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

这实际上应该是一个图表，每个坐标轴上的input范围从较短到较长。 如果您在这样的图上绘制每个algorithm，每个algorithm都会有不同的签名。 一些algorithm在模式中遭受了很多重复，这可能会影响search基因等用途。 影响整体performance的一些其他因素是不止一次地search相同的模式，同时search不同的模式。

如果我需要一个样本集，我想我会刮如谷歌或维基百科的网站，然后从所有的结果页剥离HTML。 对于search网站，input一个单词，然后使用其中一个build议的search词组。 select几种不同的语言（如果适用）。 使用网页，所有的文本将是短到中，所以合并足够的网页，以获得更长的文本。 您还可以find公共领域的书籍，法律logging和其他大量文本。 或者通过从字典中select单词来生成随机内容。 但是分析的目的是针对您要search的内容types进行testing，所以尽可能使用真实世界的样本。

我留下了一个又短又长的模糊。 对于针，我认为短为8字以下，中等以下为64字以内，长度在1k以下。 对于草垛，我认为是2 ^ 10以下，2 ^ 20以下，长达2 ^ 30个字符。

Answer 2

您指向的http://www-igm.univ-mlv.fr/~lecroq/string/index.html链接是一些最好的已知和研究的string匹配algorithm的优秀资源和摘要。;

大多数search问题的解决scheme涉及预处理开销，时间和空间要求方面的权衡。 在任何情况下，单个algorithm都不是最优的或实际的。

如果你的目标是devise一个特定的stringsearchalgorithm，那么忽略我不得不说的其余部分，如果你想开发一个通用stringsearch服务例程，那么请尝试以下操作：

花一些时间回顾一下你已经提到的algorithm的具体优缺点。 为了find一组覆盖您感兴趣的stringsearch的范围和范围的algorithm，进行回顾。然后，基于分类器函数构build前端searchselect器，以针对给定input的最佳algorithm。 这样你可以使用最有效的algorithm来完成这项工作。 当一个algorithm对某些search非常好，但是效果不好时，这个特别有效。 例如，蛮力对于长度为1的针来说可能是最好的，但是随着针长度的增加，其快速降低，因此， sustik-moorealgorithm可以变得更有效率（超过小字母），然后针对更长的针和更大的字母，KMP或Boyer – algorithm可能会更好。 这些只是举例说明一个可能的策略。

多重algorithm的方法不是一个新的想法。 我相信它已经被一些商业sorting/search包使用（例如在主机上常用的SYNCSORT实现几种sortingalgorithm，并且使用启发式来为给定的inputselect“最好的”）

每种searchalgorithm都有几种不同的变化forms，可以在性能上产生显着的差异，例如本文所述 。

对您的服务进行基准testing，对需要额外search策略的领域进行分类，或者更有效地调整您的select器function。 这种方法不是快捷或容易，但如果做得好，可以产生很好的结果。

Answer 3

我很惊讶地看到我们在这个讨论中引用的技术报告。 我是以上被命名为Sustik-Moore的algorithm的作者之一。 （我们的论文中没有使用这个术语。）

我想在这里强调，对于我来说，algorithm最有趣的特点是certificate每个字母最多只被检查一次是相当简单的。 对于早期的Boyer-Moore版本，他们certificate每个字母至多被检查3次，最多2次，这些证据被更多地包括在内（见引文）。 因此，我也看到提出/研究这个变体的教学价值。

在本文中，我们还描述了进一步的变化，在放松理论保证的同时，为了效率。 这是一篇简短的论文，我认为这些材料应该可以理解为普通高中gradle生。

我们的主要目标是把这个版本引入可以进一步改进的其他人的注意力。 stringsearch有太多的变化，我们不能想到这个想法可以带来什么好处。 （固定文本和变化模式，固定模式不同文本，可能/不可能预处理，并行执行，在大文本中查找匹配子集，允许错误，接近匹配等）

Answer 4

发布于2011年，我相信它很可能是Dany Breslauer，Roberto Grossi和Filippo Mignosi的“Simple Real-Time Constant-Space String Matching”algorithm。

更新：

在2014年，作者发表了这样的改进： 迈向最佳包装string匹配 。

Answer 5

最快的子stringsearchalgorithm将取决于上下文：

1. 字母大小（例如DNA与英文）
2. 针的长度

2010年的论文“精确string匹配问题：一个全面的实验评估”给出了51个algorithm的运行时间表（不同的字母大小和针长度），所以你可以select最适合你的上下文的algorithm。

所有这些algorithm都有C实现，以及一个testing套件，在这里：

http://www.dmi.unict.it/~faro/smart/algorithms.php

Answer 6

一个很好的问题。 只需添加一些微小的部分…

1. 有人在谈论DNA序列匹配。 但是对于DNA序列，我们通常做的是为干草堆build立一个数据结构（例如后缀数组，后缀树或者FM-索引）并且匹配许多针。 这是一个不同的问题。

2. 如果有人想要对各种algorithm进行基准testing，这将是非常好的。 有很好的压缩和后缀数组的build设基准，但我没有看到一个string匹配的基准。 潜在的干草堆候选人可能来自SACA基准 。

3. 前几天我从你推荐的页面testingBoyer-Moore实现（编辑：我需要一个像memmem（）函数调用，但它不是一个标准function，所以我决定实现它）。 我的基准testing程序使用随机干草堆。 Boyer-Moore的实现似乎比glibc的memmem（）和Mac的strnstr（）快了许多倍。 如果你有兴趣，实现在这里 ，基准代码在这里 。 这绝对不是一个现实的基准，但它是一个开始。

Answer 7

我知道这是一个古老的问题，但大多数不好的转换表是单个字符。 如果你的数据集合是有意义的（例如特别是如果有文字的话），如果你有足够的空间，你可以通过使用由n-gram而不是单个字符组成的错误转换表来获得惊人的加速。

Answer 8

这是Python的search实现 ，从整个核心使用。 注释表明它使用了一个压缩的boyer-moore delta 1表 。

我已经做了一些相当广泛的实验，用stringsearch自己，但它是多个searchstring。 Horspool和Bitap的组装实现通常可以对Aho-Corasick这样的algorithm持有自己的低模式计数。

Answer 9

你可以实现4种不同的algorithm。 每M分钟（根据经验确定）在当前的实际数据上运行全部4个分钟。 累计N次运行（也是待定）的统计数据。 然后只用下一个M分钟的赢家。

在Wins上logging统计数据，这样你就可以replace从来没有赢过的algorithm。 集中优化努力，赢得例程。 在对硬件，数据库或数据源进行任何更改之后，请特别注意统计信息。 如果可能，请将这些信息包含在统计日志中，这样就不必从日志date/时间戳中找出它。

Answer 10

您可能还希望有多种types的string，因为这可能会对性能产生很大的影响。 algorithm在search自然语言的基础上会有不同的performance（甚至在这里，由于形态的不同，可能会有细微的区别），DNAstring或随机string等。

字母大小将在许多algorithm中扮演angular色，针的大小也一样。 例如Horspool在英文文本上做得很好，但由于不同的字母大小，对DNA有坏处，使得人生难以应付坏人的规则。 后缀的介绍很大程度上是可以接受的。

Answer 11

使用stdlib strstr ：

 char *foundit = strstr(haystack, needle); 

速度非常快，只花了我5秒左右的时间打字。

Answer 12

更快的“search单个匹配字符”（ala strchr ）algorithm。

重要笔记：

• 这些函数使用“（首尾）零的数目/计数” gcc compiler intrinsic- __builtin_ctz 。 这些函数在具有执行此操作的指令的机器上（例如，x86，ppc，arm）可能只会很快。

• 这些函数假定目标体系结构可以执行32位和64位未alignment的加载。 如果你的目标架构不支持这个，你将需要添加一些启动逻辑来正确alignment读取。

• 这些function是处理器中立的。 如果目标CPU有向量指令，那么你可能会做得更好。 例如，下面的strlen函数使用SSE3，并且可以进行简单的修改，以异或字节扫描来查找除0以外的字节。 在运行Mac OS X 10.6（x86_64）的2.66GHz Core 2笔记本电脑上执行的基准testing：

  • strchr为strchr MB / s
  • findFirstByte64为2656.742 MB / s
  • strlen为13094.479 MB / s

…一个32位版本：

 #ifdef __BIG_ENDIAN__ #define findFirstZeroByte32(x) ({ uint32_t _x = (x); _x = ~(((_x & 0x7F7F7F7Fu) + 0x7F7F7F7Fu) | _x | 0x7F7F7F7Fu); (_x == 0u) ? 0 : (__builtin_clz(_x) >> 3) + 1; }) #else #define findFirstZeroByte32(x) ({ uint32_t _x = (x); _x = ~(((_x & 0x7F7F7F7Fu) + 0x7F7F7F7Fu) | _x | 0x7F7F7F7Fu); (__builtin_ctz(_x) + 1) >> 3; }) #endif unsigned char *findFirstByte32(unsigned char *ptr, unsigned char byte) { uint32_t *ptr32 = (uint32_t *)ptr, firstByte32 = 0u, byteMask32 = (byte) | (byte << 8); byteMask32 |= byteMask32 << 16; while((firstByte32 = findFirstZeroByte32((*ptr32) ^ byteMask32)) == 0) { ptr32++; } return(ptr + ((((unsigned char *)ptr32) - ptr) + firstByte32 - 1)); } 

…和一个64位版本：

 #ifdef __BIG_ENDIAN__ #define findFirstZeroByte64(x) ({ uint64_t _x = (x); _x = ~(((_x & 0x7F7F7F7F7f7f7f7full) + 0x7F7F7F7F7f7f7f7full) | _x | 0x7F7F7F7F7f7f7f7full); (_x == 0ull) ? 0 : (__builtin_clzll(_x) >> 3) + 1; }) #else #define findFirstZeroByte64(x) ({ uint64_t _x = (x); _x = ~(((_x & 0x7F7F7F7F7f7f7f7full) + 0x7F7F7F7F7f7f7f7full) | _x | 0x7F7F7F7F7f7f7f7full); (__builtin_ctzll(_x) + 1) >> 3; }) #endif unsigned char *findFirstByte64(unsigned char *ptr, unsigned char byte) { uint64_t *ptr64 = (uint64_t *)ptr, firstByte64 = 0u, byteMask64 = (byte) | (byte << 8); byteMask64 |= byteMask64 << 16; byteMask64 |= byteMask64 << 32; while((firstByte64 = findFirstZeroByte64((*ptr64) ^ byteMask64)) == 0) { ptr64++; } return(ptr + ((((unsigned char *)ptr64) - ptr) + firstByte64 - 1)); } 

编辑2011/06/04 OP在评论中指出，这个解决scheme有一个“不可逾越的错误”：

它可以读取经过查找的字节或空终止符，这可以在没有读取权限的情况下访问未映射的页面或页面。 除非alignment，否则你不能在string函数中使用大的读取。

这在技术上是正确的，但是几乎适用于任何大于单个字节的块操作的algorithm，包括OP在评论中build议的方法 ：

一个典型的strchr实现并不幼稚，但比你提供的要高效得多。 查看最广泛使用的algorithm的结尾： http : //graphics.stanford.edu/~seander/bithacks.html#ZeroInWord

这本身也和排列没有任何关系。 诚然，这可能会导致在大多数常用体系结构中使用的行为，但这与微体系结构实现细节有关。如果未alignment的读取跨越了4K边界（又是典型的），那么读取将导致程序如果下一个4K页边界未被映射，则终止故障。

但是，在strchr给出的algorithm中这不是一个“bug” – 行为是因为像strchr和strlen这样的函数不接受length参数来限制search的大小。 searchchar bytes[1] = {0x55}; ，对于我们讨论的目的，恰好恰好放置在4K VM页面边界的末端，下一页未映射，其中strchr(bytes, 0xAA) （其中strchr是一个字节实现）将以完全相同的方式崩溃。 同上strchr相关表哥strlen 。

如果没有length参数，则无法确定什么时候应该退出高速algorithm并返回逐字节algorithm。 更可能的“错误”将是读取“超过分配的大小”，这在技术上导致根据各种C语言标准的undefined behavior ，并且将被标记为诸如valgrind类的错误。

总而言之，任何运行在比字节块大的数据块上的速度会更快，因为这个答案代码和OP指出的代码必须具有字节准确的读取语义，如果没有length参数，它可能是“错误的”控制“最后一次阅读”的angular落案例。

在这个答案中的代码是一个内核，可以快速find一个自然的CPU字大小块的第一个字节，如果目标CPU有一个快速的类似ctz指令。 添加诸如确保它仅在正确alignment的自然边界上操作或者以某种forms的length方式添加事物是微不足道的，这将允许您从高速内核切换到较慢的逐字节检查。

OP也在评论中指出：

至于你的ctz优化，它只会对O（1）尾部操作产生影响。 它可以提高性能与微小的string（如strchr("abc", 'a');但肯定不与任何主要大小的string。

这个陈述是否真实取决于所讨论的微架构。 使用规范的4级RISCstream水线模型，那么它几乎肯定是真的。 但是很难判断一个现代乱序的超级标量CPU是否真的如此，其核心速度完全可以超越内存stream速。 在这种情况下，“可以退出的指令的数量”相对于“可以stream式传输的字节数”有很大的差距，这样就不仅是可信的，而且是相当普遍的，每个可以stream式传输的字节可以退出的指令数“。 如果这足够大， ctz + shift指令可以“免费”完成。

Answer 13

只要search“最快的strstr”，如果你看到有兴趣的东西就问我。

在我看来，你对自己施加了太多的限制（是的，我们都希望在最大search者处有次线性线性），然而它需要一个真正的程序员介入，直到那时我认为哈希方法只是一个漂亮的解决scheme由BNDM对2..16个较短的图案进行加固）。

只是一个简单的例子：

（32字节）searchstring（206908949bytes）…跳过性能（更好的更好）：3041％，6801754跳过/迭代Railgun_Quadruplet_7Hasherezade_hits / Railgun_Quadruplet_7Hasherezade_clocks：0/58 Railgun_Quadruplet_7Hasherezade performance： 3483KB /时钟

（32字节）searchstring（206908949bytes）作为一行…跳跃性能（更好的更好）：1554％，13307181跳过/迭代Boyer_Moore_Flensburg_hits / Boyer_Moore_Flensburg_clocks：0/83 Boyer_Moore_Flensburg_clock ： 2434KB /时钟

search模式（32字节）为string（206908949字节）为一行…跳过性能（越大越好）：129％，160239051跳过/迭代Two-Way_hits / Two-Way_clocks：0/816 两-performance： 247KB /时钟

Sanmayce，
问候

Answer 14

在你的问题中提到的双向algorithm（顺便提一下，这个algorithm是不可思议的！）最近已经得到改进，可以一次有效地处理多字节的单词： 最佳压缩string匹配 。

我还没有看完整篇文章，但似乎他们依赖于一些新的特殊的CPU指令（包括在例如SSE 4.2中）是O（1），因为它们的时间复杂性要求，尽pipe如果它们不可用，它们可以在O（log log w）时间内对它们进行模拟，使得w位字不会听起来太糟糕。

Answer 15

我最近发现了一个很好的工具来衡量各种可用algorithm的性能： http ://www.dmi.unict.it/~faro/smart/index.php

You might find it useful. Also, if I have to take a quick call on substring search algorithm, I would go with Knuth-Morris-Pratt.

Answer 16

I don't know if it's the absolute best, but I've had good experience with Boyer-Moore .