Java DFA算法

张

张建站

2026/6/10 0:17:30

10分钟阅读

DFADeterministic Finite Automaton确定性有限自动机是一种常用的算法模型在Java中广泛应用于敏感词过滤、字符串匹配、词法分析等场景。它的核心特点是每个状态对于同一个输入字符有且只有一个转移状态。基本原理DFA算法通过构建一个状态转移图通常用嵌套Map或数组表示来快速匹配关键词。相比于简单遍历匹配时间复杂度为O(n)n为待匹配文本长度与关键词数量无关。Java实现示例1. 构建DFA节点模型import java.util.*; public class DFAFilter { // 根节点 private MapCharacter, 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; MapCharacter, Object currentMap rootNode; for (int i 0; i keyword.length(); i) { char c keyword.charAt(i); // 获取下一层节点 MapCharacter, Object nextMap (MapCharacter, 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(ListString 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; MapCharacter, Object currentMap rootNode; char c; for (int j i; j text.length(); j) { c text.charAt(j); currentMap (MapCharacter, 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); Listint[] positions new ArrayList(); for (int i 0; i text.length(); i) { int matchCount 0; MapCharacter, Object currentMap rootNode; char c; for (int j i; j text.length(); j) { c text.charAt(j); currentMap (MapCharacter, 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 MapCharacter, Object rootNode new HashMap(); private static final String END_FLAG isEnd; // 忽略字符集合空格、标点符号等 private SetCharacter ignoreChars new HashSet( Arrays.asList( , ,, ., !, ?, ;, :, 、, , 。, , ) ); public void addKeyword(String keyword) { MapCharacter, Object currentMap rootNode; for (char c : keyword.toCharArray()) { currentMap (MapCharacter, 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; MapCharacter, Object currentMap rootNode; for (int j i; j text.length(); j) { char c text.charAt(j); // 跳过忽略字符 if (ignoreChars.contains(c)) { continue; } currentMap (MapCharacter, Object) currentMap.get(c); if (currentMap null) break; matchCount; if (currentMap.containsKey(END_FLAG)) { return text.substring(i, j 1); } } } return null; } }性能优化建议使用数组代替HashMap当字符集有限如纯英文时可改用MapCharacter, Node或Node[] children数组内存优化使用char[]和int[]手动实现紧凑存储并行处理大文本可分片并行匹配缓存结果对于重复文本缓存匹配结果应用场景✅ 敏感词过滤系统✅ 垃圾邮件检测✅ SQL注入检测✅ 代码语法高亮✅ 正则表达式引擎底层实现DFA算法在Java中实现简单、性能优秀尤其适合需要高性能字符串匹配的场景相比之下比遍历关键词列表快很多。

如何永久保存微信聊天记录：WeChatMsg数据备份与年度报告生成完全指南

如何永久保存微信聊天记录：WeChatMsg数据备份与年度报告生成完全指南【免费下载链接】WeChatMsg 提取微信聊天记录，将其导出成HTML、Word、CSV文档永久保存，对聊天记录进行分析生成年度聊天报告项目地址: https://gitcode.com/GitHub_Tre…...

2026/6/9 23:44:56 阅读更多 →

ARM Cortex-M4与Kinetis K10低功耗嵌入式开发实战指南

1. 项目概述：为什么是K10与Cortex-M4？在嵌入式开发领域，选型往往决定了项目的天花板和地板。天花板是性能上限，地板则是功耗底线。当你的项目需要在实时控制、信号处理与超长续航之间找到平衡点时，基于ARM Cortex-M4内…...

2026/6/9 23:43:53 阅读更多 →

如何快速搭建高效音乐API服务器：LX Music Python版完整实战指南

如何快速搭建高效音乐API服务器：LX Music Python版完整实战指南【免费下载链接】lx-music-api-server-python 适用于 LX Music 的解析接口服务器的 Python 实现项目地址: https://gitcode.com/gh_mirrors/lx/lx-music-api-server-python 想要搭建自己的专属…...

2026/6/9 23:40:10 阅读更多 →

索引堆及其优化

索引堆及其优化引言索引堆是一种数据结构，广泛应用于计算机科学和软件工程领域。它主要用于解决优先队列问题，如最小堆和最大堆。本文将详细介绍索引堆的概念、实现方法以及优化策略。索引堆的定义索引堆是一种基于堆数据结构的索引机制。它通过维护一个堆来存储数据…...

2026/6/9 1:16:23 阅读更多 →

2026实测盘点｜适合国内高校生的AI写作平台，降重润色哪家强？

2026年毕业季，学术审查全面加码。教育部明确要求毕业论文AIGC率不得超过30%，985/211院校更是将红线压到了20%以内，硕士论文甚至卡到15%。与此同时，知网上线AIGC 3.0系统，可实现段落级内容溯源；维普引入语义…...

2026/6/9 19:20:02 阅读更多 →

JewelCraft：Blender珠宝设计的终极免费解决方案

JewelCraft：Blender珠宝设计的终极免费解决方案【免费下载链接】jewelcraft Blender add-on for jewelry design 项目地址: https://gitcode.com/gh_mirrors/je/jewelcraft JewelCraft是一款专为珠宝设计师和3D艺术家打造的Blender插件，提供完整…...

2026/6/9 1:16:30 阅读更多 →