DFA 查找工具 - WordTree

简介

DFA（Deterministic Finite Automaton，确定有限自动机）查找算法是一种高效的关键词匹配算法，广泛用于敏感词过滤、关键词提取等场景。Hutool 提供了 WordTree 类来实现 DFA 匹配，支持构建关键词树、查找关键词、处理特殊字符等功能。通过 WordTree，可以轻松进行复杂的关键词匹配。

1. 构建关键词树

关键词树的构建是 DFA 匹配的基础。我们可以通过 addWord 方法向树中添加关键词。

示例：构建关键词树

import cn.hutool.dfa.WordTree;
import java.util.List;

public class DFATreeExample {
    public static void main(String[] args) {
        // 创建关键词树
        WordTree tree = new WordTree();

        // 添加关键词
        tree.addWord("大");
        tree.addWord("大土豆");
        tree.addWord("土豆");
        tree.addWord("刚出锅");
        tree.addWord("出锅");

        // 构建完成的关键词树用于后续的匹配操作
    }
}

• addWord(String word)：向关键词树中添加关键词。
  • word：要添加的关键词。
  • 返回值：无返回值，直接将关键词加入到树中。

作用： 构建关键词树用于后续的高效匹配。

实际开发场景： 在敏感词过滤、关键词提取等场景中，可以提前构建一个关键词树，提高匹配效率。

2. 查找关键词

关键词匹配是 DFA 查找的核心功能，Hutool 提供了多种匹配模式，包括最短匹配、最长匹配、跳过已匹配关键词等。

示例：查找关键词

import cn.hutool.dfa.WordTree;
import java.util.List;

public class DFATreeExample {
    public static void main(String[] args) {
        // 创建并构建关键词树
        WordTree tree = new WordTree();
        tree.addWord("大");
        tree.addWord("大土豆");
        tree.addWord("土豆");
        tree.addWord("刚出锅");
        tree.addWord("出锅");

        // 正文
        String text = "我有一颗大土豆，刚出锅的";

        // 情况一：标准匹配，匹配到最短关键词，跳过已匹配的关键词
        List<String> matchAll = tree.matchAll(text, -1, false, false);
        System.out.println("标准匹配结果: " + matchAll); // 输出: [大, 土豆, 刚出锅]

        // 情况二：匹配到最短关键词，不跳过已匹配的关键词
        matchAll = tree.matchAll(text, -1, true, false);
        System.out.println("匹配到最短关键词，不跳过已匹配的结果: " + matchAll); // 输出: [大, 土豆, 刚出锅, 出锅]

        // 情况三：匹配到最长关键词，跳过已匹配的关键词
        matchAll = tree.matchAll(text, -1, false, true);
        System.out.println("匹配到最长关键词，跳过已匹配的结果: " + matchAll); // 输出: [大, 土豆, 刚出锅]

        // 情况四：匹配到最长关键词，不跳过已匹配的关键词（最全关键词）
        matchAll = tree.matchAll(text, -1, true, true);
        System.out.println("匹配到最长关键词，不跳过已匹配的结果: " + matchAll); // 输出: [大, 大土豆, 土豆, 刚出锅, 出锅]
    }
}

• matchAll(String text, int limit, boolean isDensityMatch, boolean isGreedMatch)：查找文本中的所有匹配关键词。
  • text：要匹配的文本内容。
  • limit：匹配结果的限制数量，-1 表示不限制。
  • isDensityMatch：是否密集匹配（不跳过已匹配的关键词）。
  • isGreedMatch：是否贪婪匹配（匹配最长的关键词）。
  • 返回值：返回匹配到的关键词列表。

作用： 通过不同的匹配模式，实现对文本中关键词的多样化匹配需求。

实际开发场景： 在敏感词检测、广告过滤、关键词标注等场景中，可以根据需求选择最合适的匹配模式。

3. 处理特殊字符

在实际应用中，关键词可能包含特殊字符。Hutool 提供了 StopChar 类，用于自动跳过这些字符，在匹配时不会影响结果。

示例：处理包含特殊字符的关键词

import cn.hutool.dfa.WordTree;
import java.util.List;

public class DFATreeExample {
    public static void main(String[] args) {
        // 创建并构建关键词树
        WordTree tree = new WordTree();
        tree.addWord("关键字");

        // 正文包含特殊字符
        String text = "这是一个包含特殊字符的〓关键☆字的例子";

        // 匹配关键词，自动跳过特殊字符
        List<String> matchAll = tree.matchAll(text, -1, false, true);
        System.out.println("匹配结果: " + matchAll); // 输出: [关键字]
    }
}

• StopChar：用于定义跳过的特殊字符，match 和 matchAll 方法在执行时会自动去除这些字符。

作用： 在文本中自动跳过无意义的特殊字符，确保匹配的准确性。

实际开发场景： 在处理用户输入时，往往会出现带有特殊字符的关键词，此功能可以确保匹配结果不受这些字符的干扰。