2016年做网站能赚钱吗,西安抖音seo推广,wordpress修改域名,医疗网站建设公司何为DFA
DFA#xff0c;全称为Deterministic Finite Automaton#xff0c;即确定有穷自动机、确定有限状态自动机或确定有限自动机
对于一个给定的属于该自动机的状态和一个属于该自动机字母表Σ的字符#xff0c;它都能根据事先给定的转移函数转移到下一个状态#xff0…何为DFA
DFA全称为Deterministic Finite Automaton即确定有穷自动机、确定有限状态自动机或确定有限自动机
对于一个给定的属于该自动机的状态和一个属于该自动机字母表Σ的字符它都能根据事先给定的转移函数转移到下一个状态这个状态可以是先前那个状态)。
确定状态以及引起状态转换的事件都是可确定的不存在“意外”。
有穷状态以及事件的数量都是可穷举的。
简单来说就是存储字符串每个字符并判断到该字符为止是否属于敏感词
实现过程
存储一次性的把所有的敏感词存储到了多个map中就是下图表示这种结构
敏感词冰毒、大麻、大坏蛋 检索的过程 执行上面的过程就能匹配到内容中的敏感词了
代码实现 public static MapString, Object dictionaryMap new HashMap();/*** 生成关键词字典库* param words* return*/public static void initMap(CollectionString words) {if (words null) {System.out.println(敏感词列表不能为空);return ;}// map初始长度words.size()整个字典库的入口字数(小于words.size()因为不同的词可能会有相同的首字)MapString, Object map new HashMap(words.size());// 遍历过程中当前层次的数据MapString, Object curMap null;IteratorString iterator words.iterator();while (iterator.hasNext()) {String word iterator.next();curMap map;int len word.length();for (int i 0; i len; i) {// 遍历每个词的字String key String.valueOf(word.charAt(i));// 当前字在当前层是否存在, 不存在则新建, 当前层数据指向下一个节点, 继续判断是否存在数据MapString, Object wordMap (MapString, Object) curMap.get(key);if (wordMap null) {// 每个节点存在两个数据: 下一个节点和isEnd(是否结束标志)wordMap new HashMap(2);wordMap.put(isEnd, 0);curMap.put(key, wordMap);}curMap wordMap;// 如果当前字是词的最后一个字则将isEnd标志置1if (i len -1) {curMap.put(isEnd, 1);}}}dictionaryMap map;}/*** 搜索文本中某个文字是否匹配关键词* param text* param beginIndex* return*/private static int checkWord(String text, int beginIndex) {if (dictionaryMap null) {throw new RuntimeException(字典不能为空);}boolean isEnd false;int wordLength 0;MapString, Object curMap dictionaryMap;int len text.length();// 从文本的第beginIndex开始匹配for (int i beginIndex; i len; i) {String key String.valueOf(text.charAt(i));// 获取当前key的下一个节点curMap (MapString, Object) curMap.get(key);if (curMap null) {break;} else {wordLength ;if (1.equals(curMap.get(isEnd))) {isEnd true;}}}if (!isEnd) {wordLength 0;}return wordLength;}/*** 获取匹配的关键词和命中次数* param text* return*/public static MapString, Integer matchWords(String text) {MapString, Integer wordMap new HashMap();int len text.length();for (int i 0; i len; i) {int wordLength checkWord(text, i);if (wordLength 0) {String word text.substring(i, i wordLength);// 添加关键词匹配次数if (wordMap.containsKey(word)) {wordMap.put(word, wordMap.get(word) 1);} else {wordMap.put(word, 1);}i wordLength - 1;}}return wordMap;}
验证DFA算法
public static void main(String[] args) {ListString list new ArrayList();list.add(坏蛋);list.add(混蛋);list.add(笨蛋);initMap(list);String content我是一个坏人但是不是坏蛋也不是笨蛋;MapString, Integer map matchWords(content);System.out.println(map);} 可以看到匹配结果是正确的上面的代码可以直接封装成工具类使用
// 封装后直接调用
// 初始化敏感词库SensitiveWordUtil.initMap(sensitiveList);// 查看内容中是否包含敏感词
MapString, Integer map SensitiveWordUtil.matchWords(content);
if (map.size() 0) {System.out.println(内容中存在敏感词);}
拓展延申
这个算法和之前遇到的字典树Trie算法很像然后我就去搜索了一下两者的联系发现DFA算法的核心就是构建一颗以敏感词为基础的多叉树也就是字典树。字典树的每个节点代表一个状态每条边代表一个字符从一个状态到另一个状态的转移。当遍历完一个词后将该词的最后一个字符的状态标记为结束isEnd true
这样我们可以通过这个DFA字典树一个字符一个字符的检测输入的字符串如果检测的字符在我们的敏感词树中就进入命中的树看下一个字符在不在树中如果持续命中到最后一个字符即idEnd true那么就是完全命中了即存在敏感词
