课程设计做了个博客系统,为了对评论进行敏感词过滤,所以去看了下DFA
在Java中实现敏感词过滤的关键就是DFA算法的实现。首先我们对上图进行剖析。在这过程中我们认为下面这种结构会更加清晰明了。
同时这里没有状态转换，没有动作，有的只是Query（查找）。我们可以认为，通过S query U、V，通过U query V、P，通过V query U P。通过这样的转变我们可以将状态的转换转变为使用Java集合的查找。
诚然，加入在我们的敏感词库中存在如下几个敏感词：日本人、日本鬼子、毛.泽.东。那么我需要构建成一个什么样的结构呢？
首先：query 日 ---> {本}、query 本 --->{人、鬼子}、query 人 --->{null}、query 鬼 ---> {子}。形如下结构：
下面我们在对这图进行扩展：
这样我们就将我们的敏感词库构建成了一个类似与一颗一颗的树，这样我们判断一个词是否为敏感词时就大大减少了检索的匹配范围。比如我们要判断日本人，根据第一个字我们就可以确认需要检索的是那棵树，然后再在这棵树中进行检索。
但是如何来判断一个敏感词已经结束了呢？利用标识位来判断。
所以对于这个关键是如何来构建一棵棵这样的敏感词树。下面我已Java中的HashMap为例来实现DFA算法。具体过程如下：
日本人，日本鬼子为例
1、在hashMap中查询“日”看其是否在hashMap中存在，如果不存在，则证明已“日”开头的敏感词还不存在，则我们直接构建这样的一棵树。跳至3。
2、如果在hashMap中查找到了，表明存在以“日”开头的敏感词，设置hashMap = hashMap.get("日")，跳至1，依次匹配“本”、“人”。
3、判断该字是否为该词中的最后一个字。若是表示敏感词结束，设置标志位isEnd = 1，否则设置标志位isEnd = 0；
首先需要建立一个敏感词库:
[java] view plain copy
/**
* 读取敏感词库，将敏感词放入HashSet中，构建一个DFA算法模型：
* 中 = {
* isEnd = 0
* 国 = {
* isEnd = 1
* 人 = {isEnd = 0
* 民 = {isEnd = 1}
* }
* 男 = {
* isEnd = 0
* 人 = {
* isEnd = 1
* }
* }
* }
* }
* 五 = {
* isEnd = 0
* 星 = {
* isEnd = 0
* 红 = {
* isEnd = 0
* 旗 = {
* isEnd = 1
* }
* }
* }
* }
*/
[html] view plain copy
/** * 创建敏感词汇树 * @param keyWordSet */public void createWords(Set keyWordSet) {sensitiveWordMap =new HashMap(keyWordSet.size()); Map nowMap =null; Map wordMap =null; String key =null;for (String word : keyWordSet) { nowMap =sensitiveWordMap; key = word;for (int index=0 ; indexchar keyChar = key.charAt(index); Object newWordMap = nowMap.get(keyChar);if (newWordMap!=null) { nowMap = (Map) newWordMap; }else { wordMap =new HashMap<>(); wordMap.put("isEnd","0"); nowMap.put(keyChar,wordMap); nowMap = wordMap; }if (index == key.length()-1) { nowMap.put("isEnd","1"); } } }}
敏感词库我们一个简单的方法给实现了，那么如何实现检索呢？检索过程无非就是hashMap的get实现，找到就证明该词为敏感词，否则不为敏感词。过程如下：假如我们匹配“中国人民万岁”。
1、第一个字“中”，我们在hashMap中可以找到。得到一个新的map = hashMap.get("")。
2、如果map == null，则不是敏感词。否则跳至3
3、获取map中的isEnd，通过isEnd是否等于1来判断该词是否为最后一个。如果isEnd == 1表示该词为敏感词，否则跳至1。
通过这个步骤我们可以判断“中国人民”为敏感词，但是如果我们输入“中国女人”则不是敏感词了。
[java] view plain copy
/** * 获取敏感词汇集 * @param txt * @param matchType * @return */public Set getSensitiveWord(String txt,int matchType) { Set sensitiveWordList =new HashSet<>();for (int index=0;indexint length = checkSensitiveWord(txt,index,matchType);if (length>0) { sensitiveWordList.add(txt.substring(index,index+length)); index = index + length -1; } }return sensitiveWordList;}/** * 匹配 判断敏感词汇 * @param txt * @param beginIndex * @param matchType * @return */public int checkSensitiveWord(String txt,int beginIndex,int matchType) {boolean flag =false;int wordFlag =0;char word =0; Map nowMap =sensitiveWordMap;for (int index=beginIndex ; indexif (nowMap!=null) { wordFlag++;if ("1".equals(nowMap.get("isEnd"))) { flag =true;if (FilterUtil.minMatchTYpe == matchType) {break;//最小匹配直接跳出 } } }else {//不存在，直接返回 break; } } System.out.println(wordFlag+" "+flag);if (wordFlag<2 || !flag) {return 0; }return wordFlag;}
网友评论