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

 

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

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

    • ......以及“我最快”的意思是：

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

    • 我目前的实现比glibc的双向实现运行速度大约慢10％和8倍（取决于输入）。

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

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

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

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

    • 奖励积分为：

  • 假设针和干草堆都是格式良好的UTF-8，你可以提高性能吗？ （使用不同字节长度的字符时，良好的格式会在针头和干草堆之间强加一些字符串对齐要求，并且在遇到不匹配的头字节时允许自动2-4字节的移位，但是这些限制会为您带来甚么价值最大后缀计算，好的后缀移位等已经给你提供了各种算法？）

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

    建立一个可能的针和干草堆的测试库。 在几种搜索算法上对测试进行剖析，包括蛮力。 选择一个性能最好的数据。

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

    Boyer-Moore-Horspool使用糟糕的角色表。

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

    Rabin-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链接是一些很好的资源，并总结了一些最为人所知和研究的字符串匹配算法。

    大多数搜索问题的解决方案涉及预处理开销，时间和空间需求方面的权衡。 在任何情况下，单一算法都不是最佳的或实用的。

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

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

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

    每种搜索算法都有多种变化，可以在性能上产生显着差异，例如本文所述。

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

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

    更新：

    2014年，作者发表了这一改进：迈向最佳包装字符串匹配。

    链接地址: http://www.djcxy.com/p/14885.html

    上一篇: What is the fastest substring search algorithm?

    下一篇: Algorithm to return all combinations of k elements from n