最快的子串搜索算法是什么?

我不知道它是否是绝对最好的，但我对Boyer-Moore有很好的经验。

建立一个可能的针和干草堆的测试库。分析几种搜索算法的测试，包括蛮力算法。选择一个对你的数据表现最好的。

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

Boyer-Moore-Horspool使用了一个坏字符表。

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

- karp使用运行散列。

它们都以不同程度的开销来减少比较，因此真实世界的性能将取决于针和干草堆的平均长度。初始开销越大，输入越长越好。用很短的针，蛮力可能会赢。

编辑:

另一种算法可能是查找碱基对、英语短语或单个单词的最佳算法。如果对所有输入有一个最佳算法，它早就被公布了。

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

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

这应该是一个图形，每个轴上的输入范围从短到长。如果将每个算法绘制在这样的图上，每个算法都会有不同的签名。一些算法在模式中有很多重复，这可能会影响到像搜索基因这样的用途。影响整体性能的其他一些因素包括多次搜索相同的模式和同时搜索不同的模式。

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

我留下了短暂而漫长的模糊。对于针，我认为短是8个字符以下，中是64个字符以下，长是1k以下。对于草堆，我认为短字符小于2^10，中字符小于2^20，长字符大于2^30。

http://www-igm.univ-mlv.fr/~lecroq/string/index.html 你所指的链接是 一个极好的来源和总结的一些最著名的和研究

您可能还希望使用多种类型的字符串进行不同的基准测试，因为这可能会对性能产生很大影响。算法将根据搜索自然语言(即使在这里，由于形态的不同，仍然可能存在细微的区别)，DNA字符串或随机字符串等执行不同的操作。

字母大小将在许多算法中发挥作用，针头大小也一样。例如，Horspool在英语文本上做得很好，但在DNA上做得很差，因为字母大小不同，这使得“坏字符规则”很难实施。引入good后缀可以大大缓解这种情况。

这是一个非常好的问题。只要加一些小块……

1. 有人在谈论DNA序列匹配。但对于DNA序列，我们通常做的是为干草堆建立一个数据结构(例如后缀数组，后缀树或FM-index)，并将许多针与之匹配。这是一个不同的问题。

2. 如果有人愿意对各种算法进行基准测试，那就太好了。在压缩和后缀数组构造方面有非常好的基准测试，但我还没有看到字符串匹配方面的基准测试。潜在的候选干草堆可以从SACA基准。

3. 几天前，我从< A href="http://www-igm.univ-mlv.fr/~lecroq/string/node14.html" rel="nofollow noreferrer">你推荐的页面测试了Boyer-Moore实现(编辑:我需要一个像memmem()这样的函数调用，但它不是一个标准函数，所以我决定实现它)。我的基准测试程序使用随机草堆。该页面中的Boyer-Moore实现似乎比glibc的memmem()和Mac的strnstr()快几倍。如果您感兴趣，实现是here和基准测试代码是here。这绝对不是一个现实的基准，但它是一个开始。

使用stdlib strstr:

char *foundit = strstr(haystack, needle);

它非常快，我只花了大约5秒钟打字。

这里是Python的搜索实现，在整个核心中使用。注释表明它使用压缩波埃-摩尔δ 1表。

我自己做过一些相当广泛的字符串搜索实验，但它是针对多个搜索字符串的。对于较低的模式计数，霍斯普和Bitap的程序集实现通常可以对抗像Aho-Corasick这样的算法。

一个更快的“搜索单个匹配字符”(ala strchr)算法。

重要提示:

• 这些函数使用一个"number / count of(前导|尾随)0 " gcc编译器intrinsic- __builtin_ctz。这些函数可能只有在具有执行此操作的指令的机器(即x86、ppc、arm)上才能快速运行。

• 这些功能假定目标体系结构可以执行32位和64位未对齐负载。如果您的目标体系结构不支持这一点，您将需要添加一些启动逻辑来正确对齐读取。

• 这些函数与处理器无关。如果目标CPU有矢量指令，您可能会做得(好得多)。例如，下面的strlen函数使用SSE3，可以简单地将扫描的字节修改为XOR，以查找0以外的字节。在运行Mac OS X 10.6 (x86_64)的2.66GHz Core 2笔记本电脑上执行的基准测试:
  • 843.433 MB/s strchr
  • 2656.742 MB/s findFirstByte64
  • 13094.479 MB/s strlen
  李< / ul > < / >

  ．.． 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在评论中指出，这个解决方案有一个“不可克服的错误”:

  它可以读取超出所寻找的字节或空结束符的内容，这些结束符可以访问未映射的页或没有读权限的页。在字符串函数中不能使用大读取，除非它们对齐。

  这在技术上是正确的，但实际上适用于任何操作大于单个字节的块的算法，包括注释中OP建议的该方法:

  典型的strchr实现并不幼稚，但比你给出的要有效得多。关于最广泛使用的算法:http://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord，请参阅本文末尾

  它本身也与对齐无关。的确，这可能会导致在使用中的大多数常见架构上讨论的行为，但这更多地与微架构实现细节有关——如果未对齐的读取跨越了4K边界(同样是典型的)，那么如果下一个4K页面边界未映射，那么该读取将导致程序终止错误。

  但这并不是答案中给出的算法中的“bug”——这种行为是因为像strchr和strlen这样的函数不接受length参数来限制搜索的大小。搜索char bytes[1] = {0x55};，为了我们讨论的目的，它恰好被放置在4K VM页面边界的最末端，而下一页是未映射的，使用strchr(bytes, 0xAA)(其中strchr是一个字节-一次的实现)将以完全相同的方式崩溃。与strchr相关的表兄strlen也是如此。

  如果没有length参数，就没有办法告诉你什么时候应该切换出高速算法，回到逐字节算法。更可能的“错误”是读取“超过分配的大小”，根据各种C语言标准，从技术上讲，这将导致undefined behavior，并将被valgrind之类的东西标记为错误。

  总之，如果没有length参数来控制“最后一次读取”的大小写，那么任何操作比字节块更大以运行得更快的代码，就像这个回答代码和OP指出的代码所做的那样，但必须具有字节精确的读取语义，则很可能是“bug”。

  这个答案中的代码是一个内核，如果目标CPU有一个快速的ctz类指令，则能够快速找到一个自然CPU字大小块中的第一个字节。添加一些事情是很简单的，比如确保它只在正确对齐的自然边界上运行，或者某种形式的length边界，这将允许你切换出高速内核，进入一个较慢的字节逐个字节检查。

  OP还在评论中写道:

  至于ctz优化，它只对O(1)尾部操作有影响。它可以提高小字符串的性能(例如strchr("abc", 'a');，但肯定不能提高任何大字符串的性能。

  这种说法是否正确在很大程度上取决于所讨论的微架构。使用标准的4阶段RISC管道模型，那么它几乎肯定是正确的。但是，对于当代无序的超级标量CPU来说，很难判断这是否正确，因为核心速度完全超过了内存流速度。在这种情况下，相对于“可流的字节数”，“可退役的指令数”存在很大的差距，这样就有了“每个可流的字节对应可退役的指令数”，这不仅是合理的，而且是相当常见的。如果这个值足够大，ctz + shift指令可以“免费”执行。

我知道这是一个老问题，但大多数糟糕的移位表都是单字符的。如果它对你的数据集有意义(例如，特别是如果它是书面文字)，并且如果你有可用的空间，你可以通过使用一个由n-grams而不是单个字符组成的糟糕的移位表来获得显著的加速。

我很惊讶在这次讨论中看到我们的技术报告被引用;我是上面那个叫做Sustik-Moore的算法的作者之一。(我们在论文中没有使用这个术语。)

在这里我想强调的是，对我来说，这个算法最有趣的特点是，它很简单，可以证明每个字母最多检查一次。在早期的Boyer-Moore版本中，他们证明了每个字母最多被检查3次，后来最多被检查2次，这些证明更加复杂(参见论文中的引用)。因此，我也看到了展示/研究这种变体的教学价值。

在论文中，我们还描述了进一步的变化，旨在提高效率，同时放松理论保证。这是一篇简短的论文，在我看来，对于一个普通的高中毕业生来说，材料应该是可以理解的。

我们的主要目标是让其他可以进一步改进它的人注意到这个版本。字符串搜索有如此多的变化，我们自己不可能想到所有这个想法可以带来的好处。(固定文本和变化模式，固定模式不同文本，预处理可能/不可能，并行执行，在大文本中查找匹配子集，允许错误，接近匹配等，等等)

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

在我看来，你对自己施加了太多的限制(是的，我们都想在最大搜索器上实现次线性线性)，然而，它需要一个真正的程序员介入，在此之前，我认为哈希方法只是一个漂亮的边界解决方案(BNDM很好地加强了2..16模式)。

举个简单的例子:

正在将模式(32字节)搜索到字符串(206908949字节)作为一行… 跳过性能(越大越好):3041%，6801754次跳过/迭代 Railgun_Quadruplet_7Hasherezade_hits / Railgun_Quadruplet_7Hasherezade_clocks: 0/58 Railgun_Quadruplet_7Hasherezade性能:3483 kb/clock

正在将模式(32字节)搜索到字符串(206908949字节)作为一行… 跳过性能(越大越好):1554%，13307181次跳过/迭代 Boyer_Moore_Flensburg_hits / Boyer_Moore_Flensburg_clocks: 0/83 Boyer_Moore_Flensburg performance: 2434 kb/clock

正在将模式(32字节)搜索到字符串(206908949字节)作为一行… 跳过性能(越大越好):129%，160239051跳过/迭代 Two-Way_hits / Two-Way_clocks: 0/816 双向性能:247 kb/clock

你在问题中提到的双向算法(顺便说一下，这是不可思议的!)最近已得到改进，一次有效地处理多字节单词:最优填充字符串匹配。

我还没有阅读整篇论文，但似乎他们依赖于一些新的、特殊的CPU指令(包括在例如SSE 4.2中)为O(1)的时间复杂度声明，尽管如果它们不可用，他们可以在O(log log w)时间内模拟w-bit的单词，这听起来不太糟糕。

你可以实现，比如说，4种不同的算法。每M分钟(由经验决定)在当前真实数据上运行所有4个。累积N次运行的统计信息(也待定)。然后在接下来的M分钟里只使用获胜者。

记录胜利的统计数据，这样你就可以用新的算法替换从未赢过的算法。将优化工作集中在最成功的例程上。要特别注意对硬件、数据库或数据源进行任何更改之后的统计数据。如果可能的话，将这些信息包含在统计日志中，这样你就不必从日志日期/时间戳中计算出来。

发表于2011年，我相信它很可能是Dany Breslauer, Roberto Grossi和Filippo Mignosi的"简单实时常量空间字符串匹配"算法。

更新:

2014年，作者发布了这一改进:朝向最优的填充字符串匹配。

最快的子字符串搜索算法依赖于上下文:

1. 字母大小(例如DNA vs英语)
2. 针长

2010年的论文精确的字符串匹配问题:一个综合的实验评价给出了51种算法的运行时表(不同的字母大小和针长度)，所以你可以根据你的上下文选择最好的算法。

所有这些算法都有C实现，以及一个测试套件，在这里:

< a href = " http://www.dmi.unict.it/法/聪明/ algorithms.php”> http://www.dmi.unict.it/法/聪明/ algorithms.php < / >

“精确填充字符串匹配”;为SIMD SSE4.2优化(x86_64和aarch64)。它在所有尺寸上都表现稳定和最佳。

我链接到的网站比较了199种快速字符串搜索算法，而常用的(BM、KMP、BMH)非常慢。EPSM在这些平台上的性能优于本文提到的所有其他平台。这也是最新的。

2020年更新:EPSM最近针对AVX进行了优化，仍然是最快的。