用于在字符串中搜索子串的快速算法

Question

我想要一个有效的算法(或库),我可以在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*

Answer 1

阅读Aho-Corasick算法和Rabin-Karp算法.

如果输入不是太大,您不想多次重复搜索并且没有很多模式,那么多次使用单个模式算法可能是个好主意.该搜索算法维基百科的文章给出了运行和预处理时间很多算法.

实现:

• https://hkn.eecs.berkeley.edu/~dyoo/java/index.html
• http://algs4.cs.princeton.edu/53substring/RabinKarp.java.html
• https://github.com/hankcs/AhoCorasickDoubleArrayTrie
• https://github.com/RokLenarcic/AhoCorasick
• https://github.com/robert-bor/aho-corasick

介绍:

• http://www.slideshare.net/taka111/ahocorasick-string-matching-algorithm-15078438

Answer 2

将候选字符串集转换为确定性有限状态自动机,然后以线性时间运行输入字符串.标准书籍中详细介绍了将单个字符串转换为DFS.您可以通过首先构造一个非确定性自动机然后确定它来转换一组字符串.这可能会在自动机大小的最坏情况下产生指数性爆炸,但之后的搜索速度很快; 特别是如果目标字符串很长并且候选字符短,那将会很好.

Answer 3

这就是正则表达式的用途.如上所述,有限状态自动机是您所需要的,但这正是标准正则表达式匹配器的实现方式.

在java中,您可以编写如下内容:

StringBuilder sb = new StringBuilder();
bool first = true;
for (String subStr : substrings) {
    if (first)
        first = false;
    else
        sb.append('|');
    sb.append(escape(subStr));
}
Pattern p = Pattern.compile(sb.toString());

该方法escape应该在正则表达式中转义任何具有特殊含义的字符.