使用 Java 实现基于 DFA 算法的敏感词检测

使用 Java 实现基于 DFA 算法的敏感词检测

1. 引言

敏感词检测在内容审核、信息过滤等领域有着广泛的应用。本文将介绍如何使用 DFA（Deterministic Finite Automaton，确定有限状态自动机） 算法，在 Java 中实现高效的敏感词检测。

2. DFA 算法简介

DFA（确定有限状态自动机）是一种用于字符串匹配的高效算法。它的核心思想是将多个敏感词组织成一棵状态机，在匹配过程中避免重复扫描，提升检测速度。

DFA 的构建分为两个阶段：

1. 构建状态机（即DFA树）：将敏感词列表逐字构建成一个树形结构，每个字符对应一个节点，单词的结束位置标记为终止状态。
2. 文本匹配：使用状态机遍历输入文本，遇到匹配字符时进入下一个状态，直到匹配完整的敏感词。
   

DFA 的优点在于匹配时的时间复杂度是 O(n)，即文本长度的线性时间，适用于高性能需求的敏感词检测。

3. Java 实现 DFA 敏感词检测

3.1 定义 DFA 结构

import java.util.HashMap;
import java.util.Map;
import java.util.Set;public class SensitiveWordNode {private boolean isEnd;private Map<Character, SensitiveWordNode> children;public SensitiveWordNode() {this.isEnd = false;this.children = new HashMap<>();}public void addChild(Character c) {children.putIfAbsent(c, new SensitiveWordNode());}public SensitiveWordNode getChild(Character c) {return children.get(c);}public boolean isEnd() {return isEnd;}public void setEnd(boolean end) {isEnd = end;}
}

3.2 构建 DFA 敏感词树

public class SensitiveWordDFA {private SensitiveWordNode root;public SensitiveWordDFA(Set<String> sensitiveWords) {root = new SensitiveWordNode();for (String word : sensitiveWords) {insertWord(word);}}private void insertWord(String word) {SensitiveWordNode node = root;for (char c : word.toCharArray()) {node.addChild(c);node = node.getChild(c);}node.setEnd(true);}// 最小检测模式（检测到一个敏感词就返回）public boolean containsSensitiveWord(String text) {for (int i = 0; i < text.length(); i++) {SensitiveWordNode node = root;for (int j = i; j < text.length(); j++) {node = node.getChild(text.charAt(j));if (node == null) {break;}if (node.isEnd()) {return true;}}}return false;}// 最大检测模式（返回所有匹配的敏感词）public Set<String> findAllSensitiveWords(String text) {Set<String> result = new HashSet<>();for (int i = 0; i < text.length(); i++) {SensitiveWordNode node = root;StringBuilder wordBuffer = new StringBuilder();for (int j = i; j < text.length(); j++) {node = node.getChild(text.charAt(j));if (node == null) {break;}wordBuffer.append(text.charAt(j));if (node.isEnd()) {result.add(wordBuffer.toString());}}}return result;}
}

3.3 测试 DFA

import java.util.HashSet;
import java.util.Set;public class SensitiveWordTest {public static void main(String[] args) {Set<String> sensitiveWords = new HashSet<>();sensitiveWords.add("敏感");sensitiveWords.add("违规");SensitiveWordDFA dfa = new SensitiveWordDFA(sensitiveWords);String text1 = "这是一条包含敏感内容的文本";String text2 = "这是一条正常文本";System.out.println("文本1是否包含敏感词: " + dfa.containsSensitiveWord(text1));System.out.println("文本2是否包含敏感词: " + dfa.containsSensitiveWord(text2));String text3 = "这条信息涉及违规行为和敏感内容";System.out.println("文本3包含的敏感词: " + dfa.findAllSensitiveWords(text3));}
}

4. 优化方向

• 支持动态添加敏感词，避免重新构建 DFA。
• 增加敏感词替换功能，将匹配到的敏感词替换为 * 或其他符号。
• 使用 AC 自动机，进一步提高匹配效率。

5. 结论

本文介绍了 DFA（确定有限状态自动机） 的基本原理，并使用 Java 进行了敏感词检测的实现。DFA 具备 高效、可扩展 的特点，适用于大规模敏感词匹配场景。希望对你有所帮助！

阅读原文

原文连接