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

Question

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

• 针(模式)和haystack(要搜索的文本)都是C样式的以空字符结尾的字符串.没有提供长度信息; 如果需要,必须计算.
• 函数应该返回指向第一个匹配的指针,或者NULL如果找不到匹配项.
• 不允许发生失败案件.这意味着任何具有非常量(或大常量)存储要求的算法都需要具有分配失败的后备情况(并且后备保养中的性能因此导致最坏情况的性能).
• 实现是在C中,虽然没有代码的算法(或链接到这样的)的良好描述也很好.

......以及"最快"的意思:

• 确定性O(n)where n= haystack长度.(但是O(nm)如果它们与更强大的算法组合以给出确定性O(n)结果,则可以使用通常(例如滚动哈希)算法的思想.
• 从不执行(可测量;一些时钟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,你能提高性能吗？(对于字节长度不同的字符,良好的形式在针和haystack之间强加了一些字符串对齐要求,并且当遇到不匹配的头字节时允许自动2-4字节移位.但这些约束是否会超出你的范围最大后缀计算,良好的后缀转换等已经为您提供了各种算法？)

注意:我很清楚那里的大多数算法,而不是它们在实践中的表现.这是一个很好的参考,所以人们不会继续给我作为评论/答案的算法参考:http://www-igm.univ-mlv.fr/~lecroq/string/index.html

Answer 1

建立一个可能针和干草堆的测试库.在几种搜索算法上描述测试,包括暴力.选择对您的数据表现最佳的那个.

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

Boyer-Moore-Horspool使用了一个糟糕的角色表.

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

拉宾卡普使用奔跑的哈希.

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

编辑:

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

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

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

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

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

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

Answer 2

发布于2011年,我相信很可能是Dany Breslauer,Roberto Grossi和Filippo Mignosi 的"简单实时恒定空间字符串匹配"算法.

更新:

2014年,作者发表了这一改进:迈向最佳打包字符串匹配.

Answer 3

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

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

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

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

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

每种搜索算法都有多种变体,可以对其性能产生重大影响,例如,本文说明了这一点.

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

Answer 4

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

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

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

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

Answer 5

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

1. 字母大小(例如DNA与英文)
2. 针长

2010年论文"精确字符串匹配问题:综合实验评估"给出了51个算法(具有不同字母大小和针长度)的运行时表,因此您可以为您的上下文选择最佳算法.

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

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

Answer 6

我不知道这是否绝对是最好的，但我在Boyer-Moore方面有过很好的经验。