Java 多字符串同时匹配文本，消耗 CPU 过高，如何优化？

[print1024]

本人遇到一个性能方法的问题，这是打标的场景，主要逻辑是三个循环，YYDTO 中有段文本，XXDTO 中有关键词列表，XXDTOList 量级大约 10 万条必须执行，判断关键词列表是否全部在文本中存在，如果存在则执行业务逻辑； 目前测试了 stream 、parallelStream 、正则和原生的 for 循环，发现下面 checkExistRule 是最快的，大约 50ms ，但是会一直消耗大量 CPU （串行下一直占用 100%）。之前还考虑使用 AC 自动机，但是因为单条匹配到还要处理业务逻辑，所以不太合适。

text 举例 ：
"#DIESEL 大牌好友# @宋雨琦_G-I-DLE 演绎#DIESEL2023 秋冬系列# 牛仔坠饰 D-VINA 包袋。渐变丹宁渲染不羁格调，另类包型注解无畏想象"

keywordRule 中举例：
[鼎赛龙, 男士春夏, D-FINING, 深灰色, 锥形牛仔裤] string[]
[DIESEL, 男士春夏, DFINING, 深灰色, 锥形牛仔裤] string[]
上面这是关键词列表中的一个，总共 10 万个，也就是 10 万个 List 中每个 List 包含 N  个字符串数组

请问有什么方式进行优化？能不能做到时间复杂度 O(1) 或者 O(m + n)级别？

    for (YYDTO yydto : YYDTOList) { //2000
        String text = yydto.getText();
        for (XXDTO xxdto : XXDTOList) {//10w
          List<String[]> keywordRule = xxdto.getKeywordRule();
            if (checkExistRule(keywordRule, text)) {
                // 处理业务逻辑
                // yydto.set(xxdto.getName());
            }
        }
    }

    private boolean checkExistRule(List<String[]> keywordRule, String text) {
        try {
            for (String[] strings : keywordRule) {
                for (String string : strings) {
                    if (!text.contains(string)) {
                        return false;
                    }
                }
                return true;
            }
        } catch (Exception e) {
            
        }
        return false;
    }
    

[liprais]

你想的太简单了
建议再想想
比如你这 10w 敏感词必须一个一个判断么?
有没有可能搞成前缀树？

[BiChengfei]

试试 parallelStream ？
感觉现在还可以啊，不算慢，资源消耗也还可以，关键实现简单，好维护

[print1024]

@liprais 这是一个打标的场景，如果关键词全部包含则打上这个标签，考虑过建树但是匹配完如何知道是哪个关键词规则命中呢

[print1024]

@BiChengfei parallelStream CPU 测试消耗比较大，我们线上 CPU 就 2 核，直接就打满了

[xtreme1]

ac + double array trie

[alva0]

改下设计？先将所有关键字去重，放在一个有序集合中，XXDTOList 中的关键字列表存下标，每次 YYDTO 先判断关键字集合，取出包含的所有下标，再与 XXDTOList 比较下标是否存在？这样子试下呢

[zizon]

YYDTOList.steram().flatmap((yydto)=>{
XXDTOList.stream().flatmap(::getKeywordRule()::stream()).flatmap((keyword)=>{
return Map.Entry(keyword,yydto)
})
}).filter((entry)=>{
return entry.values.contains(keyword)
}).foreach()

如果不改数据结构/算法本身的话.

[zizon]

@zizon 哦,没有 early terminate.忽略.

[corningsun]

首先推测 checkExistRule(List<String[]> keywordRule, String text) 的实现有问题，OP 的实现只会用到第一条规则。
其次 String 的 contains 匹配是数组下标查找，也是一层循环，效率不高。
建议是先分词，得到 哈希数组，然后再比较，示例代码如下：


public static boolean checkExistRuleV2(List<Set<String>> keywordRule, Set<String> textSet) {
return keywordRule.stream().anyMatch(textSet::containsAll);
}


Benchmark 压测结果如下：循环 10000 次的时间，从 13 ms 降低到 0.5 ms

Benchmark Mode Cnt Score Error Units
Print1024Test.checkExistRule avgt 6 13.877 ± 0.148 ms/op
Print1024Test.checkExistRuleV2 avgt 6 0.528 ± 0.035 ms/op

单元测试代码

package org.corning.v2ex.year2024;

import com.google.common.collect.Lists;
import com.google.common.collect.Sets;
import org.junit.jupiter.api.Test;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;
import org.openjdk.jmh.runner.options.TimeValue;

import java.util.Arrays;
import java.util.List;
import java.util.Set;
import java.util.concurrent.TimeUnit;
import java.util.stream.Collectors;

public class Print1024Test {

public static List<String[]> keywordRule = Lists.newArrayList(
new String[]{"鼎赛龙", "男士春夏", "D-FINING", "深灰色", "锥形牛仔裤"},
new String[]{"DIESEL", "男士春夏", "DFINING", "深灰色", "锥形牛仔裤"}
);
public static String text = "#DIESEL 大牌好友# @宋雨琦_G-I-DLE 演绎#DIESEL2023 秋冬系列# 牛仔坠饰 D-VINA 包袋。渐变丹宁渲染不羁格调，另类包型注解无畏想象";
public static List<Set<String>> keywordRuleSet = keywordRule.stream()
.map(Sets::newHashSet)
.collect(Collectors.toList());

// 这里可能需要更好的分词手法，trim / 去掉逗号等
public static Set<String> textSet = Arrays.stream(text.split(" ")).collect(Collectors.toSet());

@Test
public void runBenchmarks() throws Exception {
Options options = new OptionsBuilder()
.include(this.getClass().getName() + ".*")
.mode(Mode.AverageTime)
.warmupTime(TimeValue.seconds(1))
.warmupIterations(6)
.threads(1)
.measurementIterations(6)
.forks(1)
.shouldFailOnError(true)
.shouldDoGC(true)
.build();
new Runner(options).run();
}


@Benchmark
@Test
@OutputTimeUnit(TimeUnit.MILLISECONDS)
public void checkExistRule() {
for (int i = 0; i < 10000; i++) {
Print1024.checkExistRule(keywordRule, text);
}
}

@Benchmark
@Test
@OutputTimeUnit(TimeUnit.MILLISECONDS)
public void checkExistRuleV2() {
for (int i = 0; i < 10000; i++) {
Print1024.checkExistRuleV2(keywordRuleSet, textSet);
}
}

}

[GuuJiang]

AC 自动机几乎是多模式匹配的不二解了，你说的“但是因为单条匹配到还要处理业务逻辑”是什么意思，不妨展开讲讲，看到底是什么原因导致了不适用 AC 自动机

[reeco]

线上 CPU 就 2 核，啥优化都没用

[soupu626]

理论上这个关键词的命中率应该极低，可以先筛一波，比如关键词建个前缀 map ，这个前缀取多长看你们关键词的区分度，然后先用输入文本过一遍这个 map ，筛出来可能命中的关键词小集合，然后再来全量的遍历

简单脑测了下，前面那个筛过的复杂度应该是 (N-L)*log(M) N 是输入字符串长度，M 是前缀 Map 大小 L 是前缀长度，这样筛出来的小集合理论上应该很小，再过一次 N*S 就行 S 是小集合大小

[print1024]

@GuuJiang 因为这是一个打标的场景，A 标签规则是一组关键词，B 标签也是一组关键词，如果文本完全命中这些关键词的话怎么区分是 A 标签命中还是 B 标签命中呢

[GuuJiang]

@print1024 这个完全不是问题啊，首先 AC 自动机命中时本来就知道是哪一个关键词命中的，再额外维护一下从关键词到标签的反向关联不就行了，更简单的是在构造 AC 自动机的过程中直接把标签信息冗余到节点上

[print1024]

@GuuJiang 这个反向关联关系不太好维护，因为多个关键词同时包含才能确定一个标签，拿到了命中的关键词后，去循环查找哪个标签下的关键词组合能够匹配上？那相当于还是要从头到尾遍历一次 XXDTOList 啊

[print1024]

@corningsun 感谢，checkExistRule 是有问题的，我目前采用了你这种方式，线上 YYDTO 每条耗时差不多 150ms ，因为每次都要过 10w 条 XXDTO

[print1024]

@soupu626 这是一个不错的思路，前缀 map 能细讲一下吗

[JKeita]

trie 树不就行了？

[JKeita]

trie 数+bitmap ，用 trie 数匹配到的所有关键字生成一个匹配结果的 bitmap ，然后再根据每个标签的关键字独有的 bitmap 一个个比对，成的话就执行相关策略

[yicixin]

不知道说的对不对，
1.首先看了下示例代码，一个 rule 是一个二维字符串数组，一段文本匹配该 rule 的条件是该文本中出现了 rule 中所有的关键词，既然如此，一个 rule 是否可以简化成一个一维字符串数组，即把二维数组中所有的关键词去重后放入一个一维数组，这样问题可以稍微简化一下。

2.接着，换个思路，把 10w 个 rule 中的所有关键词去重后构造前缀树，用 text 去进行匹配这个 10wKeyTrie ，拿到该 text 匹配到的所有关键词，将匹配到的所有关键词排序后拼接，最终得到一个字符串，例如 text 匹配了关键词 深灰色、锥形牛仔裤和 DIESEL ，假设排序拼接后是 DIESEL 深灰色锥形牛仔裤，记这个最终字符串为 matchText

3.上文说了把一个 rule 简化成一个一维字符串数组，那么每个 rule 也可以进行类似的排序拼接，那么最终 10w 个 rule 就是 10w 个字符串，把这 10w 个字符串构造前缀树，叫 10wRuleTrie 吧，最后用 2.中最后得到的 matchText 放进这个 10wRuleTrie 里进行匹配，如果成功匹配上即说明满足该条 rule 。

其中的 10wKeyTrie 和 10wRuleTrie 都是可以在初始化的时候就可以构造好，每次循环内要做的就是对进行 text 与 10wKeyTrie 的匹配-->得到多个关键词，排序后拼接--> 与 10wRuleTrie 进行匹配

[lrjia]

@print1024 #15 不用循环查找的，做一个倒排索引就行了

[lrjia]

ac 自动机 + trie 。记 ac 自动机匹配到的关键字个数为 n ，最终匹配到的规则数为 m 。复杂度最差应该是 O(min(2^n, 10w * n))，一般情况应该是 O(nm) https://pastebin.ubuntu.com/p/JbcMYQqHfp/

[wanqiangcrack]

你这个优化思路应该是对数据集做索引，做完索引再去匹配。 这样单次需要处理的数据就少很多了。

[crazyweeds]

DFA 了解一下

[gongxuanzhang]

前缀树正解。。 而且你这个 try catch 莫名其妙

[missya]

试试 AI 打标

[vivisidea]

AC 自动机肯定适用。。AC 自动机只是把词库快速匹配出来，你说的逻辑是放在匹配后的处理逻辑，跟 AC 无关

最直接的就是 Trie 树，把所有的词都建一个 trie 树，匹配出一堆词之后再看这堆词属于哪个 label

不好理解的话就试个简单的，先做一道粗筛
包含所有词，意味着也包含所有字

把输入字符串 变成字符 hashset ，kewordrule 也变成多个 hashset ，把原来的多重循环变成 hashset 的交集运算，速度应该会比字符串循环快，粗筛出候选，再走原来的逻辑走精确匹配

[print1024]

@vivisidea @corningsun @GuuJiang @soupu626 @lrjia 目前采用了 @vivisidea 所说的这种方式，不过我是 AC 自动机+ HashMap<keyword,Set<XXDTO>>这种形式，在数据量大的情况下较 @corningsun 方式速度能提升 10 倍。感谢感谢

[wysnxzm]

@crazyweeds #24 DFA+1

[MoYi123]

1. 把关键词列表放到一个 list, 去重排序, 并且把原先的关键词列表替换为这里的 rank, 关键词列表变成 list<list<rank>> 即把 string 离散化.

2. 把上面的 list<string> 变成 ac 自动机, 在文本中搜索. 得到一个 list<int>

3. 在 list<list<rank>>里搜索有哪几个 list<rank>是 list<int>的子序列, 在这里面抄一个最快的算法 https://leetcode.cn/problems/number-of-matching-subsequences/description/