SpringBoot 中使用 DFA 算法实现高性能敏感词过滤与内容审核

在当今的内容平台上，敏感词过滤系统已成为维护健康网络环境的基石。无论是社交媒体上的内容审核、电商平台的商品描述管理，还是在线游戏中的聊天监控，都需要一套高效且可靠的机制来实时拦截不当信息。面对海量文本，传统的字符串遍历或正则表达式匹配往往力不从心，存在性能瓶颈。

那么，有没有一种算法，既能保证毫秒级的响应速度，又能轻松应对成千上万的敏感词库呢？答案是肯定的。本文将深入剖析基于 DFA（有限状态自动机） 的算法原理，并手把手带你使用 SpringBoot 实现一套高性能的敏感词过滤系统。

为什么 DFA 算法是更优选择？

传统方案的性能瓶颈

在实际开发中，简单粗暴的敏感词过滤方法通常面临以下挑战：

❌ 暴力匹配的低效

// 时间复杂度：O(n × m × k)
// 随着敏感词数量增加，性能急剧下降
for (String word : sensitiveWords) {
    if (text.contains(word)) {
        // 处理敏感词
    }
}

当敏感词数量达到数千甚至数万级别时，处理一篇稍长的文章可能需要数秒时间，这会严重影响用户体验和系统吞吐量。

❌ 正则表达式的局限性
尽管正则表达式功能强大，但在本场景下却存在明显缺陷：

• 构建一个囊括所有敏感词的巨型正则表达式会导致编译时间过长。
• 动态增删敏感词需要重新编译整个表达式，不够灵活。
• 内存占用随敏感词数量线性增长。
• 在匹配复杂规则或长文本时，可能存在回溯开销，效率下降。

DFA 算法的核心优势

DFA 算法通过构建状态机模型，将敏感词匹配过程转化为确定性的状态转移，带来了质的飞跃：

✅ 线性时间复杂度: O(n) - 只需遍历待检测文本一次，匹配时间与敏感词库大小无关。
✅ 空间共享优化: 利用 Trie 树 数据结构，使具有共同前缀的敏感词共享存储节点，显著减少内存占用。
✅ 确定性匹配: 匹配过程无需回溯，避免了正则表达式可能产生的回溯开销。
✅ 动态扩展友好: 支持在运行时动态添加或删除敏感词，无需重建整个数据结构。

举个例子，当敏感词库从1千个扩展到1万个时，暴力匹配的耗时可能增加近10倍，而 DFA 算法的处理时间几乎保持不变。

DFA 算法原理解析：从数学模型到 Trie 树

DFA 的数学本质

DFA（Deterministic Finite Automaton，确定有限状态自动机）是一个经典的计算机基础数学模型，通常定义为一个五元组 M = (Q, Σ, δ, q₀, F)：

• Q: 有限的状态集合。
• Σ: 输入字母表（例如所有中英文字符）。
• δ: 状态转移函数，定义了在当前状态和输入字符下，下一个状态是什么。
• q₀: 初始状态。
• F: 接受状态集合（在敏感词过滤中，代表一个敏感词匹配完成）。

在敏感词过滤场景里，每个状态代表匹配到某个字符位置。

用 Trie 树直观理解 DFA

Trie 树（字典树或前缀树）是 DFA 的一种非常直观的实现方式。让我们通过一个例子来构建它。

假设敏感词库为：["apple", "app", "application", "apply", "orange"]

构建的 Trie 树结构可视化如下：

root
├── a
│   └── p
│       └── p [结束]  ← 匹配到 “app”
│           └── l
│               ├── e [结束]  ← 匹配到 “apple”
│               ├── i
│               │   └── c
│               │       └── a
│               │           └── t
│               │               └── i
│               │                   └── o
│               │                       └── n [结束]  ← 匹配到 “application”
│               └── y [结束]  ← 匹配到 “apply”
└── o
    └── r
        └── a
            └── n
                └── g
                    └── e [结束]  ← 匹配到 “orange”

Trie 树的关键特征：

1. 前缀共享：“app” 作为 “apple”、“application”、“apply” 的共同前缀，在树中只存储一次，从该节点再分支出不同路径。这极大地节省了空间。
2. 状态转移：每个 ├── 或 └── 代表一次基于输入字符的状态转移。[结束] 标记代表 DFA 的接受状态（即一个完整的敏感词）。
3. 高效查找：要检测文本中是否包含 “application”，只需从根节点开始，依次输入 a-p-p-l-i-c-a-t-i-o-n 共11次状态转移即可完成，无需与其他敏感词逐个比较。

匹配过程示例：
检测文本 “I like apples and apps”：

1. 指针从根节点开始，遇到字符 ‘a’，转移到 ‘a’ 子节点。
2. 遇到 ‘p’，转移到 ‘p’ 子节点。
3. 遇到 ‘p’，转移到 ‘p’ 子节点（此节点标记为[结束]，成功匹配敏感词 “app”）。
4. 继续，遇到 ‘l’，转移到 ‘l’ 子节点。
5. 遇到 ‘e’，转移到 ‘e’ 子节点（此节点标记为[结束]，成功匹配敏感词 “apple”）。

整个过程只需对文本进行一次线性扫描，效率极高。

核心代码实现详解

1. 基础数据结构：Trie 树节点

每个节点代表自动机中的一个状态。

public class TrieNode {
    // 子节点映射：字符 -> Trie节点
    private Map<Character, TrieNode> children = new HashMap<>();

    // 是否为敏感词的结束节点
    private boolean isEnd = false;

    // 完整敏感词内容（便于输出）
    private String keyword;

    public TrieNode getChild(char c) {
        return children.get(c);
    }

    public TrieNode addChild(char c) {
        return children.computeIfAbsent(c, k -> new TrieNode());
    }

    public boolean hasChild(char c) {
        return children.containsKey(c);
    }
    // 省略 getters 和 setters...
}

2. DFA 过滤器核心类

这是最精简的 DFA 过滤器实现，包含了核心的构建与匹配逻辑。

public class SensitiveWordFilter {
    private TrieNode root;
    private int minWordLength = 1;

    public SensitiveWordFilter(List<String> sensitiveWords) {
        this.root = buildTrie(sensitiveWords);
        this.minWordLength = sensitiveWords.stream()
            .mapToInt(String::length).min().orElse(1);
    }

    /**
     * 构建 Trie 树
     */
    private TrieNode buildTrie(List<String> words) {
        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                node = node.addChild(c);
            }
            node.setEnd(true);
            node.setKeyword(word);
        }
        return root;
    }

    /**
     * 检查是否包含敏感词 - 核心 DFA 匹配算法
     */
    public boolean containsSensitiveWord(String text) {
        if (text == null || text.length() < minWordLength) {
            return false;
        }

        char[] chars = text.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (dfaMatch(chars, i)) {
                return true;
            }
        }
        return false;
    }

    /**
     * DFA 状态转移匹配
     */
    private boolean dfaMatch(char[] chars, int start) {
        TrieNode node = root;

        for (int i = start; i < chars.length; i++) {
            char c = chars[i];

            if (!node.hasChild(c)) {
                break; // 状态转移失败，从文本下一个字符重新开始
            }

            node = node.getChild(c);

            if (node.isEnd()) {
                return true; // 到达接受状态，匹配成功
            }
        }
        return false;
    }

    /**
     * 查找并替换敏感词
     */
    public String filter(String text, String replacement) {
        List<SensitiveWordResult> words = findAllWords(text);

        // 从后往前替换，避免索引变化问题
        StringBuilder result = new StringBuilder(text);
        for (int i = words.size() - 1; i >= 0; i--) {
            SensitiveWordResult word = words.get(i);
            String stars = String.valueOf(replacement != null ? replacement : "*")
                .repeat(word.getEnd() - word.getStart() + 1);
            result.replace(word.getStart(), word.getEnd() + 1, stars);
        }
        return result.toString();
    }

    /**
     * 查找所有敏感词
     */
    public List<SensitiveWordResult> findAllWords(String text) {
        List<SensitiveWordResult> results = new ArrayList<>();

        if (text == null || text.length() < minWordLength) {
            return results;
        }

        char[] chars = text.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            TrieNode node = root;
            int j = i;

            while (j < chars.length && node.hasChild(chars[j])) {
                node = node.getChild(chars[j]);
                j++;

                if (node.isEnd()) {
                    results.add(new SensitiveWordResult(
                        text.substring(i, j), i, j - 1));
                }
            }
        }
        return results;
    }
}

3. 敏感词匹配结果封装

public class SensitiveWordResult {
    private String word;      // 敏感词内容
    private int start;        // 在文本中的起始位置
    private int end;          // 结束位置

    public SensitiveWordResult(String word, int start, int end) {
        this.word = word;
        this.start = start;
        this.end = end;
    }
    // 省略 getters 和 toString...
}

实战应用场景与 SpringBoot 集成

场景一：高并发聊天消息实时过滤

在即时通讯系统中，过滤必须低延迟、高吞吐。

public class ChatMessageFilter {
    private SensitiveWordFilter wordFilter;
    private ExecutorService filterExecutor = Executors.newFixedThreadPool(10);

    public CompletableFuture<Message> filterMessageAsync(Message message) {
        return CompletableFuture.supplyAsync(() -> {
            String content = message.getContent();

            if (wordFilter.containsSensitiveWord(content)) {
                // 实时替换
                String filtered = wordFilter.filter(content, "***");
                message.setContent(filtered);
                // 记录统计，用于优化词库
                recordSensitiveWords(content);
            }
            return message;
        }, filterExecutor);
    }

    private void recordSensitiveWords(String content) {
        List<SensitiveWordResult> words = wordFilter.findAllWords(content);
        // 更新敏感词频率统计...
    }
}

场景二：内容审核系统的多级处理策略

对不同风险等级的词汇采取不同措施。

public class ContentAuditor {
    private SensitiveWordFilter highRiskFilter;  // 高风险词
    private SensitiveWordFilter mediumRiskFilter;// 中风险词
    private SensitiveWordFilter lowRiskFilter;   // 低风险词

    public AuditResult auditContent(String content) {
        AuditResult result = new AuditResult();

        // 按风险级别逐级检测
        List<SensitiveWordResult> highRiskWords = highRiskFilter.findAllWords(content);
        if (!highRiskWords.isEmpty()) {
            result.setStatus(AuditStatus.REJECT);
            result.setReason("包含高风险敏感词");
            return result;
        }

        List<SensitiveWordResult> mediumRiskWords = mediumRiskFilter.findAllWords(content);
        if (!mediumRiskWords.isEmpty()) {
            result.setStatus(AuditStatus.MANUAL_REVIEW);
            result.setReason("包含中风险敏感词，需要人工审核");
            return result;
        }

        List<SensitiveWordResult> lowRiskWords = lowRiskFilter.findAllWords(content);
        if (!lowRiskWords.isEmpty()) {
            // 低风险词直接替换
            String filtered = lowRiskFilter.filter(content, "***");
            result.setFilteredContent(filtered);
            result.setStatus(AuditStatus.PASS_WITH_FILTER);
        } else {
            result.setStatus(AuditStatus.PASS);
        }
        return result;
    }
}

场景三：动态词库管理与 SpringBoot 集成

词库需要支持热更新。

@Service
public class SensitiveWordManager {
    private volatile SensitiveWordFilter filter;
    private ScheduledExecutorService updateExecutor =
        Executors.newSingleThreadScheduledExecutor();

    @PostConstruct
    public void init() {
        loadWords();
        // 每小时定期更新词库
        updateExecutor.scheduleAtFixedRate(this::loadWords, 0, 1, TimeUnit.HOURS);
    }

    public void loadWords() {
        try {
            // 从数据库、配置中心或文件加载最新词库
            List<String> words = fetchLatestWords();
            SensitiveWordFilter newFilter = new SensitiveWordFilter(words);
            this.filter = newFilter; // 原子性替换
            log.info("敏感词库更新完成，当前词数：{}", words.size());
        } catch (Exception e) {
            log.error("词库更新失败", e);
        }
    }

    public boolean containsSensitiveWord(String text) {
        return filter != null && filter.containsSensitiveWord(text);
    }

    public String filterText(String text) {
        return filter != null ? filter.filter(text, "***") : text;
    }
}

在 application.yml 中配置词库路径：

sensitive-word:
  file-path: classpath:sensitive-words.txt
  reload-interval: 3600

高级优化方案选型

对于超大规模或特殊场景，基础 DFA 可以进一步优化。

方案1：双数组 Trie (Double-Array Trie)

• 核心：将 Trie 树压缩为 base 和 check 两个数组，极大减少内存占用。
• 优点：内存利用率极高，查询速度极快。
• 缺点：构建算法复杂，动态更新困难。
• 适用：词库巨大且变动不频繁的离线场景。

方案2：AC 自动机 (Aho-Corasick)

• 核心：在 Trie 树上增加失败指针，实现一次扫描匹配所有模式串。
• 优点：多模式匹配的经典算法，功能强大。
• 缺点：空间开销稍大，实现比基础 DFA 复杂。
• 适用：需要同时检测大量敏感词，或敏感词之间存在包含关系。

方案3：分片 + 布隆过滤器预筛选

• 核心：通过文本哈希进行分片，分散压力；用布隆过滤器快速排除肯定不包含敏感词的请求。
• 优点：支持水平扩展，能应对超高并发。
• 缺点：系统架构变复杂，布隆过滤器有误判率。
• 适用：分布式、微服务架构下的海量文本处理系统。

总结

DFA 算法凭借其 O(n) 的线性时间复杂度和高效的前缀共享能力，为敏感词过滤提供了一个近乎完美的解决方案。从简单的 Trie 树实现到集成到 SpringBoot 项目中，我们看到了它如何从理论走向实践，支撑起实时聊天、内容审核等关键业务。

选择哪种实现和优化方案，最终取决于你的具体业务场景、词库规模、性能要求和技术栈。希望本文的讲解和代码示例能为你构建自己的敏感词过滤系统提供扎实的算法/数据结构基础。技术之路，常学常新，欢迎到 云栈社区 交流讨论更多后端 & 架构与 Java 开发实践。

本文示例完整代码仓库：

https://github.com/yuboon/java-examples/tree/master/springboot-dfa