Java实现DFA算法对敏感词、广告词过滤功能示例

一、前言

开发中经常要处理用户一些文字的提交，所以涉及到了敏感词过滤的功能，参考资料中DFA有穷状态机算法的实现，创建有向图。完成了对敏感词、广告词的过滤，而且效率较好，所以分享一下。

具体实现：

 1、匹配大小写过滤
 2、匹配全角半角过滤
 3、匹配过滤停顿词过滤。
 4、敏感词重复词过滤。

例如：

支持如下类型类型过滤检测：

fuck 全小写

FuCk 大小写

ｆｕｃｋ全角半角

f!!!u&c ###k 停顿词

fffuuuucccckkk 重复词

敏感词过滤的做法有很多，我简单描述我现在理解的几种：

①查询数据库当中的敏感词，循环每一个敏感词，然后去输入的文本中从头到尾搜索一遍，看是否存在此敏感词，有则做相

应的处理，这种方式讲白了就是找到一个处理一个。

优点：so easy。用java代码实现基本没什么难度。

缺点：这效率让我心中奔过十万匹草泥马，而且匹配的是不是有些蛋疼，如果是英文时你会发现一个很无语的事情，比如英文

a是敏感词，那我如果是一篇英文文档，那程序它妹的得处理多少次敏感词？谁能告诉我？

②传说中的DFA算法（有穷自动机）,也正是我要给大家分享的，毕竟感觉比较通用，算法的原理希望大家能够自己去网上查查

资料，这里就不详细说明了。

优点：至少比上面那sb效率高点。

缺点：对于学过算法的应该不难，对于没学过算法的用起来也不难，就是理解起来有点gg疼，匹配效率也不高，比较耗费内存，

敏感词越多，内存占用的就越大。

③第三种在这里要特别说明一下，那就是你自己去写一个算法吧，或者在现有的算法的基础上去优化，这也是小Alan追求的至

高境界之一，如果哪位淫兄有自己的想法一定别忘了小Alan，可以加小Alan的QQ：810104041教小Alan两招耍耍。

二、代码实现

其目录结构如下：

其中resources资源目录中：

stopwd.txt ：停顿词，匹配时间直接过滤。

wd.txt：敏感词库。

1、WordFilter敏感词过滤类

package org.andy.sensitivewdfilter;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.andy.sensitivewdfilter.util.BCConvert;

/**
* 创建时间：2016年8月30日 下午3:01:12
*
* 思路： 创建一个FilterSet，枚举了0~65535的所有char是否是某个敏感词开头的状态
*
* 判断是否是 敏感词开头 | | 是 不是 获取头节点 OK--下一个字 然后逐级遍历，DFA算法
*
* @author andy
* @version 2.2
*/
public class WordFilter {

private static final FilterSet set = new FilterSet(); // 存储首字
 private static final Map<Integer, WordNode> nodes = new HashMap<Integer, WordNode>(1024, 1); // 存储节点
 private static final Set<Integer> stopwdSet = new HashSet<>(); // 停顿词
 private static final char SIGN = '*'; // 敏感词过滤替换

static {
   try {
     long a = System.nanoTime();
     init();
     a = System.nanoTime() - a;
     System.out.println("加载时间 : " + a + "ns");
     System.out.println("加载时间 : " + a / 1000000 + "ms");
   } catch (Exception e) {
     throw new RuntimeException("初始化过滤器失败");
   }
 }

private static void init() {
   // 获取敏感词
   addSensitiveWord(readWordFromFile("wd.txt"));
   addStopWord(readWordFromFile("stopwd.txt"));
 }

/**
  * 增加敏感词
  * @param path
  * @return
  */
 private static List<String> readWordFromFile(String path) {
   List<String> words;
   BufferedReader br = null;
   try {
     br = new BufferedReader(new InputStreamReader(WordFilter.class.getClassLoader().getResourceAsStream(path)));
     words = new ArrayList<String>(1200);
     for (String buf = ""; (buf = br.readLine()) != null;) {
       if (buf == null || buf.trim().equals(""))
         continue;
       words.add(buf);
     }
   } catch (Exception e) {
     throw new RuntimeException(e);
   } finally {
     try {
       if (br != null)
         br.close();
     } catch (IOException e) {
     }
   }
   return words;
 }

/**
  * 增加停顿词
  *
  * @param words
  */
 private static void addStopWord(final List<String> words) {
   if (words != null && words.size() > 0) {
     char[] chs;
     for (String curr : words) {
       chs = curr.toCharArray();
       for (char c : chs) {
         stopwdSet.add(charConvert(c));
       }
     }
   }
 }

/**
  * 添加DFA节点
  * @param words
  */
 private static void addSensitiveWord(final List<String> words) {
   if (words != null && words.size() > 0) {
     char[] chs;
     int fchar;
     int lastIndex;
     WordNode fnode; // 首字母节点
     for (String curr : words) {
       chs = curr.toCharArray();
       fchar = charConvert(chs[0]);
       if (!set.contains(fchar)) {// 没有首字定义
         set.add(fchar);// 首字标志位 可重复add,反正判断了，不重复了
         fnode = new WordNode(fchar, chs.length == 1);
         nodes.put(fchar, fnode);
       } else {
         fnode = nodes.get(fchar);
         if (!fnode.isLast() && chs.length == 1)
           fnode.setLast(true);
       }
       lastIndex = chs.length - 1;
       for (int i = 1; i < chs.length; i++) {
         fnode = fnode.addIfNoExist(charConvert(chs[i]), i == lastIndex);
       }
     }
   }
 }

/**
  * 过滤判断 将敏感词转化为成屏蔽词
  * @param src
  * @return
  */
 public static final String doFilter(final String src) {
   char[] chs = src.toCharArray();
   int length = chs.length;
   int currc;
   int k;
   WordNode node;
   for (int i = 0; i < length; i++) {
     currc = charConvert(chs[i]);
     if (!set.contains(currc)) {
       continue;
     }
     node = nodes.get(currc);// 日 2
     if (node == null)// 其实不会发生，习惯性写上了
       continue;
     boolean couldMark = false;
     int markNum = -1;
     if (node.isLast()) {// 单字匹配（日）
       couldMark = true;
       markNum = 0;
     }
     // 继续匹配（ * / * 妹），以长的优先
     // 你-3 妹-4 夫-5
     k = i;
     for (; ++k < length;) {
       int temp = charConvert(chs[k]);
       if (stopwdSet.contains(temp))
         continue;
       node = node.querySub(temp);
       if (node == null)// 没有了
         break;
       if (node.isLast()) {
         couldMark = true;
         markNum = k - i;// 3-2
       }
     }
     if (couldMark) {
       for (k = 0; k <= markNum; k++) {
         chs[k + i] = SIGN;
       }
       i = i + markNum;
     }
   }

return new String(chs);
 }

/**
  * 是否包含敏感词
  * @param src
  * @return
  */
 public static final boolean isContains(final String src) {
   char[] chs = src.toCharArray();
   int length = chs.length;
   int currc;
   int k;
   WordNode node;
   for (int i = 0; i < length; i++) {
     currc = charConvert(chs[i]);
     if (!set.contains(currc)) {
       continue;
     }
     node = nodes.get(currc);// 日 2
     if (node == null)// 其实不会发生，习惯性写上了
       continue;
     boolean couldMark = false;
     if (node.isLast()) {// 单字匹配（日）
       couldMark = true;
     }
     // 继续匹配（ * / * 妹），以长的优先
     // 你-3 妹-4 夫-5
     k = i;
     for (; ++k < length;) {
       int temp = charConvert(chs[k]);
       if (stopwdSet.contains(temp))
         continue;
       node = node.querySub(temp);
       if (node == null)// 没有了
         break;
       if (node.isLast()) {
         couldMark = true;
       }
     }
     if (couldMark) {
       return true;
     }
   }

return false;
 }

/**
  * 大写转化为小写 全角转化为半角
  *
  * @param src
  * @return
  */
 private static int charConvert(char src) {
   int r = BCConvert.qj2bj(src);
   return (r >= 'A' && r <= 'Z') ? r + 32 : r;
 }

}

其中：

isContains ：是否包含敏感词
doFilter：过滤敏感词

2、WordNode敏感词节点

package org.andy.sensitivewdfilter;

import java.util.LinkedList;
import java.util.List;

/**
* 创建时间：2016年8月30日 下午3:07:45
*
* @author andy
* @version 2.2
*/
public class WordNode {

private int value; // 节点名称

private List<WordNode> subNodes; // 子节点

private boolean isLast;// 默认false

public WordNode(int value) {
   this.value = value;
 }

public WordNode(int value, boolean isLast) {
   this.value = value;
   this.isLast = isLast;
 }

/**
  *
  * @param subNode
  * @return 就是传入的subNode
  */
 private WordNode addSubNode(final WordNode subNode) {
   if (subNodes == null)
     subNodes = new LinkedList<WordNode>();
   subNodes.add(subNode);
   return subNode;
 }

/**
  * 有就直接返回该子节点， 没有就创建添加并返回该子节点
  *
  * @param value
  * @return
  */
 public WordNode addIfNoExist(final int value, final boolean isLast) {
   if (subNodes == null) {
     return addSubNode(new WordNode(value, isLast));
   }
   for (WordNode subNode : subNodes) {
     if (subNode.value == value) {
       if (!subNode.isLast && isLast)
         subNode.isLast = true;
       return subNode;
     }
   }
   return addSubNode(new WordNode(value, isLast));
 }

public WordNode querySub(final int value) {
   if (subNodes == null) {
     return null;
   }
   for (WordNode subNode : subNodes) {
     if (subNode.value == value)
       return subNode;
   }
   return null;
 }

public boolean isLast() {
   return isLast;
 }

public void setLast(boolean isLast) {
   this.isLast = isLast;
 }

@Override
 public int hashCode() {
   return value;
 }

}

三、测试结果

项目包含敏感词库，源码，停顿词库等，只需运行maven打jar包直接可运行。

项目源码：sensitivewd-filter_jb51.rar

来源：http://blog.csdn.net/fengshizty/article/details/52373005