在此先感谢 elulis，开源项目主页：https://github.com/elulis/sensitive-words

关键词：敏感词 过滤 DFA

封装代码

StringPointer

  1. import java.io.Serializable;
  2. import java.util.HashMap;
  3. import java.util.TreeMap;
  5. /**
  6.  * 没有注释的方法与{@link String}类似<br/>
  7.  * <b>注意：</b>没有（数组越界等的）安全检查<br/>
  8.  * 可以作为{@link HashMap}和{@link TreeMap}的key
  9.  *
  10.  * @author ZhangXiaoye
  11.  * @date 2017年1月5日 下午2:11:56
  12.  */
  13. public class StringPointer implements Serializable, CharSequence, Comparable<StringPointer>{
  15.     private static final long serialVersionUID = 1L;
  17.     protected final char[] value;
  19.     protected final int offset;
  21.     protected final int length;
  23.     private int hash = 0;
  25.     public StringPointer(String str){
  26.         value = str.toCharArray();
  27.         offset = 0;
  28.         length = value.length;
  29.     }
  31.     public StringPointer(char[] value, int offset, int length){
  32.         this.value = value;
  33.         this.offset = offset;
  34.         this.length = length;
  35.     }
  37.     /**
  38.      * 计算该位置后（包含）2个字符的hash值
  39.      *
  40.      * @param i 从 0 到 length - 2
  41.      * @return hash值
  42.      * @author ZhangXiaoye
  43.      * @date 2017年1月5日 下午2:23:02
  44.      */
  45.     public int nextTwoCharHash(int i){
  46.         return 31 * value[offset + i] + value[offset + i + 1];
  47.     }
  49.     /**
  50.      * 计算该位置后（包含）2个字符和为1个int型的值<br/>
  51.      * int值相同表示2个字符相同
  52.      *
  53.      * @param i 从 0 到 length - 2
  54.      * @return int值
  55.      * @author ZhangXiaoye
  56.      * @date 2017年1月5日 下午2:46:58
  57.      */
  58.     public int nextTwoCharMix(int i){
  59.         return (value[offset + i] << 16) | value[offset + i + 1];
  60.     }
  62.     /**
  63.      * 该位置后（包含）的字符串，是否以某个词（word）开头
  64.      *
  65.      * @param i 从 0 到 length - 2
  66.      * @param word 词
  67.      * @return 是否？
  68.      * @author ZhangXiaoye
  69.      * @date 2017年1月5日 下午3:13:49
  70.      */
  71.     public boolean nextStartsWith(int i, StringPointer word){
  72.         // 是否长度超出
  73.         if(word.length > length - i){
  74.             return false;
  75.         }
  76.         // 从尾开始判断
  77.         for(int c =  word.length - 1; c >= 0; c --){
  78.             if(value[offset + i + c] != word.value[word.offset + c]){
  79.                 return false;
  80.             }
  81.         }
  82.         return true;
  83.     }
  85.     /**
  86.      * 填充（替换）
  87.      *
  88.      * @param begin 从此位置开始（含）
  89.      * @param end 到此位置结束（不含）
  90.      * @param fillWith 以此字符填充（替换）
  91.      * @author ZhangXiaoye
  92.      * @date 2017年1月5日 下午3:29:21
  93.      */
  94.     public void fill(int begin, int end, char fillWith){
  95.         for(int i = begin; i < end; i ++){
  96.             value[offset + i] = fillWith;
  97.         }
  98.     }
  100.     @Override
  101.     public int length(){
  102.         return length;
  103.     }
  105.     @Override
  106.     public char charAt(int i){
  107.         return value[offset + i];
  108.     }
  110.     public StringPointer substring(int begin){
  111.         return new StringPointer(value, offset + begin, length - begin);
  112.     }
  114.     public StringPointer substring(int begin, int end){
  115.         return new StringPointer(value, offset + begin, end - begin);
  116.     }
  118.     @Override
  119.     public CharSequence subSequence(int start, int end) {
  120.         return substring(start, end);
  121.     }
  123.     @Override
  124.     public String toString(){
  125.         return new String(value, offset, length);
  126.     }
  128.     @Override
  129.     public int hashCode() {
  130.         int h = hash;
  131.         if (h == 0 && length > 0) {
  132.             for (int i = 0; i < length; i++) {
  133.                 h = 31 * h + value[offset + i];
  134.             }
  135.             hash = h;
  136.         }
  137.         return h;
  138.     }
  140.     public boolean equals(Object anObject) {
  141.         if (this == anObject) {
  142.             return true;
  143.         }
  144.         if (anObject instanceof StringPointer) {
  145.             StringPointer that = (StringPointer)anObject;
  146.             if (length == that.length) {
  147.                 char v1[] = this.value;
  148.                 char v2[] = that.value;
  149.                 for(int i = 0; i < this.length; i ++){
  150.                     if(v1[this.offset + i] != v2[that.offset + i]){
  151.                         return false;
  152.                     }
  153.                 }
  154.                 return true;
  155.             }
  156.         }
  157.         return false;
  158.     }
  160.     @Override
  161.     public int compareTo(StringPointer that) {
  162.         int len1 = this.length;
  163.         int len2 = that.length;
  164.         int lim = Math.min(len1, len2);
  165.         char v1[] = this.value;
  166.         char v2[] = that.value;
  168.         int k = 0;
  169.         while (k < lim) {
  170.             char c1 = v1[this.offset + k];
  171.             char c2 = v2[that.offset + k];
  172.             if (c1 != c2) {
  173.                 return c1 - c2;
  174.             }
  175.             k++;
  176.         }
  177.         return len1 - len2;
  178.     }
  180. }

SensitiveNode

  1. import java.io.Serializable;
  2. import java.util.TreeSet;
  4. /**
  5.  * 敏感词节点，每个节点包含了以相同的2个字符开头的所有词
  6.  * 
  7.  * @author ZhangXiaoye
  8.  * @date 2017年1月5日 下午5:06:26
  9.  */
  10. public class SensitiveNode implements Serializable{
  12.     private static final long serialVersionUID = 1L;
  14.     /**
  15.      * 头两个字符的mix，mix相同，两个字符相同
  16.      */
  17.     protected final int headTwoCharMix;
  19.     /**
  20.      * 所有以这两个字符开头的词表
  21.      */
  22.     protected final TreeSet<StringPointer> words = new TreeSet<StringPointer>();
  24.     /**
  25.      * 下一个节点
  26.      */
  27.     protected SensitiveNode next;
  29.     public SensitiveNode(int headTwoCharMix){
  30.         this.headTwoCharMix = headTwoCharMix;
  31.     }
  33.     public SensitiveNode(int headTwoCharMix, SensitiveNode parent){
  34.         this.headTwoCharMix = headTwoCharMix;
  35.         parent.next = this;
  36.     }
  38. }

SensitiveFilter

  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.io.Serializable;
  5. import java.nio.charset.StandardCharsets;
  6. import java.util.Iterator;
  7. import java.util.NavigableSet;
  9. /**
  10.  * 敏感词过滤器，以过滤速度优化为主。<br/>
  11.  * * 增加一个敏感词：{@link #put(String)} <br/>
  12.  * * 过滤一个句子：{@link #filter(String, char)} <br/>
  13.  * * 获取默认的单例：{@link #DEFAULT}
  14.  *
  15.  * @author ZhangXiaoye
  16.  * @date 2017年1月5日 下午4:18:38
  17.  */
  18. public class SensitiveFilter implements Serializable {
  20.     private static String regex = "[`~!@#$%^&*()+=|{}':;',\\\\[\\\\].<>/?~！@#￥%……&*（）——+|{}【】‘；：”“’。，、？]|\\s*";
  22.     private static final long serialVersionUID = 1L;
  24.     /**
  25.      * 默认的单例，使用自带的敏感词库
  26.      */
  27.     public static final SensitiveFilter DEFAULT = new SensitiveFilter(
  28.             new BufferedReader(new InputStreamReader(
  29.                     ClassLoader.getSystemResourceAsStream("sensi_words.txt")
  30.                     , StandardCharsets.UTF_8)));
  32.     /**
  33.      * 为2的n次方，考虑到敏感词大概在10k左右，
  34.      * 这个数量应为词数的数倍，使得桶很稀疏
  35.      * 提高不命中时hash指向null的概率，
  36.      * 加快访问速度。
  37.      */
  38.     static final int DEFAULT_INITIAL_CAPACITY = 131072;
  40.     /**
  41.      * 类似HashMap的桶，比较稀疏。
  42.      * 使用2个字符的hash定位。
  43.      */
  44.     protected SensitiveNode[] nodes = new SensitiveNode[DEFAULT_INITIAL_CAPACITY];
  46.     /**
  47.      * 构建一个空的filter
  48.      *
  49.      * @author ZhangXiaoye
  50.      * @date 2017年1月5日 下午4:18:07
  51.      */
  52.     public SensitiveFilter() {
  54.     }
  56.     /**
  57.      * 加载一个文件中的词典，并构建filter<br/>
  58.      * 文件中，每行一个敏感词条<br/>
  59.      * <b>注意：</b>读取完成后会调用{@link BufferedReader#close()}方法。<br/>
  60.      * <b>注意：</b>读取中的{@link IOException}不会抛出
  61.      *
  62.      * @param reader
  63.      * @author ZhangXiaoye
  64.      * @date 2017年1月5日 下午4:21:06
  65.      */
  66.     public SensitiveFilter(BufferedReader reader) {
  67.         try {
  68.             for (String line = reader.readLine(); line != null; line = reader.readLine()) {
  69.                 put(line);
  70.             }
  71.             reader.close();
  72.         } catch (IOException e) {
  73.             e.printStackTrace();
  74.         }
  75.     }
  77.     /**
  78.      * 增加一个敏感词，如果词的长度（trim后）小于2，则丢弃<br/>
  79.      * 此方法（构建）并不是主要的性能优化点。
  80.      *
  81.      * @param word
  82.      * @author ZhangXiaoye
  83.      * @date 2017年1月5日 下午2:35:21
  84.      */
  85.     public boolean put(String word) {
  86.         // 长度小于2的不加入
  87.         if (word == null || word.trim().length() < 2) {
  88.             return false;
  89.         }
  90.         // 两个字符的不考虑
  91.         if (word.length() == 2 && word.matches("\\w\\w")) {
  92.             return false;
  93.         }
  94.         StringPointer sp = new StringPointer(word.trim());
  95.         // 计算头两个字符的hash
  96.         int hash = sp.nextTwoCharHash(0);
  97.         // 计算头两个字符的mix表示（mix相同，两个字符相同）
  98.         int mix = sp.nextTwoCharMix(0);
  99.         // 转为在hash桶中的位置
  100.         int index = hash & (nodes.length - 1);
  102.         // 从桶里拿第一个节点
  103.         SensitiveNode node = nodes[index];
  104.         if (node == null) {
  105.             // 如果没有节点，则放进去一个
  106.             node = new SensitiveNode(mix);
  107.             // 并添加词
  108.             node.words.add(sp);
  109.             // 放入桶里
  110.             nodes[index] = node;
  111.         } else {
  112.             // 如果已经有节点（1个或多个），找到正确的节点
  113.             for (; node != null; node = node.next) {
  114.                 // 匹配节点
  115.                 if (node.headTwoCharMix == mix) {
  116.                     node.words.add(sp);
  117.                     return true;
  118.                 }
  119.                 // 如果匹配到最后仍然不成功，则追加一个节点
  120.                 if (node.next == null) {
  121.                     new SensitiveNode(mix, node).words.add(sp);
  122.                     return true;
  123.                 }
  124.             }
  125.         }
  126.         return true;
  127.     }
  129.     /**
  130.      * 对句子进行敏感词过滤<br/>
  131.      * 如果无敏感词返回输入的sentence对象，即可以用下面的方式判断是否有敏感词：<br/><code>
  132.      * String result = filter.filter(sentence, '*');<br/>
  133.      * if(result != sentence){<br/>
  134.      * &nbsp;&nbsp;// 有敏感词<br/>
  135.      * }
  136.      * </code>
  137.      *
  138.      * @param sentence 句子
  139.      * @param replace  敏感词的替换字符
  140.      * @return 过滤后的句子
  141.      * @author ZhangXiaoye
  142.      * @date 2017年1月5日 下午4:16:31
  143.      */
  144.     public String filter(String sentence, char replace) {
  145.         // 先转换为StringPointer
  146.         sentence = sentence.replaceAll(regex, "");
  147.         StringPointer sp = new StringPointer(sentence);
  149.         // 标示是否替换
  150.         boolean replaced = false;
  152.         // 匹配的起始位置
  153.         int i = 0;
  154.         while (i < sp.length - 2) {
  155.             /*
  156.              * 移动到下一个匹配位置的步进：
  157.              * 如果未匹配为1，如果匹配是匹配的词长度
  158.              */
  159.             int step = 1;
  160.             // 计算此位置开始2个字符的hash
  161.             int hash = sp.nextTwoCharHash(i);
  162.             /*
  163.              * 根据hash获取第一个节点，
  164.              * 真正匹配的节点可能不是第一个，
  165.              * 所以有后面的for循环。
  166.              */
  167.             SensitiveNode node = nodes[hash & (nodes.length - 1)];
  168.             /*
  169.              * 如果非敏感词，node基本为null。
  170.              * 这一步大幅提升效率
  171.              */
  172.             if (node != null) {
  173.                 /*
  174.                  * 如果能拿到第一个节点，
  175.                  * 才计算mix（mix相同表示2个字符相同）。
  176.                  * mix的意义和HashMap先hash再equals的equals部分类似。
  177.                  */
  178.                 int mix = sp.nextTwoCharMix(i);
  179.                 /*
  180.                  * 循环所有的节点，如果非敏感词，
  181.                  * mix相同的概率非常低，提高效率
  182.                  */
  183.                 outer:
  184.                 for (; node != null; node = node.next) {
  185.                     /*
  186.                      * 对于一个节点，先根据头2个字符判断是否属于这个节点。
  187.                      * 如果属于这个节点，看这个节点的词库是否命中。
  188.                      * 此代码块中访问次数已经很少，不是优化重点
  189.                      */
  190.                     if (node.headTwoCharMix == mix) {
  191.                         /*
  192.                          * 查出比剩余sentence小的最大的词。
  193.                          * 例如剩余sentence为"色情电影哪家强？"，
  194.                          * 这个节点含三个词从小到大为："色情"、"色情电影"、"色情信息"。
  195.                          * 则从“色情电影”开始向前匹配
  196.                          */
  197.                         NavigableSet<StringPointer> desSet = node.words.headSet(sp.substring(i), true);
  198.                         if (desSet != null) {
  199.                             for (StringPointer word : desSet.descendingSet()) {
  200.                                 /*
  201.                                  * 仍然需要再判断一次，例如"色情信息哪里有？"，
  202.                                  * 如果节点只包含"色情电影"一个词，
  203.                                  * 仍然能够取到word为"色情电影"，但是不该匹配。
  204.                                  */
  205.                                 if (sp.nextStartsWith(i, word)) {
  206.                                     // 匹配成功，将匹配的部分，用replace制定的内容替代
  207.                                     sp.fill(i, i + word.length, replace);
  208.                                     // 跳过已经替代的部分
  209.                                     step = word.length;
  210.                                     // 标示有替换
  211.                                     replaced = true;
  212.                                     // 跳出循环（然后是while循环的下一个位置）
  213.                                     break outer;
  214.                                 }
  215.                             }
  216.                         }
  218.                     }
  219.                 }
  220.             }
  222.             // 移动到下一个匹配位置
  223.             i += step;
  224.         }
  226.         // 如果没有替换，直接返回入参（节约String的构造copy）
  227.         if (replaced) {
  228.             return sp.toString();
  229.         } else {
  230.             return sentence;
  231.         }
  232.     }
  234. }

使用

  1. import java.io.BufferedReader;
  2. import java.io.File;
  3. import java.io.FileInputStream;
  4. import java.io.InputStreamReader;
  5. import java.io.PrintStream;
  6. import java.util.ArrayList;
  7. import java.util.List;
  9. import junit.framework.TestCase;
  11. public class SensitiveFilterTest extends TestCase {
  13.     public void test() throws Exception {
  15.         // 使用默认单例（加载默认词典）
  16.         SensitiveFilter filter = SensitiveFilter.DEFAULT;
  17.         // 向过滤器增加一个词
  18.         filter.put("婚礼上唱春天在哪里");
  20.         // 待过滤的句子
  21.         String sentence = "然后，市长在婚礼上唱春天在哪里。";
  22.         // 进行过滤
  23.         String filted = filter.filter(sentence, '*');
  25.         // 如果未过滤，则返回输入的String引用
  26.         if (sentence != filted) {
  27.             // 句子中有敏感词
  28.             System.out.println(filted);
  29.         }
  31.     }
  33.     public void testLogic() {
  35.         SensitiveFilter filter = new SensitiveFilter();
  37.         filter.put("你好");
  38.         filter.put("你好1");
  39.         filter.put("你好2");
  40.         filter.put("你好3");
  41.         filter.put("你好4");
  43.         System.out.println(filter.filter("你好3天不见", '*'));
  45.     }
  47.     public void testSpeed() throws Exception {
  49.         PrintStream ps = new PrintStream("123Out.txt");
  51.         File file = new File("123.txt");
  53.         List<String> testSuit = new ArrayList<String>(1048576);
  54.         long length = 0;
  56.         if (file.isFile() && file.getName().endsWith(".txt")) {
  57.             BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(file), "gb18030"));
  58.             for (String line = br.readLine(); line != null; line = br.readLine()) {
  59.                 if (line.trim().length() > 0) {
  60.                     testSuit.add(line);
  61.                     length += line.length();
  62.                 }
  63.             }
  64.             br.close();
  65.         }
  67.         System.out.println(String.format("待过滤文本共 %d 行，%d 字符。", testSuit.size(), length));
  70.         SensitiveFilter filter = SensitiveFilter.DEFAULT;
  72.         int replaced = 0;
  74.         for (String sentence : testSuit) {
  75.             String result = filter.filter(sentence, '*');
  76.             if (result != sentence) {
  77.                 ps.println(sentence);
  78.                 ps.println(result);
  79.                 ps.println();
  80.                 replaced++;
  81.             }
  82.         }
  83.         ps.close();
  85.         long timer = System.currentTimeMillis();
  86.         for (String line : testSuit) {
  87.             filter.filter(line, '*');
  88.         }
  89.         timer = System.currentTimeMillis() - timer;
  90.         System.out.println(String.format("过滤耗时 %1.3f 秒， 速度为 %1.1f字符/毫秒", timer * 1E-3, length / (double) timer));
  91.         System.out.println(String.format("其中 %d 行有替换", replaced));
  93.     }
  95. }