Java DFA算法-开发者社区

DFA（Deterministic Finite Automaton，确定性有限自动机）是一种常用的算法模型，在Java中广泛应用于敏感词过滤、字符串匹配、词法分析等场景。它的核心特点是：每个状态对于同一个输入字符，有且只有一个转移状态。

基本原理

DFA算法通过构建一个状态转移图（通常用嵌套Map或数组表示）来快速匹配关键词。相比于简单遍历匹配，时间复杂度为O(n)，n为待匹配文本长度，与关键词数量无关。

Java实现示例

1. 构建DFA节点模型

import java.util.*; public class DFAFilter { // 根节点 private Map<Character, Object> rootNode = new HashMap<>(); // 敏感词结束标识 private static final String END_FLAG = "isEnd"; /** * 添加关键词到DFA中 * @param keyword 关键词 */ public void addKeyword(String keyword) { if (keyword == null || keyword.isEmpty()) return; Map<Character, Object> currentMap = rootNode; for (int i = 0; i < keyword.length(); i++) { char c = keyword.charAt(i); // 获取下一层节点 Map<Character, Object> nextMap = (Map<Character, Object>) currentMap.get(c); if (nextMap == null) { nextMap = new HashMap<>(); currentMap.put(c, nextMap); } currentMap = nextMap; // 最后一个字符标记结束 if (i == keyword.length() - 1) { currentMap.put(END_FLAG, true); } } } /** * 批量添加关键词 */ public void addKeywords(List<String> keywords) { for (String keyword : keywords) { addKeyword(keyword); } } }

2. 匹配敏感词

/** * 检查文本是否包含敏感词，并返回第一个匹配的敏感词 */ public String check(String text) { if (text == null || text.isEmpty()) return null; for (int i = 0; i < text.length(); i++) { int matchCount = 0; Map<Character, Object> currentMap = rootNode; char c; for (int j = i; j < text.length(); j++) { c = text.charAt(j); currentMap = (Map<Character, Object>) currentMap.get(c); if (currentMap == null) { break; // 匹配失败，重新从下一个字符开始 } matchCount++; // 检查是否匹配到完整关键词 if (currentMap.containsKey(END_FLAG)) { return text.substring(i, i + matchCount); } } } return null; } /** * 替换文本中的敏感词 * @param text 原始文本 * @param replaceChar 替换字符 * @return 替换后的文本 */ public String replace(String text, char replaceChar) { if (text == null || text.isEmpty()) return text; StringBuilder result = new StringBuilder(text); List<int[]> positions = new ArrayList<>(); for (int i = 0; i < text.length(); i++) { int matchCount = 0; Map<Character, Object> currentMap = rootNode; char c; for (int j = i; j < text.length(); j++) { c = text.charAt(j); currentMap = (Map<Character, Object>) currentMap.get(c); if (currentMap == null) break; matchCount++; if (currentMap.containsKey(END_FLAG)) { positions.add(new int[]{i, i + matchCount}); i = i + matchCount - 1; // 跳过已匹配部分 break; } } } // 执行替换 for (int[] pos : positions) { for (int i = pos[0]; i < pos[1]; i++) { result.setCharAt(i, replaceChar); } } return result.toString(); }

3. 完整示例

public class DFATest { public static void main(String[] args) { DFAFilter filter = new DFAFilter(); // 添加敏感词 filter.addKeywords(Arrays.asList( "色情", "暴力", "赌博", "毒品", "法轮功" )); // 测试文本 String text = "这个网站包含色情和暴力内容，还有赌博信息。"; // 检查敏感词 String sensitive = filter.check(text); System.out.println("检测到敏感词: " + sensitive); // 替换敏感词 String filtered = filter.replace(text, '*'); System.out.println("过滤后: " + filtered); } } 输出： 检测到敏感词: 色情 过滤后: 这个网站包含**和**内容，还有**信息。

优化版本：支持跳过特殊字符

/** * 增强版：支持忽略特殊字符（如空格、标点） */ public class AdvancedDFAFilter { private Map<Character, Object> rootNode = new HashMap<>(); private static final String END_FLAG = "isEnd"; // 忽略字符集合（空格、标点符号等） private Set<Character> ignoreChars = new HashSet<>( Arrays.asList(' ', ',', '.', '!', '?', ';', ':', '、', '，', '。', '！', '？') ); public void addKeyword(String keyword) { Map<Character, Object> currentMap = rootNode; for (char c : keyword.toCharArray()) { currentMap = (Map<Character, Object>) currentMap.computeIfAbsent( c, k -> new HashMap<>() ); } currentMap.put(END_FLAG, true); } public String check(String text) { for (int i = 0; i < text.length(); i++) { int matchCount = 0; Map<Character, Object> currentMap = rootNode; for (int j = i; j < text.length(); j++) { char c = text.charAt(j); // 跳过忽略字符 if (ignoreChars.contains(c)) { continue; } currentMap = (Map<Character, Object>) currentMap.get(c); if (currentMap == null) break; matchCount++; if (currentMap.containsKey(END_FLAG)) { return text.substring(i, j + 1); } } } return null; } }