查找字符串是否包含集合中的任何字符串

string data-structures collections java

2022-09-02 19:35:19

我正在尝试提高我拥有的Java函数的性能，该函数正在确定给定的搜索字符串是否包含集合中的>0个字符串。这可能看起来像过早优化，但该函数称为A LOT，因此任何加速都将是非常有益的。

代码当前如下所示：

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）更好。是否有任何数据结构可以让我做到这一点？

答案 1

使用Aho-Corasick算法可以显着加快它的速度。

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

答案 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" and "agitator" to ("ag", ("ent", "itator"))