DFA 敏感词过滤算法：O(N) 匹配效率的工程实践（附完整 Java 实现）

作者：忆笙智云官方 ｜ 发布时间：2026-05-04 10:00 ｜ 更新时间：2026-06-04 10:00

DFA算法在敏感词过滤中的应用

引言

在UGC（用户生成内容）平台中，敏感词过滤是内容安全的第一道防线。面对海量文本和庞大的敏感词库，如何实现高效的实时过滤是一个核心工程问题。

暴力匹配（逐词遍历词库）的时间复杂度为O(M×N)，当词库达到十万级别时，性能急剧下降。DFA（Deterministic Finite Automaton，确定性有限自动机）算法通过将词库预处理为字典树，将匹配时间复杂度降至O(N)，是目前工业界最主流的敏感词过滤方案。

一、DFA算法原理

1.1 什么是DFA

DFA是一种计算模型，由有限个状态和状态之间的转移组成。在敏感词过滤场景中，每个字符对应一个状态转移，从初始状态出发，沿着输入文本逐字符前进，如果到达某个终态，就匹配到了一个敏感词。

1.2 字典树（Trie）结构

DFA的核心数据结构是字典树（又称前缀树、Trie树）。将敏感词库构建为字典树后，每个节点代表一个字符，从根节点到某个节点的路径对应一个词的前缀。

graph TB
    ROOT[Root] --> A["敏"]
    ROOT --> B["违"]
    ROOT --> C["禁"]

    A --> A1["感"]
    A1 --> A2["词"]
    A2 --> A3["*** END"]

    B --> B1["规"]
    B1 --> B2["内"]
    B2 --> B3["容"]
    B3 --> B4["*** END"]

    C --> C1["词"]
    C1 --> C2["*** END"]

    style ROOT fill:#e8f4f8
    style A3 fill:#f9d5d5
    style B4 fill:#f9d5d5
    style C2 fill:#f9d5d5

上图中，*** END标记表示从根节点到此节点的路径构成一个完整的敏感词。字典树的关键特性：

1.3 时间复杂度分析

方法 预处理 匹配 空间
暴力遍历 O(1) O(M×N) O(M)
正则匹配 O(M) O(M×N)最坏 O(M)
DFA/Trie O(M×L) O(N) O(M×L)
AC自动机 O(M×L) O(N+K) O(M×L)

M=词库大小，N=文本长度，L=平均词长，K=匹配结果数

DFA的匹配时间与词库大小无关，仅与文本长度成正比，这是其核心优势。

二、字典树构建

2.1 数据结构设计

/**
 * DFA字典树节点
 * 每个节点包含一个字符映射表，指向下一级节点
 * isEnd标记表示当前路径是否构成一个完整的敏感词
 */
public class DfaNode {

    /** 是否为词尾节点（完整敏感词的结束） */
    private boolean isEnd = false;

    /** 子节点映射：字符 -> 子节点 */
    private final Map<Character, DfaNode> children = new HashMap<>();

    /**
     * 添加子节点
     * @param ch 字符
     * @return 对应的子节点（已存在则返回已有节点）
     */
    public DfaNode addChild(char ch) {
        return children.computeIfAbsent(ch, k -> new DfaNode());
    }

    /**
     * 获取子节点
     * @param ch 字符
     * @return 子节点，不存在返回null
     */
    public DfaNode getChild(char ch) {
        return children.get(ch);
    }

    public boolean isEnd() {
        return isEnd;
    }

    public void setEnd(boolean end) {
        isEnd = end;
    }
}

2.2 构建字典树

/**
 * DFA敏感词过滤器
 * 将敏感词库构建为字典树，提供高效匹配能力
 */
@Component
public class SensitiveWordFilter {

    /** 字典树根节点 */
    private DfaNode root = new DfaNode();

    /** 敏感词最小匹配长度 */
    private static final int MIN_MATCH_LENGTH = 2;

    /**
     * 初始化敏感词库，构建字典树
     * @param sensitiveWords 敏感词集合
     */
    public void initSensitiveWordMap(Set<String> sensitiveWords) {
        // 重建字典树（支持热更新）
        DfaNode newRoot = new DfaNode();

        for (String word : sensitiveWords) {
            if (word == null || word.trim().length() < MIN_MATCH_LENGTH) {
                continue;
            }
            DfaNode currentNode = newRoot;
            for (char ch : word.toCharArray()) {
                currentNode = currentNode.addChild(ch);
            }
            currentNode.setEnd(true);  // 标记词尾
        }

        // 原子替换，保证线程安全
        this.root = newRoot;
    }

    /**
     * 添加单个敏感词
     * @param word 敏感词
     */
    public void addWord(String word) {
        if (word == null || word.trim().length() < MIN_MATCH_LENGTH) {
            return;
        }
        DfaNode currentNode = root;
        for (char ch : word.toCharArray()) {
            currentNode = currentNode.addChild(ch);
        }
        currentNode.setEnd(true);
    }
}

三、敏感词匹配算法

3.1 匹配流程

flowchart TB
    A[输入文本] --> B[遍历文本每个字符]
    B --> C{当前字符在字典树中?}
    C -->|否| D[重置到根节点，移动主指针]
    C -->|是| E[移动到子节点]
    E --> F{当前节点是词尾?}
    F -->|否| G{还有下一字符?}
    G -->|是| B
    G -->|否| H[结束匹配]
    F -->|是| I[记录匹配到的敏感词]
    I --> J{继续检查更长匹配?}
    J -->|是| G
    J -->|否| K[重置到根节点，移动主指针]
    K --> G
    D --> G

    style I fill:#f9d5d5
    style H fill:#d5f9d5

3.2 最小匹配与最大匹配

/**
 * 匹配模式枚举
 */
public enum MatchType {
    /** 最小匹配：匹配到最短的敏感词即返回 */
    MIN_MATCH,
    /** 最大匹配：尽可能匹配最长的敏感词 */
    MAX_MATCH
}

/**
 * 检测文本中是否包含敏感词
 * @param text 待检测文本
 * @param matchType 匹配模式
 * @return 是否包含敏感词
 */
public boolean contains(String text, MatchType matchType) {
    if (text == null || text.isEmpty()) {
        return false;
    }
    for (int i = 0; i < text.length(); i++) {
        int matchLength = checkSensitiveWord(text, i, matchType);
        if (matchLength > 0) {
            return true;
        }
    }
    return false;
}

/**
 * 从指定位置开始检测敏感词
 * @param text 文本
 * @param startIndex 起始索引
 * @param matchType 匹配模式
 * @return 匹配到的敏感词长度，0表示未匹配
 */
private int checkSensitiveWord(String text, int startIndex, MatchType matchType) {
    int matchLength = 0;
    DfaNode currentNode = root;
    char ch;

    for (int i = startIndex; i < text.length(); i++) {
        ch = text.charAt(i);
        DfaNode node = currentNode.getChild(ch);
        if (node == null) {
            break;  // 字典树中无此路径，匹配失败
        }
        matchLength++;
        currentNode = node;

        if (node.isEnd()) {
            if (matchType == MatchType.MIN_MATCH) {
                break;  // 最小匹配模式，匹配到即返回
            }
            // 最大匹配模式，继续尝试匹配更长的词
        }
    }

    // 如果匹配长度小于2或未到达词尾，视为未匹配
    if (matchLength < MIN_MATCH_LENGTH || !currentNode.isEnd()) {
        matchLength = 0;
    }

    return matchLength;
}

3.3 获取所有敏感词

/**
 * 获取文本中的所有敏感词
 * @param text 待检测文本
 * @param matchType 匹配模式
 * @return 敏感词列表（包含重复出现的词）
 */
public Set<String> getSensitiveWords(String text, MatchType matchType) {
    Set<String> sensitiveWords = new LinkedHashSet<>();
    if (text == null || text.isEmpty()) {
        return sensitiveWords;
    }

    for (int i = 0; i < text.length(); i++) {
        int matchLength = checkSensitiveWord(text, i, matchType);
        if (matchLength > 0) {
            String word = text.substring(i, i + matchLength);
            sensitiveWords.add(word);
            // 跳过已匹配的部分（避免重复检测）
            if (matchType == MatchType.MAX_MATCH) {
                i += matchLength - 1;
            }
        }
    }
    return sensitiveWords;
}

四、敏感词替换策略

4.1 替换实现

/**
 * 敏感词替换策略
 */
public enum ReplaceStrategy {
    /** 星号替换 */
    STAR,
    /** 自定义字符替换 */
    CUSTOM_CHAR,
    /** 整词替换为指定文本 */
    REPLACE_WORD
}

/**
 * 替换文本中的敏感词
 * @param text 原始文本
 * @param replaceChar 替换字符（如'*'）
 * @param matchType 匹配模式
 * @return 替换后的文本
 */
public String replaceSensitiveWord(String text, char replaceChar,
                                   MatchType matchType) {
    if (text == null || text.isEmpty()) {
        return text;
    }

    StringBuilder result = new StringBuilder(text);
    for (int i = 0; i < result.length(); i++) {
        int matchLength = checkSensitiveWord(result.toString(), i, matchType);
        if (matchLength > 0) {
            // 将敏感词的每个字符替换为指定字符
            for (int j = i; j < i + matchLength; j++) {
                result.setCharAt(j, replaceChar);
            }
            if (matchType == MatchType.MAX_MATCH) {
                i += matchLength - 1;
            }
        }
    }
    return result.toString();
}

4.2 替换效果示例

输入: "这篇文章包含违规内容和敏感词"
输出: "这篇文章包含****内容和***"

输入: "请勿发布违禁词语"
输出: "请勿发布**词语"

五、优化与增强

5.1 忽略特殊字符

攻击者常通过插入特殊字符绕过过滤（如"敏感词"），需要预处理：

/**
 * 文本预处理器
 * 去除干扰字符，统一全半角
 */
public class TextPreprocessor {

    /** 需要忽略的干扰字符集合 */
    private static final Set<Character> IGNORE_CHARS = Set.of(
        ' ', '*', '.', '-', '_', '|', '@', '#', '$', '%', '&'
    );

    /**
     * 预处理文本
     * 1. 去除干扰字符
     * 2. 全角转半角
     * 3. 英文统一小写
     */
    public static String preprocess(String text) {
        StringBuilder sb = new StringBuilder();
        for (char ch : text.toCharArray()) {
            // 跳过干扰字符
            if (IGNORE_CHARS.contains(ch)) {
                continue;
            }
            // 全角转半角
            if (ch >= 0xFF01 && ch <= 0xFF5E) {
                ch = (char) (ch - 0xFEE0);
            }
            // 英文转小写
            if (ch >= 'A' && ch <= 'Z') {
                ch = (char) (ch + 32);
            }
            sb.append(ch);
        }
        return sb.toString();
    }
}

5.2 白名单机制

/**
 * 敏感词白名单
 * 白名单中的词不会被过滤
 */
@Component
public class SensitiveWordWhitelist {

    private Set<String> whitelist = new HashSet<>();

    /**
     * 初始化白名单
     */
    public void initWhitelist(Set<String> words) {
        this.whitelist = new HashSet<>(words);
    }

    /**
     * 判断是否在白名单中
     */
    public boolean isWhitelisted(String word) {
        return whitelist.contains(word);
    }
}

六、整体架构

flowchart TB
    A[用户提交内容] --> B[文本预处理]
    B --> C[全角转半角/去干扰字符/统一小写]
    C --> D[DFA字典树匹配]
    D --> E{检测到敏感词?}
    E -->|否| F[内容正常放行]
    E -->|是| G{在白名单中?}
    G -->|是| F
    G -->|否| H[记录过滤日志]
    H --> I[执行替换/拦截策略]
    I --> J[返回处理后的内容]

    subgraph 字典树维护
        K[敏感词库] --> L[构建DFA字典树]
        L --> M[热更新支持]
        M --> D
    end

    style F fill:#d5f9d5
    style I fill:#f9d5d5

结论与建议

核心优势

  1. O(N)匹配效率：匹配时间仅与文本长度相关，与词库大小无关
  2. 内存可控：字典树共享前缀，十万级词库内存占用约50-100MB
  3. 实时性好：单次文本过滤耗时在毫秒级

实践建议

  1. 词库热更新：字典树构建采用"构建-替换"策略，避免更新期间服务中断
  2. 多级过滤：DFA做第一层快速过滤，AI模型做第二层语义理解，两者互补
  3. 日志审计：记录所有过滤事件，用于后续分析和词库优化
  4. 性能监控：监控过滤耗时，当词库增大导致性能下降时及时优化
  5. 繁简转换：对繁体中文场景，需先将繁体转简体再匹配

局限性

相关资源

本文来自 忆笙智云技术社区，查看完整互动内容请访问 原帖页面。

© 忆笙智云 https://yscode.cn（皖ICP备2026018240号-1）