如何降低大规模语料双词提取程序的时间复杂度？

问题背景 #

需要处理平均50万行的大规模语料，提取每个句子中的双词组合，但当前实现采用三层嵌套循环，时间复杂度达O(n³)，运行效率极低，急需优化思路。

当前实现代码 #

主循环代码 #

while (count < fileStream.size()) { // 1st loop

    List<String> lineArray = new ArrayList<>(Arrays.asList(fileStream.get(count).split("\\$+")));
    //lineArray.forEach(System.out::println);

    if (lineArray.size() > 2) {

        List<Sentence> sentences = sentenceSplitter.split(shoppingPlatform.getProductDescription());
        sentences.replaceAll(sentence -> new Sentence(sentence.toString().toLowerCase(new Locale("tr-TR"))));

        for (Sentence sentence : sentences) { // 2nd loop

            FsmParseList[] parseLists = fsm.robustMorphologicalAnalysis(sentence);
            ArrayList<FsmParse> candidateParses = morphologicalDisambiguator.disambiguate(parseLists);

            map = biGramSentences(map, map2, shortcuts, unicodes, candidateParses);

        }
        //sentences.forEach(System.out::println);
    }
    count++;
}

双词提取核心方法 #

private static Map<String, Integer> biGramSentences(Map<String, Integer> map, Map<String, String> map2, ArrayList<String> shortcuts, ArrayList<String> unicodes, ArrayList<FsmParse> candidateParses) {

    Set<String> keys = map2.keySet();
    for (int i = 0; i < candidateParses.size() - 1; i++) { // 3rd loop

        for (String key : keys) {

            if (candidateParses.get(i).getSurfaceForm().equals(key)) {
                ...
            }
            if (candidateParses.get(i + 1).getSurfaceForm().equals(key)) {
                ...
            }
        }

        String temp = candidateParses.get(i).getSurfaceForm() + " " + candidateParses.get(i + 1).getSurfaceForm();

        if (map.get(temp) != null) {
            map.put(temp, map.get(temp) + 1);
        } else if (map.get(temp) == null) {

            for (String unicode : unicodes) {

                if (candidateParses.get(i).getSurfaceForm().contains(unicode)) {
                   ...
                }
                if (candidateParses.get(i + 1).getSurfaceForm().contains(unicode)) {
                   ...
                }
            }

            boolean flag2 = true;
            for (String shortcut : shortcuts) {

                if (candidateParses.get(i).getSurfaceForm().equals(shortcut)
                        || candidateParses.get(i + 1).getSurfaceForm().equals(shortcut)) {

                    ...
                }
            }

            if (flag2 && (Objects.equals(candidateParses.get(i).getFinalPos(), "VERB") || Objects.equals(candidateParses.get(i + 1).getFinalPos(), "VERB")
                    || Objects.equals(candidateParses.get(i).getFinalPos(), "NUM") || Objects.equals(candidateParses.get(i + 1).getFinalPos(), "NUM")
                    || Objects.equals(candidateParses.get(i).getPos(), "PUNC") || Objects.equals(candidateParses.get(i + 1).getPos(), "PUNC"))) {

                ...
            }

            if (flag2 && (candidateParses.get(i).isPunctuation() || candidateParses.get(i + 1).isPunctuation()
                    || candidateParses.get(i).isNumber() || candidateParses.get(i + 1).isNumber())) {

                ...
            }

            if (flag2)
                map.put(temp, 1);
        }
    }
    return map;
}

优化思路 #

1. 用HashSet消除嵌套循环，将线性查询转为O(1)操作 #

当前biGramSentences中，遍历map2.keySet()和shortcuts的嵌套循环是主要耗时点。提前将这两个集合转为HashSet，直接通过contains方法判断元素是否存在，彻底消除嵌套循环：

// 预初始化（仅执行一次）
Set<String> map2KeySet = new HashSet<>(map2.keySet());
Set<String> shortcutSet = new HashSet<>(shortcuts);

// 在biGramSentences中替换原循环逻辑
if (map2KeySet.contains(current.getSurfaceForm())) {
    ...
}
if (map2KeySet.contains(next.getSurfaceForm())) {
    ...
}

// 替换shortcut的遍历判断
if (shortcutSet.contains(current.getSurfaceForm()) || shortcutSet.contains(next.getSurfaceForm())) {
    ...
}

2. 优化HashMap计数逻辑，减少重复哈希查询 #

原代码中判断map.get(temp)是否存在再更新计数，需要两次哈希查询。改用Map.merge方法，一次操作完成计数更新，效率更高：

// 替换原计数逻辑
map.merge(temp, 1, Integer::sum);

若需保留过滤逻辑，可先通过map.containsKey(temp)判断，仅当双词不存在时才执行过滤，避免无效计算。

3. 减少重复对象访问与创建 #

• 在biGramSentences的循环中，多次调用candidateParses.get(i)和get(i+1)，提前将对象存入局部变量，避免重复索引查找：

for (int i = 0; i < candidateParses.size() - 1; i++) {
    FsmParse current = candidateParses.get(i);
    FsmParse next = candidateParses.get(i+1);
    // 后续操作直接使用current和next
}

• 句子转小写时，若Sentence类支持直接修改内部文本，避免新建对象：

sentences.replaceAll(sentence -> {
    sentence.setText(sentence.toString().toLowerCase(new Locale("tr-TR")));
    return sentence;
});

4. 并行化处理独立任务 #

语料的行、句子之间处理逻辑完全独立，可使用并行流加速。注意将非线程安全的HashMap替换为ConcurrentHashMap：

fileStream.parallelStream().forEach(line -> {
    List<String> lineArray = new ArrayList<>(Arrays.asList(line.split("\\$+")));
    if (lineArray.size() > 2) {
        List<Sentence> sentences = sentenceSplitter.split(shoppingPlatform.getProductDescription());
        sentences.replaceAll(...);
        for (Sentence sentence : sentences) {
            // 形态分析与双词提取逻辑
            ...
            concurrentMap.merge(temp, 1, Integer::sum);
        }
    }
});

5. 提前过滤无效数据 #

进入形态分析等耗时步骤前，过滤掉空句子、长度不足2的句子（无法生成双词），减少不必要的计算：

for (Sentence sentence : sentences) {
    if (sentence.length() < 2) {
        continue;
    }
    // 后续形态分析与双词提取
    ...
}

6. 优化Unicode检查逻辑 #

若unicode集合较大，预编译正则表达式，一次性检查是否包含任意unicode字符，替代遍历判断：

// 预初始化（仅执行一次）
String unicodePattern = String.join("|", unicodes);
Pattern pattern = Pattern.compile(unicodePattern);

// 在biGramSentences中使用
Matcher matcher = pattern.matcher(current.getSurfaceForm());
if (matcher.find()) {
    ...
}
matcher.reset(next.getSurfaceForm());
if (matcher.find()) {
    ...
}

内容的提问来源于stack exchange，提问作者Abdullah Gür