查找字符串中是否包含集合中的任意一个字符串

Question

我正在尝试提高一个Java函数的性能，该函数确定给定的搜索字符串是否包含集合中的>0个字符串。这可能看起来像是过早地进行优化，但该函数被频繁调用，因此任何速度提升都将非常有益。

当前代码如下：

public static boolean containsAny(String searchString, List<String> searchCollection) {
    int size = searchCollection.size();
    for (int i = 0; i < size; i++) {
        String stringInCollection = searchCollection.get(i);
        if (!Util.isNullOrEmpty(stringInCollection)) {
            // This is a performance optimization of contains.
            if (searchString.indexOf(stringInCollection, 0) > -1) {
                return true;
            }
        }
    }
    return false;
}

列表通常有大约30个元素，并且同一集合在每次调用之间经常被重复使用。

上面的代码是一个相当简单的线性搜索。我认为除非我们更改数据结构使其比O(n)更好，否则无法显着改进它。是否有任何数据结构可以让我做到这一点？

- Yrlec

---

选择另一种数据结构来存储字符串，例如使用 Map<Character,List<String>> ，其中键是字母表中的一个字母，而 List<String> 包含以该键作为开头的单词的排序列表。或者使用 trie。 - Luiggi Mendoza

它们主要用于那个，是的。我不确定它们的适用性。这让我想到了“最长公共子串问题”，可以通过后缀树有效地解决。虽然不完全一样，但也可以使用。 - keyser

请查看 Aho Corasick。你需要构建一个状态机，但之后搜索会很快。 - Sotirios Delimanolis

我已经对当前的建议进行了一些性能测试，你目前的代码表现比我提出的代码要好得多，甚至比基于正则表达式模式的@Joop的代码表现更好（即使该模式已被缓存）。 - Vlad

你可能需要修改ahocorasick.org的实现以更好地适应你的用例。ahocorasick.org可以找到所有匹配项，而你可以在第一个匹配项停止。这是一个重要的区别。 - Ryan

Answer 1

使用Aho-Corasick算法可以大幅提高速度。

您可以使用O（集合中所有字符串的总长度）的时间和空间构建一个Aho-Corasick自动机。然后，通过遍历此自动机，在O（S.length）的时间内可以检查集合中的字符串是否是给定字符串S的子串。

- kraskevich

Answer 2

// Make a regex pattern (once only):
StringBuilder pattern = new StringBuilder();
for (String sought : searchCollection) {
    if (!Util.isNullOrEmpty(sought)) {
        if (pattern.length() != 0) {
            pattern.append('|');
        }
        pattern.append(Pattern.quote(sought));
    }
}
final Pattern PATTERN = Pattern.compile("(" + pattern + ")");

这将创建一个类似于"(abc|def|ghi)"的替代模式。您可能需要考虑不区分大小写的搜索。

在函数containsAny中：

Matcher m = PATTERN.matcher(searchString);
return m.find();

正则表达式编译相对聪明。可以将要查找的单词集合看作一个搜索树："agent" 和 "agitator" 转为 ("ag", ("ent", "itator"))

- Joop Eggen

---

@SivaKumar Pattern.quote(sought) 应该返回 sought，其中所有正则表达式特殊字符都被转义。 - Joop Eggen

@SivaKumar 你的意思是在“abc |”上查找（你漏掉了'a'）会返回true，因为abc被寻找到了。对于整个单词搜索，搜索字符串可以使用边界标记：“\ \ b(abc|def|ghi)\ \ b”。 - Joop Eggen

如果模式为abc|def|ghi，搜索字面量bc|将不会返回true。如果您要搜索的字符串之一包含字面管道字符，则只需使模式构建器更复杂以进行转义即可。 - Kevin Krumwiede

@KevinKrumwiede 谢谢，所以我误解了这个评论。忘记告诉你 |（“或”）分隔匹配的替代项。 - Joop Eggen

我认为Matcher#find()对于输入的长度也是O(n)，这就是为什么我点赞了这个答案。 - Kevin Krumwiede

Answer 3

这是一个CPU密集型操作，不会长时间运行或被I/O阻塞。如果您使用的是Java 8，可以像下面展示的那样使用并行流来进行并行处理。该方法已更改为使用Collection而非List，以使其更加灵活。

public static boolean containsAny(final String searchString,
        final Collection<String> searchCollection) {
    return searchCollection.stream().parallel()
            .anyMatch(x -> searchString.indexOf(x) > -1);
}

此外，应使用Set作为基础数据结构，而不是使用List，这样可以消除重复条目（如果有的话）。

- Gladwin Burboz

Answer 4

使用Aho Corasick算法，您可以在大约2/3的时间内完成搜索。

来自@user2040251和其他人（包括我自己）的被接受的答案建议使用Aho Corasick算法。

从您的评论中，我可以看出您不是在寻找一般解决方案，而是在寻找在特定用例中表现良好的解决方案。

@Vlad创建了一个可能的测试套件来基准测试一些提议的解决方案。

由Java实现的测试，由@Marco13在http://ahocorasick.org/进行，表明您的初始实现更快。

您的评论提供了关于您正在尝试解决的问题的重要附加细节：

• 大约有30个字符串需要搜索
• 要查找的字符串长度为10-40个字符。
• 要搜索的字符串通常约为100个字符长。
• 您正在搜索的字符串是文件路径。

我对@Vlad的代码进行了几个快速修改，以更好地匹配您描述的问题的具体情况。

我之前曾评论过其他人测试过的Aho-Corasick实现程序找到了所有可能的匹配项。一旦找到第一个匹配项就返回的方法应该会更快。 为了验证我的直觉是否正确，我创建了一个分支，基于Robert Bor的Java Aho-Corasick实现。 这个分支现在已经合并到Aho-Corasick中了！

• 在4337毫秒内完成了100000个containsAny操作（平均0毫秒）
• 在41153毫秒内完成了100000个containsAnyWithRegex操作（平均0毫秒）
• 在23624毫秒内完成了100000个containsAnyWithOffset操作（平均0毫秒）
• 在7956毫秒内完成了100000个containsAnyAhoCorasickDotOrg操作（平均0毫秒）
• 在5351毫秒内完成了100000个containsAnyAhoCorasickDotOrgMatches操作（平均0毫秒）
• 在2948毫秒内完成了100000个containsAnyAhoCorasickDYoo操作（平均0毫秒）
• 在7052毫秒内完成了100000个containsAnyHospool操作（平均0毫秒）
• 在5397毫秒内完成了100000个containsAnyRaita操作（平均0毫秒）
• 在8285毫秒内完成了100000个containsAnyJava8StreamParallel操作（平均0毫秒）

我还实现了一种方法，将每个搜索放在自己的线程中执行。该实现非常糟糕，速度大约慢了10倍。

更新：自从我最初的测试以来，我发现了一个更快的Aho-Corasick实现。

我包括了@GladwinB建议的Java 8并行流实现的基准测试，以及两个com.eaio.stringsearch实现。

可能仍然有收益可得。例如，这篇论文描述了一种适合您问题的集合匹配变体的Aho-Corasick。为入侵检测实现更快的字符串匹配

- Ryan

Answer 5

我相信最适合此类的数据结构是 后缀树。对于长度为n的字符串，构建后缀树需要Theta(n)的时间，而在其中搜索长度为m的子字符串，则需要O(m)的时间。

这是一种非常适合（并且旨在）用于搜索字符串的数据结构之一。它是一种非常常见的数据结构，有许多在线实现。

- ethanfar

Answer 6

与此相比，这是一种倒置和优化的版本：

  public static boolean containsAny(String searchString, List<String> searchCollection) {
    for (int offset = 0; offset < searchString.length(); offset++) {
      for (String sought: searchCollection) {
        int remainder = searchString.length() - offset;
        if (remainder >= sought.length && searchString.startsWith(sought, offset)) {
          return true;
        }
      }
    }
    return false;
  }

注意使用带有偏移量的startsWith。

- Vlad

Answer 7

许多其他人已经回答了，在存储和搜索字符串方面，通常有更好的数据结构。你的问题在于，你的列表只有30个条目。使用更复杂的数据结构和算法所添加的开销很容易超过您从中获得的收益。

不要误解我，你的瓶颈是indexOf行。看起来它占用了95%的处理。但是如果其他数据结构没有帮助（我尝试过一个现成的Aho-Corasick Trie，它比原来慢两倍），这里有一些东西需要检查...

关于使用indexOf而不是contains的评论是值得怀疑的。在我的测试中，我使用"contains"每秒看到约150万个查询，而使用indexOf只有大约70万。如果你有相同的结果，那将使你的速度提高一倍。

更改

// This is a performance optimization of contains.
if (searchString.indexOf(stringInCollection, 0) > -1) {

[返回] 到

if (searchString.contains(stringInCollection)) {

如果你感兴趣，我测试过的trie在这里：http://ahocorasick.org/，代码非常简单。问题是它没有提供在找到第一个匹配项后立即退出的功能。它会解析整个字符串并查找所有匹配项。当没有匹配项时，速度比indexOf()快（830K/sec），但仍然比contains()慢。

显然http://ahocorasick.org/已经不存在了。

非常相似的代码（可能是同一个）可以在https://github.com/robert-bor/aho-corasick找到。

- Ted Bigham

---

链接已经失效，很抱歉。你能修复它吗？谢谢！ - fdermishin

性能的提升严重依赖于数据。例如，如果字符串足够长，则在理想情况下加速比与子字符串数量（约30个）成正比。然而，例如Aho-Corasick算法的内部循环比“contains”的内部循环更复杂，因此可能会慢几倍，但远不至于慢30倍。对于长字符串进行基准测试以查看性能差异将非常有趣。 - fdermishin

Answer 8

你可以尝试使用这个解决方案：

    final String[] searchList = searchCollection.toArray(new String[0]);
    Arrays.sort(searchList, new Comparator<String>() {
        @Override
        public int compare(final String o1, final String o2) {
            if (o1 == null && o2 == null) {
                return 0;
            }
            if (o1 == null || o1.isEmpty()) {
                return 1;
            }
            if (o2 == null || o2.isEmpty()) {
                return -1;
            }
            return o1.compareTo(o2);
        }
    });
    final int result = Arrays.binarySearch(searchList, searchString);
    return result >= 0 ? true : false;

- Nikola Dimitrovski

---

假设字符串列表已经排序，但是这并没有在任何地方说明？如果列表没有排序，最好在将其传递给此函数之前对其进行排序，以便它只被排序一次，而不是每次调用函数时都要排序。除此之外，我同意这个解决方案。 - PandaConda

这个解决方案并不能解决问题。它只适用于searchString和列表中字符串的完全匹配，但问题要求匹配子字符串。 - fdermishin

Answer 9

你可以使用哈希集数据结构。但是哈希集不允许重复。例如，在哈希集中不能有两个相同的字符串 "foo"。

好处是，复杂度应该为 O(1)。

http://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html

- Vlad Muresan

---

这与问题无关。 - fdermishin

Answer 10

@Yrlec，从你的评论中可以发现，searchCollection 可以被视为常数且不需要太多修改，你可以对数组列表进行排序并进行缓存，也可以实现自定义 List 类来存储已排序的元素的引用。

原因在于，如果你将 searchCollection 排序，则可以使用 String 的 compareTo 方法，并减少迭代次数，从而提高方法性能。

public static boolean containsAny(String searchString, List<String> searchCollectionSorted) {
    int size = searchCollectionSorted.size();
    for (int i = 0; i < size; i++) {
        String stringInCollection = searchCollectionSorted.get(i);
        if (!Util.isNullOrEmpty(stringInCollection)) {
            if (stringInCollection.compareToIgnoreCase(searchString) > 0) {
                if (searchString.startsWith(stringInCollection) {
                    return true;
                } else {
                    // No point of iterating if we reach here as the searchstring is greater and hence iterations are saved improving performance
                    break;
                }
            }
        }
    }
    return false;
}

- Manjunath

---

只有当 searchString 以任何一个 stringInCollection 开头时才有效，但如果它在中间包含了 stringInCollection，则无效。 - fdermishin