实现原理

布隆过滤器

建立bitset，将一个词都hash映射到bitset中，如果查找一个词全1那么就是敏感词，非全1就不是
这是一种空间换时间的方法，因为映射空间非常小，就会产生冲突
http://www.cnblogs.com/heaad/archive/2011/01/02/1924195.html

tire树

这一种树，每一个节点是一个字母或者汉字，同时一个节点有多个子节点，还有标志位用来记录是不是结束，比如色情这个词汇中情字节点就会有标志位

http://blog.duyaokeep.cn/2016/03/24/%E5%AD%97%E5%85%B8%E6%A0%91/

复杂度分析

（1） 插入、查找的时间复杂度均为O(N)，其中N为字符串长度。
（2） 空间复杂度是26^n级别的，非常庞大（可采用双数组实现改善）。

结构

结构如下：其中map记录了所有的子节点，对于英文字就可以用数组实现，因为总数固定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
private class TrieNode {
    /**
     * true 关键词的终结 ； false 继续
     */
    private boolean end = false;
    /**
     * key下一个字符，value是对应的节点
     */
    private Map<Character, TrieNode> subNodes = new HashMap<>();
    /**
     * 向指定位置添加节点树
     */
    void addSubNode(Character key, TrieNode node) {
        subNodes.put(key, node);
    }
    /**
     * 获取下个节点
     */
    TrieNode getSubNode(Character key) {
        return subNodes.get(key);
    }
    boolean isKeywordEnd() {
        return end;
    }
    void setKeywordEnd(boolean end) {
        this.end = end;
    }
    public int getSubNodeCount() {
        return subNodes.size();
    }
}

查找过程

添加过程就是有三个指针begin、position、root分别指向回滚位置、当期位置和树的根节点
不停比较position和root位置的字符，会产生2种结果

  • 相等
    说明有可能是敏感词可以继续后移比较，同时检查如果树中root位置已经到了标记位，说明从begin到pos都是敏感词，记录并开始新的一轮
  • 不相等
    root和pos都后移
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
 * 过滤敏感词
 */
public String filter(String text) {
    if (StringUtils.isBlank(text)) {
        return text;
    }
    String replacement = DEFAULT_REPLACEMENT;
    StringBuilder result = new StringBuilder();
    TrieNode tempNode = rootNode;
    int begin = 0; // 回滚数
    int position = 0; // 当前比较的位置
    while (position < text.length()) {
        char c = text.charAt(position);
        // 空格直接跳过
        if (isSymbol(c)) {
            if (tempNode == rootNode) {
                result.append(c);
                ++begin;
            }
            ++position;
            continue;
        }
        tempNode = tempNode.getSubNode(c);
        // 当前位置的匹配结束
        if (tempNode == null) {
            // 以begin开始的字符串不存在敏感词
            result.append(text.charAt(begin));
            // 跳到下一个字符开始测试
            position = begin + 1;
            begin = position;
            // 回到树初始节点
            tempNode = rootNode;
        } else if (tempNode.isKeywordEnd()) {
            // 发现敏感词， 从begin到position的位置用replacement替换掉
            result.append(replacement);
            position = position + 1;
            begin = position;
            tempNode = rootNode;
        } else {
            ++position;
        }
    }
    result.append(text.substring(begin));
    return result.toString();
}

添加节点

就是判断该节点是不是和字符相等，不相等就继续查，节点空说明查到叶子节点了，需要添加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private void addWord(String lineTxt) {
    TrieNode tempNode = rootNode;
    // 循环每个字节
    for (int i = 0; i < lineTxt.length(); ++i) {
        Character c = lineTxt.charAt(i);
        // 过滤空格
        if (isSymbol(c)) {
            continue;
        }
        TrieNode node = tempNode.getSubNode(c);
        if (node == null) { // 没初始化
            node = new TrieNode();
            tempNode.addSubNode(c, node);
        }
        tempNode = node;
        if (i == lineTxt.length() - 1) {
            // 关键词结束， 设置结束标志
            tempNode.setKeywordEnd(true);
        }
    }
}

其余过滤

过滤过程中，同时会出现*色*情等加入空格或者其他符号的现象，因此通过其ascii值就能过滤掉

1
2
3
4
5
6
7
8
/**
 * 判断是否是一个符号
 */
private boolean isSymbol(char c) {
    int ic = (int) c;
    // 0x2E80-0x9FFF 东亚文字范围
    return !CharUtils.isAsciiAlphanumeric(c) && (ic < 0x2E80 || ic > 0x9FFF);
}

还要过滤html等标签

1
HtmlUtils.htmlEscape(question.getTitle());

过滤服务

这个service需要初始化来导入敏感词，因此要实现InitializingBean
在afterPropertiesSet()方法中实现读取敏感词文件的过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class SensitiveService implements InitializingBean {
    private static final Logger logger = LoggerFactory.getLogger(SensitiveService.class);
    /**
     * 默认敏感词替换符
     */
    private static final String DEFAULT_REPLACEMENT = "敏感词";
    /**
     * 根节点
     */
    private TrieNode rootNode = new TrieNode();
    @Override
    public void afterPropertiesSet() throws Exception {
        rootNode = new TrieNode();
        try {
            InputStream is = Thread.currentThread().getContextClassLoader()
                    .getResourceAsStream("SensitiveWords.txt");
            InputStreamReader read = new InputStreamReader(is);
            BufferedReader bufferedReader = new BufferedReader(read);
            String lineTxt;
            while ((lineTxt = bufferedReader.readLine()) != null) {
                lineTxt = lineTxt.trim();
                addWord(lineTxt);
            }
            read.close();
        } catch (Exception e) {
            logger.error("读取敏感词文件失败" + e.getMessage());
        }
    }
    public static void main(String[] argv) {
        SensitiveService s = new SensitiveService();
        s.addWord("色情");
        s.addWord("好色");
        System.out.print(s.filter("你好X色**情XX"));
    }
}

http://www.cnblogs.com/heaad/archive/2011/01/02/1924195.html