[Java] Java实现高效敏感词过滤：基于SpringBoot与DFA（Trie树）算法详解

敏感词过滤是保障内容安全的核心功能，广泛应用于社交内容审核、电商商品管理与游戏聊天监控等场景。面对海量文本，传统的字符串暴力匹配与正则表达式方案在性能与扩展性上存在明显瓶颈。

本文将深入介绍一种基于DFA（确定有限状态自动机） 算法的高效解决方案，利用 Trie树（前缀树） 数据结构，可实现毫秒级的文本过滤响应，轻松满足实时业务需求。

传统方案的性能瓶颈

在真实的业务场景中，早期的敏感词过滤实现常面临以下挑战：

❌ 暴力匹配效率低下

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

当敏感词库规模达到数千甚至数万时，对一篇千字文章进行检测可能耗时数秒，严重影响用户体验。

❌ 正则表达式的局限性

尽管正则表达式功能强大，但在本场景中却显不足：

• 构建庞大的正则表达式会导致编译时间过长。
• 动态增减敏感词需要重新编译整个表达式。
• 内存占用与敏感词数量呈线性增长。
• 复杂规则下的匹配效率会显著下降。

DFA算法的核心优势

DFA算法通过构建状态机模型，将匹配过程转化为确定性的状态转移，带来质的提升：

• 线性时间复杂度：仅需一次文本遍历（O(n)），不受敏感词数量影响。
• 空间共享优化：利用前缀共享存储，极大减少内存占用。
• 确定性匹配：无回溯开销，匹配路径唯一。
• 动态扩展友好：支持运行时增删敏感词，无需重构整个数据结构。

以实际数据为例，当词库从1000个扩展到10000个时：

• 暴力匹配耗时增加约10倍。
• DFA算法耗时几乎保持不变。

DFA算法原理与Trie树结构

DFA（Deterministic Finite Automaton）是一个五元组数学模型 M = (Q, Σ, δ, q₀, F)。在敏感词过滤中，Trie树是其最直观的实现方式。

假设有敏感词集：["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" 作为多个词的公共前缀，只存储一次。
2. 状态节点：每个字符节点代表DFA的一个状态。
3. 接受状态：标记为 [结束] 的节点表示一个完整敏感词。
4. 高效查找：查找 "application" 仅需11次字符比较。

匹配过程示例（文本：“I like apples”）：

• 从根开始，输入 'a' -> 'p' -> 'p' -> 'l' -> 'e'。
• 到达 'e'（接受状态），成功匹配敏感词 "apple"。

核心实现：从Trie节点到完整过滤器

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 and 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 and toString...
}

实战应用场景

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

在 即时通讯 等场景中，要求低延迟、高吞吐。

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);
    }
}

场景二：内容审核系统的分级策略

根据敏感词风险级别采取不同处理方式。

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

    public AuditResult auditContent(String content) {
        AuditResult result = new AuditResult();
        // 按风险级别分级检测
        if (!highRiskFilter.findAllWords(content).isEmpty()) {
            result.setStatus(AuditStatus.REJECT);
            return result;
        }
        // ... 中低风险处理逻辑
        return result;
    }
}

场景三：支持动态更新的词库管理

在实际项目中，词库需要支持热更新。

@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();
            this.filter = new SensitiveWordFilter(words);
        } catch (Exception e) {
            log.error("词库更新失败", e);
        }
    }
}

高级优化方案

面对更大规模或更复杂的场景，基础的DFA算法可以进一步演进。

1. 双数组Trie（Double-Array Trie）

核心思想：将Trie树压缩为base和check两个数组，极大减少内存占用。
适用场景：词库规模极大且相对静态，如搜索引擎词库。
优点：内存占用可减少50%-80%。
缺点：构建复杂，动态更新困难。

2. AC自动机（Aho-Corasick）

核心思想：在Trie树上增加失败指针，实现一次遍历文本即可匹配所有模式词。
适用场景：需要同时匹配海量模式（如病毒特征码、多关键词）。
优点：多模式匹配效率极致。
缺点：空间复杂度高，实现更复杂。

3. 分片与布隆过滤器预筛选

核心思想：在 微服务架构 下，通过分片分散压力，并用布隆过滤器快速排除绝不可能包含敏感词的请求。
适用场景：超高并发系统，如全民级的弹幕或聊天系统。
优点：支持水平扩展，预处理层过滤大量请求。
缺点：系统复杂度增加，布隆过滤器有误判率。

总结

DFA算法结合Trie树数据结构，为敏感词过滤问题提供了效率与准确性兼备的解决方案。开发者可根据自身业务规模（词库大小、并发量）和场景特点（是否需要动态更新、分级审核），选择基础实现或高级优化方案。该方案是构建健康内容生态的强大技术基石。

示例仓库

完整的可运行代码示例可在以下仓库查看：
https://github.com/yuboon/java-examples/tree/master/springboot-dfa