DFA算法简单理解实现

大家好，又见面了，我是你们的朋友全栈君。

背景：因为最近项目要使用到敏感词过滤服务，在网上了解到dfa实现这个功能性能还不错，特此学习了一下

1. 什么是DFA算法

引用简书作者：浪人与酒丶的解释
原文链接：https://www.jianshu.com/p/c67f917c9363

DFA全称为：Deterministic Finite Automaton,即确定有穷自动机。其特征为：有一个有限状态集合和一些从一个状态通向另一个状态的边，每条边上标记有一个符号，其中一个状态是初态，某些状态是终态。但不同于不确定的有限自动机，DFA中不会有从同一状态出发的两条边标志有相同的符号。
确定：状态以及引起状态转换的事件都是可确定的，不存在“意外”。
有穷：状态以及事件的数量都是可穷举的。

2. DFA算法模型

state_event_dict = { 
   
    "匹": { 
   
        "配": { 
   
            "算": { 
   
                "法": { 
   
                    "is_end": True
                },
                "is_end": False
            },
            "关": { 
   
                "键": { 
   
                    "词": { 
   
                        "is_end": True
                    },
                    "is_end": False
                },
                "is_end": False
            },
            "is_end": False
        },
        "is_end": False
    },
    "信": { 
   
        "息": { 
   
            "抽": { 
   
                "取": { 
   
                    "is_end": True
                },
                "is_end": False
            },
            "is_end": False
        },
        "is_end": False
    }
}

3. 通过java程序加载敏感词库，构建一个DFA算法模型

private static void addSensitiveWordToHashMap(Set<String> keyWordSet) { 
   
        // 初始化HashMap对象并控制容器的大小
        sensitiveWordMap = new HashMap(keyWordSet.size());
        // 敏感词
        String key = null;
        // 用来按照相应的格式保存敏感词库数据
        Map nowMap = null;
        // 用来辅助构建敏感词库
        Map<String, String> newWorMap = null;
        // 使用一个迭代器来循环敏感词集合
        Iterator<String> iterator = keyWordSet.iterator();
        while (iterator.hasNext()) { 
   
            key = iterator.next();
            nowMap = sensitiveWordMap;
            for (int i = 0; i < key.length(); i++) { 
   
                // 截取敏感词当中的字，在敏感词库中字为HashMap对象的Key键值
                char keyChar = key.charAt(i);

                // 判断这个字是否存在于敏感词库中
                Object wordMap = nowMap.get(keyChar);
                if (wordMap != null) { 
   
                    nowMap = (Map) wordMap;
                } else { 
   
                    newWorMap = new HashMap<>();
                    newWorMap.put("isEnd", "0");
                    nowMap.put(keyChar, newWorMap);
                    nowMap = newWorMap;
                }
                // 如果该字是当前敏感词的最后一个字，则标识为结尾字
                if (i == key.length() - 1) { 
   
                    nowMap.put("isEnd", "1");
                }

            }

        }
    }