相关疑难解决方法(0)

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

• 针(模式)和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

我想要一个有效的算法(或库),我可以在Java中使用它来搜索字符串中的子串.

我想做的是:

给定一个输入字符串 - INSTR:

"BCDEFGH"

还有一组候选字符串--CAND:

"AB","CDE","FG","H","IJ"

在INSTR中查找匹配为子字符串的任何CAND字符串

在这个例子中,我将匹配"CDE","FG"和"H"(但不是"AB"和"IJ")

可能有数千个候选字符串(在CAND中),但更重要的是,我将进行数百万次搜索,因此我需要它快速.

我想使用char数组.此外,我并不喜欢建筑解决方案,例如分发搜索 - 只是在本地进行搜索的最有效的功能/算法.

另外,CAND和INSTR中的所有字符串都将相对较小(<50个字符) - 即目标字符串INSTR相对于候选字符串不长.

我应该提到的更新,在所有INSTR值中,CAND字符串集是不变的.

更新我只需要知道有匹配 - 我不需要知道匹配是什么.

最终更新 由于实施简单,我选择尝试AhoCorsick和Rabin-Karp.因为我有可变长度模式,所以我使用了一个修改过的Rabin-Karp,它会散列每个模式的前n个字符,其中n是最小模式的长度,N则是我的滚动子字符串搜索窗口的长度.对于Aho Corsick,我用过这个

在我的测试中,我在两篇文档新闻论文中搜索了1000个模式,平均1000次迭代等...标准化时间完成:

AhoCorsick:1

拉宾卡尔普:1.8

天真搜索(检查每个模式并使用string.contains):50

*描述以下答案中提到的算法的一些资源:

http://www.seas.gwu.edu/~simhaweb/cs151/lectures/module5/module5.html

http://www.cs.princeton.edu/courses/archive/spr09/cos226/lectures/18SubstringSearch-2x2.pdf

http://www-igm.univ-mlv.fr/~lecroq/string/index.html*

几周前我向Stackoverflow提出了一个问题,即创建一个有效的算法来搜索大块文本中的模式.现在我使用String函数indexOf进行搜索.一个建议是使用Rabin-Karp作为替代方案.我按如下方式编写了一个小测试程序来测试Rabin-Karp的实现,如下所示.

public static void main(String[] args) {
    String test = "Mary had a little lamb whose fleece was white as snow";

    String p = "was";
     long start  = Calendar.getInstance().getTimeInMillis();
     for (int x = 0; x < 200000; x++)
         test.indexOf(p);
     long end = Calendar.getInstance().getTimeInMillis();
     end = end -start;
     System.out.println("Standard Java Time->"+end);

    RabinKarp searcher = new RabinKarp("was");
    start  = Calendar.getInstance().getTimeInMillis();
    for (int x = 0; x < 200000; x++)
    searcher.search(test);
    end = Calendar.getInstance().getTimeInMillis();
    end = end -start;
    System.out.println("Rabin Karp time->"+end);

}

以下是我正在使用的Rabin-Karp的实现: …