在Java中高效地搜索一组字符串的方法

Question

我有一个大小约为100-200的元素集合，其中样本元素为X。

每个元素都是一组字符串（这样的集合中的字符串数量在1到4之间）。X= {s1, s2, s3}

对于给定的输入字符串（约100个字符），比如P，我想测试是否存在任何一个X是“存在于”该字符串中。

当且仅当所有属于X的s都是P的子字符串时，X存在于P中。

元素集合可供预处理。

---

我希望在Java中尽可能快地实现此操作。不适用于我的要求的可能方法：

检查所有字符串s是否是P的子字符串似乎是一项昂贵的操作。

因为s可以是P的任何子字符串（不一定是单词），所以我不能使用单词散列

我不能直接使用正则表达式，因为s1、s2和s3可以按任意顺序出现，而且所有字符串都需要作为子字符串存在

---

目前我的方法是构造一个巨大的正则表达式，其中包含每个X的所有可能顺序的排列。由于X中的元素数量小于等于4，因此这仍然是可行的。如果有人能向我指出更好（更快/更优雅）的方法，那就太好了。

请注意，元素集合可供预处理，并且我需要在Java中解决该问题。

- BiGYaN

---

你是否预计这些集合中会有很多元素重复，还是它们应该大多数都是独特的？ - codebox

@codebox，不同的集合之间会有一些重复。也许一个字符串最多会在10个集合中出现。我能否从这个特性中获益？ - BiGYaN

Answer 1

您可以直接使用正则表达式：

Pattern regex = Pattern.compile(
    "^               # Anchor search to start of string\n" +
    "(?=.*s1)        # Check if string contains s1\n" +
    "(?=.*s2)        # Check if string contains s2\n" +
    "(?=.*s3)        # Check if string contains s3", 
    Pattern.DOTALL | Pattern.COMMENTS);
Matcher regexMatcher = regex.matcher(subjectString);
foundMatch = regexMatcher.find();

foundMatch为真，如果字符串中存在所有三个子字符串。

请注意，如果“needle strings”可能包含正则表达式元字符，则需要对其进行转义。

- Tim Pietzcker

---

谢谢您的建议。这将是我的初始方法。 - BiGYaN

这种方法对我的目的来说足够快。谢谢。 - BiGYaN

Answer 2

听起来你在实际发现某种方法太慢之前就过早地优化了你的代码。

你这一组字符串的好处是，字符串必须包含所有X元素作为子字符串--这意味着如果我们找到一个X元素不包含在P中，我们可以快速失败。这可能比其他方法更省时，特别是如果X元素通常长于几个字符且没有或仅有少量重复字符。例如，当检查非重复字符(如coast)长度为5的字符串的存在时，正则表达式引擎只需要检查100长度字符串中的20个字符。而且由于X有100-200个元素，所以如果可能的话，你真的想尽快失败。

我的建议是按长度对字符串进行排序，并依次检查每个字符串，如果找不到一个字符串，就提前停止检查。

- Dunes

---

谢谢您的建议。我将尝试使用@codebox提到的冗余因素来采用这种快速失败的方法。 - BiGYaN

Answer 3

看起来Rabin-Karp算法是一个完美的选择：

相比于Knuth-Morris-Pratt算法、Boyer-Moore字符串搜索算法以及其他更快的单模式字符串搜索算法，Rabin-Karp在单模式搜索方面表现较差，因为它的最坏情况行为较慢。然而，在多模式搜索中，Rabin-Karp是首选算法。

- Zar Shardan

Answer 4

当预处理时间不重要时，您可以创建一个哈希表，将至少在一个字符串中出现的每个单字母、双字母、三字母等组合映射到包含它的字符串列表。

索引字符串的算法如下（未经测试）：

HashMap<String, Set<String>> indexes = new HashMap<String, Set<String>>();

for (int pos = 0; pos < string.length(); pos++) {
    for (int sublen=0; sublen < string.length-pos; sublen++) {
         String substring = string.substr(pos, sublen);
         Set<String> stringsForThisKey = indexes.get(substring);
         if (stringsForThisKey == null) {
             stringsForThisKey = new HashSet<String>();
             indexes.put(substring, stringsForThisKey);
         }
         stringsForThisKey.add(string);
    }
}

用这种方式对每个字符串进行索引将会是与字符串长度的平方成正比，但每个字符串只需要进行一次索引。

但结果将会是以恒定速度访问包含特定字符串的字符串列表。

- Philipp

---

我认为 OP 所需要的预处理是在字符串集合（字典）X 上进行，而不是在输入字符串上进行。 - amit

Answer 5

一种方法是生成每个可能的子字符串并将其添加到集合中。这相当低效。

相反，您可以从任何点创建所有字符串到末尾，并将其放入一个NavigableSet中查找最接近的匹配项。如果最接近的匹配项以您要查找的字符串开头，则有一个子字符串匹配。

static class SubstringMatcher {
    final NavigableSet<String> set = new TreeSet<String>();

    SubstringMatcher(Set<String> strings) {
        for (String string : strings) {
            for (int i = 0; i < string.length(); i++)
                set.add(string.substring(i));
        }
        // remove duplicates.
        String last = "";
        for (String string : set.toArray(new String[set.size()])) {
            if (string.startsWith(last))
                set.remove(last);
            last = string;
        }
    }

    public boolean findIn(String s) {
        String s1 = set.ceiling(s);
        return s1 != null && s1.startsWith(s);
    }
}

public static void main(String... args) {
    Set<String> strings = new HashSet<String>();
    strings.add("hello");
    strings.add("there");
    strings.add("old");
    strings.add("world");
    SubstringMatcher sm = new SubstringMatcher(strings);
    System.out.println(sm.set);
    for (String s : "ell,he,ow,lol".split(","))
        System.out.println(s + ": " + sm.findIn(s));
}

打印

[d, ello, ere, hello, here, ld, llo, lo, old, orld, re, rld, there, world]
ell: true
he: true
ow: false
lol: false

- Peter Lawrey

---

谢谢您的建议。我还没有最终确定方法。如果没有其他的，我学到了NavigableSet。 - BiGYaN

Answer 6

你可能正在寻找Aho-Corasick算法，它可以从一组字符串（字典）构建出一个自动机（类似于trie），并尝试使用该自动机将输入字符串与字典进行匹配。

- amit

---

谢谢你的建议。我知道Aho-Corasick算法。我原以为正则表达式在内部会使用类似的算法。顺便问一下，你能推荐我一些相关的库吗？ - BiGYaN

@BiGYaN：据我所知，正则表达式并不使用这个算法。实际上，在Java中，至少有些情况下，正则表达式可能会衰减为指数运行时间。我不熟悉实现该算法的库，但维基页面在“外部链接”部分提到了这个实现。 - amit

如果我只使用正则表达式（可由有限自动机识别），那么像Thompson NFA或Aho-Corasick这样的算法应该是最快的实现...对吗？我曾经认为像Java这样广泛使用的语言应该已经实现了这些算法。然后我读到了http://swtch.com/~rsc/regexp/regexp1.html - BiGYaN

事实上，这些边缘情况非常罕见。然而，我相信使用Thompson或Aho-Corasick算法可能是解决您问题最有效的方法。 - amit

谢谢你的见解。现在我需要找到一个好的实现方式来使用它们中的任何一个。如果没有，那么我就必须自己编写代码了。:( - BiGYaN

Answer 7

你可能也想考虑使用“后缀树”。我没有使用过这段代码，但是这里有一个描述。

我曾经使用过专有的实现（现在甚至无法访问），它们非常快。

- JoeG

---

如果您正在参考Ukonnen算法，我不知道是否有任何标准实现。这是一个相当复杂的算法，我不想编写它或使用一些不太知名的源代码。 - BiGYaN