首页 文章

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

提问于
浏览 次
139

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

  • Needle（模式）和haystack（要搜索的文本）都是C风格的以空字符结尾的字符串 . 没有提供长度信息;如果需要，必须计算 .

  • 函数应返回指向第一个匹配的指针，如果未找到匹配则返回 NULL .

  • Failure cases are not allowed. This means any algorithm with non-constant (or large constant) storage requirements will need to have a fallback case for allocation failure (and performance in the fallback care thereby contributes to worst-case performance).

  • 实现是在C中，虽然没有代码的算法（或链接到这样的）的良好描述也很好 .

......以及“最快”的意思：

  • 确定性 O(n) 其中 n = haystack长度 . （但是如果它们与更强大的算法组合以给出确定性的结果，则可以使用通常为 O(nm) （例如滚动哈希）的算法的想法 .

  • 从不执行（可测量;几个时钟为 if (!needle[1]) 等等）比天真蛮力算法更差，特别是在非常短的针上，这可能是最常见的情况 . （无条件的重预处理开销是不好的，因为试图以可能的针头为代价来改善病理针的线性系数 . ）

  • 给定任意针和干草堆，与任何其他广泛实施的算法相比，具有相当或更好的性能（不低于搜索时间长50％） .

  • 除了这些条件，我建议"fastest" .

我目前的实现比glibc的双向实现大约慢10％和8倍（取决于输入） .

Update: My current optimal algorithm is as follows:

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

  • 对于长度为2-4的针，使用机器字一次比较2-4个字节，如下所示：使用16位或32位整数预加载针，并从每个干草堆中循环移位旧字节输出/新字节迭代 . 大海捞针的每个字节只读取一次，并对0（字符串结束）和一个16位或32位比较进行检查 .

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

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

  • 有没有办法更好地利用坏移位表？ Boyer-Moore通过向后扫描（从右向左）充分利用它，但是双向扫描需要从左向右扫描 .

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

奖励积分：

  • 假设针和干草堆都是结构良好的UTF-8，你能提高性能吗？ （对于具有不同字节长度的字符，良好的形式在针和haystack之间强加了一些字符串对齐要求，并且当遇到不匹配的头字节时允许自动2-4字节移位 . 但这些约束是否会超出你的范围最大后缀计算，良好的后缀转换等已经为您提供了各种算法？）

Note: 我'm well aware of most of the algorithms out there, just not how well they perform in practice. Here'是一个很好的参考，所以人们不会继续给我作为评论/答案的算法参考：http://www-igm.univ-mlv.fr/~lecroq/string/index.html

c algorithm string substring

16 回答

  • 3

    最快的子字符串搜索算法将取决于上下文：

    • 字母大小（例如DNA与英文）

    • 针长

    2010年的论文"The Exact String Matching Problem: a Comprehensive Experimental Evaluation"给出了51个算法（具有不同的字母大小和针长）的运行时表，因此您可以为您的上下文选择最佳算法 .

    所有这些算法都有C实现，以及测试套件，这里：

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

    回复于
  • 4

    您可能还希望对多种类型的字符串使用不同的基准测试，因为这可能会对性能产生很大影响 . algos将基于搜索自然语言（甚至在这里因为不同的形态学仍然可能存在细微的区别），DNA字符串或随机字符串等来执行差异 .

    字母大小将在许多算法中起作用，针大小也将如此 . 例如，Horspool在英文文本方面表现不错，但由于字母大小不同而在DNA上表现不佳，这使得糟糕的角色规则变得艰难 . 引入良好后缀大大加强了这一点 .

    回复于
  • 23

    一种更快的"Search for a single matching character"（ala strchr ）算法 .

    Important notes:

    • 这些函数使用"number / count of (leading|trailing) zeros" gcc 编译器内在_ __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 for strchr

    • 2656.742 MB / s for findFirstByte64

    • 13094.479 MB / s for strlen

    ...一个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));
}

    Edit 2011/06/04 OP在评论中指出此解决方案具有"insurmountable bug"：

    它可以读取搜索到的字节或空终止符，它可以在没有读取权限的情况下访问未映射的页面或页面 . 你不能在字符串函数中使用大型读取，除非它们是对齐的 .

    这在技术上是正确的，但几乎适用于任何在大于单个字节的块上运行的算法，包括评论中OP建议的the method：

    典型的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 参数，就无法确定何时应该切换出高速算法并返回逐字节算法 . 更有可能"bug"将读取"past the size of the allocation"，根据各种C语言标准技术上会产生 undefined behavior ，并且会被 valgrind 标记为错误 .

    总之，任何操作大于字节块的东西都会更快，因为这会回答代码所做的和OP指出的代码，但必须具有字节精确的读取语义，如果没有 length 参数可以控制"buggy" "the last read"的角落案例 .

    本答案中的代码是一个内核，用于在目标CPU具有快速 ctz 类指令时能够快速查找自然CPU字大小块中的第一个字节 . 添加诸如确保它仅在正确对齐的自然边界上运行或者某种形式的 length 绑定这样的事情是微不足道的，这将允许您切换出高速内核并进入较慢的逐字节检查 .

    OP还在评论中指出：

    至于你的ctz优化，它只会对O（1）尾部操作产生影响 . 它可以通过微小的字符串来提高性能（例如strchr（“abc”，“a”）;但肯定不会使用任何主要大小的字符串 .

    这个陈述是否真实取决于所讨论的微架构 . 使用规范的4阶段RISC管道模型，几乎可以肯定 . 但是很难说现在的乱序超级标量CPU是否属实，其中核心速度可以使内存流速度完全相形见绌 . 在这种情况下，相对于"the number of bytes that can be streamed"，"the number of instructions that can be retired"中存在较大的差距，这不仅是合理的，而是相当普遍的，因此您有"the number of instructions that can be retired for each byte that can be streamed" . 如果这足够大， ctz 移位指令可以完成"for free" .

    回复于
  • 2

    这是Python's search implementation，用于整个核心 . 评论表明它使用压缩的boyer-moore delta 1表 .

    我自己进行了一些非常广泛的字符串搜索实验，但它适用于多个搜索字符串 . 对于低模式计数，Horspool和Bitap的汇编实现通常可以针对像Aho-Corasick这样的算法保持自己的实现 .

    回复于
  • 13

    我知道这是一个老问题，但大多数糟糕的班次表都是单一字符 . 如果它对您的数据集有意义（例如，特别是如果它是书面文字），并且如果您有可用空间，则可以通过使用由n-gram而不是单个字符组成的错误移位表来获得显着的加速 .

    回复于
  • 18

    您在问题中提到的双向算法（顺便说一句，令人难以置信！）最近得到了改进，可以一次有效地处理多字节单词：Optimal Packed String Matching .

    我没有阅读整篇论文，但似乎他们依赖于一些新的，特殊的CPU指令（包括在例如SSE 4.2中）作为时间复杂性声明的O（1），尽管如果它们不可用它们可以在O（log log w）时间内模拟它们对于听起来不太糟糕的w位词 .

    回复于
  • 2

    我绝对不是最好的，但我对Boyer-Moore有很好的经验 .

    回复于
  • 3

    您指向的http://www-igm.univ-mlv.fr/~lecroq/string/index.html链接是一些最知名和研究的字符串匹配算法的绝佳来源和摘要 .

    大多数搜索问题的解决方案涉及预处理开销，时间方面的权衡和空间要求 . 在所有情况下，没有一种算法是最佳的或实用的 .

    如果您的目标是为字符串搜索设计一个特定的算法，那么忽略我要说的其余部分，如果您想开发一个通用的字符串搜索服务例程，请尝试以下方法：

    花一些时间来回顾一下您已经引用的算法的特定优点和缺点 . 进行审查的目的是找到一组算法，涵盖您感兴趣的字符串搜索的范围和范围 . 然后，基于分类器函数构建前端搜索选择器，以针对给定输入定位最佳算法 . 这样，您可以使用最有效的算法来完成工作 . 当算法对于某些搜索非常好但是降级很差时，这尤其有效 . 例如，对于长度为1的针，蛮力可能是最佳的，但随着针长度的增加而迅速降低，因此sustik-moore algoritim可能变得更有效（超过小字母），然后对于更长的针和更大的字母，KMP或Boyer-Moore算法可能更好 . 这些只是举例说明可能的策略 .

    多算法方法不是一个新想法 . 我相信它已被一些商业排序/搜索包使用（例如，大型机上常用的SYNCSORT实现了几种排序算法，并使用启发式方法为给定输入选择“最佳”）

    每种搜索算法都有多种变体，可以对其性能产生显着差异，例如，这可以说明这一点 .

    对您的服务进行基准测试，以对需要其他搜索策略的区域进行分类，或者更有效地调整您的选择器功能 . 这种方法不是快速或简单的，但如果做得好可以产生非常好的结果 .

    回复于
  • 3

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

    您可能会发现它很有用 . 另外，如果我必须快速调用子串搜索算法，我会选择Knuth-Morris-Pratt .

    回复于
  • 0

    Build 一个可能针和干草堆的测试库 . 在几种搜索算法上描述测试，包括暴力 . 选择最适合您的数据的那个 .

    Boyer-Moore使用带有良好后缀表的错误字符表 .

    Boyer-Moore-Horspool使用错误的字符表 .

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

    Rabin-Karp使用运行哈希值 .

    它们都是交易开销，以减少不同程度的比较，因此现实世界的表现将取决于针和干草堆的平均长度 . 初始开销越多，输入越长越好 . 如果针很短，可能会获得蛮力 .

    编辑：

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

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

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

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

    如果我需要一个样本集，我想我会刮掉像谷歌或维基百科的网站，然后从所有结果页面中删除html . 对于搜索网站，键入单词然后使用建议的搜索短语之一 . 如果适用，请选择几种不同的语言 . 使用网页，所有文本都是短到中等，因此合并足够的页面以获得更长的文本 . 您还可以查找公共领域书籍，法律记录和其他大型文本 . 或者只是通过从字典中挑选单词来生成随机内容 . 但分析的要点是测试根据您要搜索的内容类型，如果可能，请使用真实世界的示例 .

    我留下了短暂而长久的模糊 . 对于针头，我认为短小于8个字符，中等小于64个字符，长度低于1k . 对于大海捞针，我认为短于2 ^ 10，中等到2 ^ 20，长到2 ^ 30个字符 .

    回复于
  • 33

    我很惊讶地看到本次讨论中引用的技术报告;我是上面名为Sustik-Moore的算法的作者之一 . （我们在论文中没有使用该术语 . ）

    我想在此强调一点，对我而言，该算法最有趣的特点是证明每个字母最多被检查一次非常简单 . 对于早期的Boyer-Moore版本，他们证明每个字母最多检查3次，最多检查2次，并且这些证据更多涉及（参见纸上的引用） . 因此，我也看到了呈现/研究这种变体的教学 Value .

    在本文中，我们还描述了在放松理论保证的同时针对效率的进一步变化 . 这是一篇简短的论文，我认为这对普通高中毕业生来说应该是可以理解的 .

    我们的主要目标是将此版本引入其他可以进一步改进的版本 . 字符串搜索有很多变化，我们无法想象这个想法可以带来什么好处 . （固定文本和更改模式，固定模式不同文本，预处理可能/不可能，并行执行，在大文本中查找匹配子集，允许错误，接近匹配等等）

    回复于
  • 3

    例如，您可以实现4种不同的算法 . 每M分钟（根据经验确定）在当前实际数据上运行全部4 . 累计N次运行（也是TBD）的统计数据 . 然后在接下来的M分钟内仅使用获胜者 .

    在Wins上记录统计数据，以便您可以替换从未赢得新算法的算法 . 专注于winningest例程的优化工作 . 在对硬件，数据库或数据源进行任何更改后，请特别注意统计信息 . 如果可能，请在统计日志中包含该信息，这样您就不必从日志日期/时间戳中找出它 .

    回复于
  • 22

    使用stdlib strstr ：

    char *foundit = strstr(haystack, needle);

    这是非常快，只花了我约5秒钟打字 .

    回复于
  • 3

    一个非常好的问题 . 只需添加一些小块......

    • 有人在谈论DNA序列匹配 . 但是对于DNA序列，我们通常做的是为大海捞针 Build 一个数据结构（例如后缀数组，后缀树或FM索引）并匹配许多针对它 . 这是一个不同的问题 .

    • 如果有人想要对各种算法进行基准测试，真的很棒 . 压缩和后缀数组的构建有很好的基准，但我还没有看到字符串匹配的基准 . 潜在的干草堆候选人可能来自SACA benchmark .

    • 前几天我在the page you recommended测试Boyer-Moore实现（编辑：我需要像memmem（）这样的函数调用，但它不是标准函数，所以我决定实现它） . 我的基准测试程序使用随机干草堆 . 似乎该页面中的Boyer-Moore实现比glibc 's memmem() and Mac' s strnstr（）快一倍 . 如果您感兴趣，实现是here，基准代码是here . 这绝对不是一个现实的基准，但它是一个开始 .

    回复于
  • 4

    只需搜索“最快的strstr”，如果你看到有趣的东西就问我 .

    在我看来，你对自己施加了太多的限制（是的，我们都希望在最大搜索者处使用次线性线性），但是需要一个真正的程序员介入，直到那时我认为哈希方法只是一个漂亮的解决方案（由BNDM为更短的2..16模式加强 .

    Just a quick example:

    搜索模式（32字节）到字符串（206908949bytes）作为一行...跳过性能（越大越好）：3041％，6801754跳过/迭代Railgun_Quadruplet_7Hasherezade_hits / Railgun_Quadruplet_7Hasherezade_clocks：0/58 Railgun_Quadruplet_7Hasherezade 性能： 3483KB /时钟

    搜索模式（32字节）到字符串（206908949bytes）作为一行...跳过性能（越大越好）：1554％，13307181跳过/迭代Boyer_Moore_Flensburg_hits / Boyer_Moore_Flensburg_clocks：0/83 Boyer_Moore_Flensburg 性能： 2434KB /时钟

    搜索模式（32字节）到字符串（206908949bytes）作为一行...跳过性能（越大越好）：129％，160239051跳过/迭代双向导航/双向导线：0/816 Two-Way 表现： 247KB /时钟

    Sanmayce，
    问候

    回复于
  • 3

    发布于2011年，我相信很可能是Dany Breslauer，Roberto Grossi和Filippo Mignosi编写的"Simple Real-Time Constant-Space String Matching"算法 .

    更新：

    2014年，作者发表了这一改进：Towards optimal packed string matching .

    回复于

相关问题