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

Question

我希望能够在Java中使用一种高效的算法（或库）来搜索字符串中的子串。

我想要做的是：

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

"BCDEFGH"

和一组候选字符串-CAND:

"AB"，"CDE"，"FG"，"H"，"IJ"

找到任何与INSTR匹配的CAND字符串。

在这个例子中，我会匹配"CDE"、"FG"和"H"（但不是"AB"和"IJ"）。

可能有许多千个候选字符串（在CAND中），但更重要的是，我将进行这种搜索很多次，因此需要快速解决问题。

我想使用char数组。此外，我对架构解决方案（如分布式搜索）不感兴趣，只需要在本地执行最有效的函数/算法。

此外，所有CAND和INSTR中的字符串都相对较小（＜50字符）-即目标字符串INSTR与候选字符串相比并不长。

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

更新：我只需要知道是否存在匹配，而不需要知道匹配是什么。

最后更新：我选择尝试AhoCorsick和Rabin-Karp，因为它们易于实现。 由于我有可变长度的模式，我使用了修改过的Rabin-Karp算法来哈希每个模式的前n个字符，其中n是最小模式的长度，N是我的滚动子字符串搜索窗口的长度。 对于Aho Corsick，我使用了这个。

在我的测试中，我在两篇报纸文章中搜索了1000个模式，并在1000次迭代中计算出平均完成时间等...

标准化的完成时间如下：

AhoCorsick: 1

RabinKarp: 1.8

Naive Search（检查每个模式并使用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*

- Joel

---

输入字符串与候选字符串的长度如何？ - Thomas Jung

它们很短。输入字符串通常少于40个字符，候选字符串也是如此。 - Joel

但是可能有成千上万个候选字符串 - 而我想在数百万次的多个输入字符串中重复执行此操作。 - Joel

鉴于细节，有限状态机可能是您最好的选择。 - Daniel Brückner

好奇你期望的输出是什么。只知道找到了一个是否足够，还是需要知道找到了哪些？你需要知道每个子字符串被找到的次数吗？ - PSpeed

是的，一个匹配就足够了 - 只需要一个简单的真/假值，不需要其他信息。 - Joel

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

- Daniel Brückner

---

可以在http://stringsearchalgorithms.amygdalum.net/上找到包含Aho-Corasick在内的多种算法的集合。 - CoronA

Answer 2

将候选字符串集转换为确定性有限状态自动机，然后以线性时间运行输入字符串。将单个字符串转换为DFS在标准书籍中已经有很好的覆盖。您可以通过首先构建非确定性自动机，然后确定它来转换一组字符串。这可能会在自动机的大小最坏情况下导致指数级增长，但搜索之后很快；特别是如果目标字符串很长而候选字符串很短，那么这种方法就很有效。

- Antti Huima

---

考虑到输入字符串和候选字符串都非常短，例如<50个字符，因此这个解决方案是否相关？ - Joel

@Joel 我认为这取决于你在上面写的“我想在许多输入字符串中重复执行此操作”的含义。DFS 不依赖于输入字符串，因此，如果候选字符串集在多个输入字符串之间保持不变，则相当于一个长输入字符串，因此解决方案肯定是相关的。如果所有字符串都很短且候选项每次都会更改，则可能不是最佳解决方案。 - Antti Huima

这与上面建议的 Rabin-Karp 多模式搜索算法相比如何？鉴于可能的子字符串数量很大，而输入字符串长度相对较短，这似乎是一个不错的解决方案？ - Joel

@Joel Rabin-Karp 绝对是另一个好的解决方案，它只是有不同的渐进行为。深度优先搜索（DFS）解决方案在匹配方面具有最佳的渐进复杂度，因为它仅在输入字符串的长度为O(n)。Rabin-Karp 在复杂性中有额外的项。然而，从零开始实现更简单。 - Antti Huima

请提供一本书的链接或名称，其中描述如何将单个字符串转换为DFS。我找不到它... - Tebe

将字符串转换为有限状态机是可行的，但在字符串搜索的专家中会指出有几种方法可以做到这一点。Knuth-Morris-Pratt（单个模式搜索）或Aho-Corasick（多模式搜索）都基于确定性有限自动机。Shift-And则基于非确定性有限自动机（如果与位并行一起使用也很有效）。因此，这个答案严格上是被接受的答案的复制。 - CoronA

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应该转义在正则表达式中具有特殊含义的任何字符。

- Jørgen Fogh

---

我并不声称我的解决方案是完美的。但它可能是足够的。你的经验可能会有所不同。 - Jørgen Fogh

正则表达式执行像"a|b|c|d"这样的模式的方式是从位置0开始，尝试所有选项，移动到位置1，尝试所有选项，移动到位置2，尝试所有选项等等。没有大型正则表达式OR的更快的方法应该很容易编写。搜索所有INSTR中的CAND1，然后搜索CAND2等永远不会更糟，并且通常会更好。此外，这种搜索方式要容易优化得多。 - PSpeed

虽然这很困难。您可以查看Java的正则表达式代码。问题在于OR节点不知道“a”、“b”、“c”等节点在做什么。此外，您隐含地提出了错误的问题，因为“a|b|c|d”是要求其中一个的第一个匹配...这意味着您至少必须搜索所有这些内容，然后才能知道（除非您首先找到第一个字符）。发帖者想知道是否有任何匹配，并且与正则表达式相比，单独测试“a”、“b”、“c”等更快。它总是会的。 - PSpeed

@Jørgen，就我所知，当我们的正则表达式大师在一段时间前向我解释这个问题时，我也有完全相同的反应。 :) - PSpeed

Java的正则表达式可能实现得非常糟糕；我不太熟悉它。但是除此之外，正则表达式应该提供最优解决方案。编译后的正则表达式应该随着模式长度线性增长（带有任何运气的子线性），肯定不是指数级别的，并且搜索时间是线性的。 - R.. GitHub STOP HELPING ICE

Answer 4

Rabin-Karp多模式搜索算法似乎是最快的。

- emptyset

Answer 5

你可能需要了解Aho-Corasick算法及相关算法。我不知道有没有直接实现这个算法的库，但这是解决这个问题的经典方法。请参考Aho-Corasick algorithm。

- Avi

---

感谢您。Java实现在这里：http://hkn.eecs.berkeley.edu/~dyoo/java/index.html - Joel

Answer 6

还要检查Boyer-Moore算法，用于单字符串模式匹配。

- spoulson

Answer 7

我们可以利用字符串长度较小 (<50 char) 的优势来构建一个超级快速的算法，以此来解决这个问题，但需要付出一定的内存代价。

我们可以将 INSTR 的所有可能子串哈希到一个哈希表中，这个过程只需要 O(n^2) 的时间。然后无论 CAND 字符串的数量如何，查找都只需要 O(1) 的时间。这对于大量的 CAND 字符串是值得的。

如果 INSTR 很长，那么我们可以构建一个后缀数组，并不进行排序，使得顶部项为最长 (=N)，底部项为 INSTR 的最后一个字符。现在对于每个 CAND 字符串，只需要从顶部开始搜索，只要 length(CAND) <= length(suffix)。这些比较的时间复杂度都是 O(n)。

- Joy Dutta

---

我对此还有点模糊，可能会跑题，但哈希时间应该是O（n+1）（n/2），而不是O（n^2），因为应该有这么多不同的子字符串。 - Chris Dutrow

Big-O忽略系数。将表达式中的1和2去掉，剩下的是O((n)(n))，这与O(n^2)相同。 - Tripp Kinetics

Answer 8

import java.util.Scanner;

public class StringMatch 
{
    static int temp,i=0,j=0; static boolean flag=true,matcher=false;

    static String str=null,mstr=null;static char astr[],amstr[];

    static void getter(){
        Scanner sc = new Scanner(System.in);
        str = sc.nextLine();
        //String str="today is Monday"; 
        astr=str.toCharArray();
         mstr = sc.nextLine();
        //String mstr="is"; 
         amstr=mstr.toCharArray();
    }

    static void stringMatch(){
        while(i<astr.length){
            if(astr[i]==amstr[j]){
            while((j!=amstr.length)&&flag){temp=i;
                if(astr[i]!=amstr[j]) {flag=false;matcher=false;}
                else{matcher=true;}
                i++;j++;
                //System.out.println(i+"\t"+j);
            }if(matcher==true)break;i=temp;}i++;j=0;flag=true;

        }
        if(matcher==true) {System.out.println("true");}
        else    {System.out.println("false");}
    }

    public static void main(String[] args) {

    StringMatch.getter();
    StringMatch.stringMatch();

    }
}

- Deepak Kumar

Answer 9

另一种解决方案是使用后缀数组来进行INSTR的操作。
由于INSTR很小，您可以使用冒泡排序对其进行排序。

之后，您可以在O(logN)时间内搜索特定的CAND字符串，
其中N = length(suffix_array) = length(INSTR)。

- Nick Dandoulakis

Answer 10

这里有一些Java中快速字符串搜索算法的实现。

- netcyrax

---

你在哪里？你忘记复制粘贴链接了吗？ - Tushar

如果您点击“这里”文本，您将被重定向到带有算法的网站。 - netcyrax