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

Question

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

我想做的是:

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

"BCDEFGH"

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

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

在 INSTR

中查找任何与子字符串匹配的 CAND 字符串

在本例中，我将匹配“CDE”、“FG”和“H”(但不匹配“AB”和“IJ”)

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

我想使用 char 数组。此外，我对架构解决方案没有兴趣，例如分发搜索 - 只是在本地执行它的最有效的功能/算法。

此外，CAND 和 INSTR 中的所有字符串都相对较小(< 50 个字符) - 即目标字符串 INSTR 相对于候选字符串而言并不长。

---

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

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

最终更新由于实现简单，我选择尝试 AhoCorsick 和 Rabin-Karp。因为我有可变长度模式，所以我使用了一个修改过的 Rabin-Karp，它对每个模式的前 n 个字符进行哈希处理，其中 n 是最小模式的长度，N 是我的滚动子字符串搜索窗口的长度。对于 Aho Corsick，我使用了 this

在我的测试中，我在两篇新闻报纸文章中搜索了 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 algorithm和 Rabin-Karp algorithm .

如果输入不是太大，您不想重复搜索很多次并且您没有很多模式，那么多次使用单个模式算法可能是个好主意。 Wikipedia article on search algorithms给出了许多具有运行和预处理时间的算法。

实现:

• 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