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

本人遇到一个性能方法的问题，这是打标的场景，主要逻辑是三个循环，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;
    }

vivisidea

104 天前

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

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

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

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

MoYi123

103 天前

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/