dfa java实现

在Java中实现DFA（确定有限状态自动机）算法，可以通过以下几个步骤来完成，以下是一个详细的实现过程：

一、定义数据结构

1、状态节点类

创建一个StateNode类来表示DFA中的每个状态节点，该类包含一个布尔类型的isEnd字段，用于标记该状态是否为某个敏感词的结束状态；一个Map<Character, StateNode>类型的nextStates字段，用于存储从当前状态出发，根据输入字符可以到达的下一个状态。

示例代码如下：

     class StateNode {
         boolean isEnd;
         Map<Character, StateNode> nextStates;
         public StateNode() {
             this.isEnd = false;
             this.nextStates = new HashMap<>();
         }
     }

2、DFA类

创建一个DFA类来封装DFA的相关操作和数据，该类包含一个StateNode类型的root字段，表示DFA的初始状态；一个List<String> sensitiveWords字段，用于存储敏感词列表，以便构建DFA的状态转换图。

示例代码如下：

     import java.util.;
     public class DFA {
         private StateNode root;
         private List<String> sensitiveWords;
         public DFA(List<String> sensitiveWords) {
             this.sensitiveWords = sensitiveWords;
             this.root = new StateNode();
             buildDFA();
         }
         private void buildDFA() {
             for (String word : sensitiveWords) {
                 StateNode currentNode = root;
                 for (char c : word.toCharArray()) {
                     currentNode = currentNode.nextStates.computeIfAbsent(c, k -> new StateNode());
                 }
                 currentNode.isEnd = true;
             }
         }
         public boolean isSensitive(String text) {
             StateNode currentNode = root;
             for (char c : text.toCharArray()) {
                 currentNode = currentNode.nextStates.getOrDefault(c, null);
                 if (currentNode == null) {
                     return false;
                 }
                 if (currentNode.isEnd) {
                     return true;
                 }
             }
             return false;
         }
     }

二、构建DFA状态转换图

1、遍历敏感词列表

在DFA类的构造函数中，调用buildDFA方法来构建DFA的状态转换图，该方法遍历敏感词列表sensitiveWords，对于每个敏感词，从DFA的初始状态root开始，逐个字符地构建状态转换路径，如果当前字符对应的下一个状态不存在，则创建一个新的StateNode对象并添加到当前状态的nextStates映射中，将最后一个字符对应的状态标记为结束状态（isEnd=true）。

三、使用DFA进行敏感词检测

1、检测方法

DFA类中的isSensitive方法用于检测输入的文本中是否包含敏感词，该方法接收一个字符串参数text，表示要检测的文本，它从DFA的初始状态root开始，逐个字符地遍历文本，对于每个字符，根据当前状态的nextStates映射找到下一个状态，如果在遍历过程中遇到null，说明文本中出现了不在DFA状态转换图中的字符序列，因此可以直接返回false，如果在遍历过程中遇到一个结束状态（isEnd=true），说明找到了一个敏感词，立即返回true，如果遍历完整个文本都没有找到敏感词，则返回false。

四、示例代码整合与测试

1、整合代码

将上述定义的数据结构和方法整合到一个完整的Java程序中，并进行测试，以下是完整的示例代码：

     import java.util.;
     class StateNode {
         boolean isEnd;
         Map<Character, StateNode> nextStates;
         public StateNode() {
             this.isEnd = false;
             this.nextStates = new HashMap<>();
         }
     }
     public class DFA {
         private StateNode root;
         private List<String> sensitiveWords;
         public DFA(List<String> sensitiveWords) {
             this.sensitiveWords = sensitiveWords;
             this.root = new StateNode();
             buildDFA();
         }
         private void buildDFA() {
             for (String word : sensitiveWords) {
                 StateNode currentNode = root;
                 for (char c : word.toCharArray()) {
                     currentNode = currentNode.nextStates.computeIfAbsent(c, k -> new StateNode());
                 }
                 currentNode.isEnd = true;
             }
         }
         public boolean isSensitive(String text) {
             StateNode currentNode = root;
             for (char c : text.toCharArray()) {
                 currentNode = currentNode.nextStates.getOrDefault(c, null);
                 if (currentNode == null) {
                     return false;
                 }
                 if (currentNode.isEnd) {
                     return true;
                 }
             }
             return false;
         }
         public static void main(String[] args) {
             List<String> sensitiveWords = Arrays.asList("敏感词1", "敏感词2", "敏感词3");
             DFA dfa = new DFA(sensitiveWords);
             String testText1 = "这是一个测试文本，不包含敏感词";
             String testText2 = "这个文本包含敏感词1";
             System.out.println(dfa.isSensitive(testText1)); // 输出: false
             System.out.println(dfa.isSensitive(testText2)); // 输出: true
         }
     }

2、运行结果

运行上述代码，可以看到对于不包含敏感词的文本testText1，输出为false；对于包含敏感词的文本testText2，输出为true，这表明我们的DFA实现能够正确地检测出文本中的敏感词。

通过以上步骤，可以在Java中实现一个基本的DFA算法来进行敏感词检测，实际应用中可能需要根据具体需求对算法进行优化和扩展，例如处理大小写敏感、添加更多的敏感词等。