JAVA实现trie树（前缀树，字典树）进行敏感词检测/过滤

JAVA实现trie树（前缀树，字典树）进行敏感词检测/过滤

定义

在计算机科学中，trie树，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。

trie中的键通常是字符串，但也可以是其它的结构。trie的算法可以很容易地修改为处理其它结构的有序序列，比如一串数字或者形状的排列。比如，bitwise trie中的键是一串位元，可以用于表示整数或者内存地址

优点：

• 可以最大限度地减少无谓的字符串比较

• 跟哈希表比较：

1. 最坏情况时间复杂度比hash表好

2. 没有冲突，除非一个key对应多个值（除key外的其他信息）

3. 自带排序功能（类似Radix Sort），中序遍历trie可以得到排序。

缺点：

1. 虽然不同单词共享前缀，但其实trie是一个以空间换时间的算法。其每一个字符都可能包含至多字符集大小数目的指针（不包含卫星数据）。

2. 每个结点的子树的根节点的组织方式有几种。

   • 如果默认包含所有字符集，则查找速度快但浪费空间（特别是靠近树底部叶子）。
   • 如果用链接法(如左儿子右兄弟)，则节省空间但查找需顺序（部分）遍历链表。
   • alphabet reduction*: 减少字符宽度以减少字母集个数。,4>对字符集使用bitmap，再配合链接法。

3. 如果数据存储在外部存储器等较慢位置，Trie会较hash速度慢（hash访问O(1)次外存，Trie访问O(树高)）。

应用

• 词频统计
• 大量字符串排序。
  

敏感词检测

假设我们的敏感词库有下面敏感词：

• 高清AV

• 日狗

• 高清裸体图

开始构建敏感词Trie树

时间复杂度

• 如果敏感词的长度为 m,有 n个敏感词的话，构建 trie 树的时间复杂度是 O(n * m)。
• 但是我们可以使用静态代码块在应用初始化的时候就构建trie 树，而且之后每次查找都可以复用这棵树。所以可以忽略构建 trie 树的时间复杂度，

静态代码块：执行优先级高于非静态的初始化块，它会在类初始化的时候执行一次，执行完成便销毁，它仅能初始化类变量，即static修饰的数据成员。

static{
   

}
1
2
3
4

敏感词去重

但是一般我们的敏感词词库都很大，当敏感词数量很多之后我们新添敏感词的时候可能会忘记之前是不是添加了某个敏感词，那就会出现重复的敏感词，为了敏感词树构建的效率，我们要对敏感词去重

怎么去重？很简单，把敏感词读出来之后放进HashSet中，再把敏感词从HashSet中遍历出来插入TRIE树就可以啦

敏感词检测

如果有一段文字是：那些简单就是不肯免费带你吃鸡充不上电剧场版免费吃鸡，带你看免*费 AV

怎么从上面这段文字中检测出这段文字是否包含敏感词呢？

去特殊字符

有时候用户知道我们有敏感词检测的功能，会用一些特殊符号隔开敏感词，这时候为了更严格地检测，我们要把用户输入的特殊字符去掉特殊字符再检测

方法

1. 使用正则匹配出文本中的特殊字符
2. 把特殊字符把用‘’空字符串代替

/**
 * create by: Antares
 * description: 去掉特殊字符
 * create time: 2020/6/9 18:22
 * return
 **/
public static String deleteSpecialWord (String txt) {
   
   String regEx = "[\n`~!@#$%^&*()+=|{}':;,\\[\\].<>/?！￥…（）—【】‘；：”“’。，_·、？]";
   //可以在中括号内加上任何想要替换的字符，实际上是一个正则表达式

   //这里是将特殊字符换为aa字符串,""代表直接去掉
   String aa = "";

   Pattern p = Pattern.compile (regEx);

   Matcher m = p.matcher (txt);//这里把想要替换的字符串传进来

   return m.replaceAll (aa).trim ();

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

结束标识符

有时候会出现一种情况是：词库中含有敏感词是另一个敏感词的前缀，比如：abc是敏感词，abcd也是敏感词，检测ABCD很好办，因为可以默认为叶子结点就是结束位置

那么如何能够在检测时检测出abc呢？

• 可以用1表示是结尾，0不是
• 也可以用true ，false

JAVA实现

那么在JAVA中选用什么数据结构来实现Trie树呢

HashMap

• 我们都知道HashMap是一个查找效率在O（logn)的集合，所以用在这再合适不过

完整代码

初始化

import org.springframework.core.io.ClassPathResource;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class SensitiveWordInit {
   
    public static HashMap sensitiveWordMap;
    private static String ENCODING = "UTF-8";    //字符编码

    static {
   
        initKeyWord ();
    }

    public SensitiveWordInit () {
   
        super ();
    }

    
    public static Map initKeyWord () {
   
        try {
   
            //读取敏感词库
            Set<String> keyWordSet = readSensitiveWordFile ();
//            System.out.println (keyWordSet.size ());
            //将敏感词库加入到HashMap中
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