抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

DFA算法-简易Java敏感词过滤(含源文件和上万敏感词列表)

Java

发布于：2021年7月11日

次浏览

敏感词过滤说白了就是简单的字符串替换,Java本身已经提供了相关函数,但是一旦遇到长文本,或者敏感词数量庞大,效率下降就会非常明显.本文将介绍利用多叉树进行敏感词存储和过滤的方法.

多叉树

多叉树是一种特殊的数据结构,如下图
DearXuan
Head为头节点,下面的ABCDE均为子树.那么多叉树是如何存储敏感词的呢？首先将敏感词分解为一个一个的字符,例如敏感词"CSDN",第一个字符是C,则在Head下创建子树"C"(如果已经存在则跳过这一步).第二个字符是S,则在子树"C"下面创建"S"接下来是D,N,创建完N就可以结束了.如此循环,就可以创建出类似上图的多叉树.


检测敏感词时,对于字符串中的每一个字符,先查找Head下是否有存在对应子树,例如字符串"ELN",先读取第一个字符E,并检查Head,发现存在子树"E"；于是读取第二个字符L,并检查子树E的子树,发现存在L；最后读取第三个字符N,发现子树N还是存在.此时发现子树N后面没有内容,这说明ELN是一个敏感词,于是将ELN替换成"***".


这种算法会出现一个小意外,如果一个敏感词恰好是另一个敏感词的前缀,就会导致较短的敏感词被长的敏感词覆盖,这种情况可以通过添加结束标记来区分.不过我的想法是,如果出现这种情况,直接把前缀屏蔽掉就行了,这样后半段也不算敏感词了(好像实际工作中不能这样做),因此我没有添加结束标记.

代码

首先要先写一个数据结构来模拟多叉树,下图里Word就是一颗树,里面保存着当前字符c和子树next,compareTo是用来排序的,以提高查找效率.

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Word implements Comparable<Word>{
    public char c;
    public List next = null;
 
    public Word(char c){
        this.c = c;
    }
 
    @Override
    public int compareTo(Word word) {
        return c - word.c;
    }
}

上图的List继承了ArrayList,主要是因为ArrayList可以动态添加元素,便于偷懒

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
import java.util.ArrayList;
 
public class List extends ArrayList<Word> {
    public Word get(char c){
        for(Word w :this){
            if(w.c == c) return w;
        }
        return null;
    }
 
    /**
     * 二分查找,必须先升序排序
     * @param c 需要查找的字符
     * @return Word对象：如果找到   null:如果没找到
     */
    public Word binaryGet(char c){
        int left,right,key;
        Word word;
        left = 0;right = this.size()-1;
        while (left <= right){
            key = (left + right) / 2;
            word = get(key);
            if(word.c == c){
                return word;
            }else if(word.c > c){
                right = key - 1;
            }else {
                left = key + 1;
            }
        }
        return null;
    }
 
    public Word add(char c){
        Word word = new Word(c);
        super.add(word);
        return word;
    }
}

以下是核心代码

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
 
 
public final class SensitiveWordFilter {
    public static List wordList;
    private final static char replace = '*'; // 替代字符
    private final static char[] skip = new char[]{ // 遇到这些字符就会跳过,例如,如果"AB"是敏感词,那么"A B","A=B"也会被屏蔽
            '!','*','-','+','_','=',',','.','@'
    };
 
    /**
     * 敏感词替换
     * @param text 待替换文本
     * @return 替换后的文本
     */
    public static String Filter(String text){
        if(wordList == null || wordList.size() == 0) return text;
        char[] __char__ = text.toCharArray(); // 把String转化成char数组,便于遍历
        int i,j;
        Word word;
        boolean flag; // 是否需要替换
        for(i=0;i<__char__.length;i++){ // 遍历所有字符
            char c = __char__[i];
            word = wordList.binaryGet(c); // 使用二分查找来寻找字符,提高效率
            if(word != null){ // word != null说明找到了
                flag = false;
                j = i+1;
                while (j < __char__.length){ // 开始逐个比较后面的字符
                    if(skip(__char__[j])) { // 跳过空格之类的无关字符
                        j++;
                        continue;
                    }
                    if(word.next != null){ // 字符串尚未结束,不确定是否存在敏感词
                        /*
                        以下代码并没有使用二分查找,因为以同一个字符开头的敏感词较少
                        例如,wordList中记录了所有敏感词的开头第一个字,它的数量通常会有上千个
                        假如现在锁定了字符“T”开头的敏感词,而“T”开头的敏感词只有10个,这时使用二分查找的效率反而低于顺序查找
                         */
                        word = word.next.get(__char__[j]);
                        if(word == null){
                            break;
                        }
                        j++;
                    }else { // 字符串已结束,存在敏感词汇
                        flag = true;
                        break;
                    }
                }
                if(word != null && word.next == null){
                    flag = true;
                }
                if(flag){ // 如果flag==true,说明检测出敏感粗,需要替换
                    while (i<j){
                        if(skip(__char__[i])){ // 跳过空格之类的无关字符,如果要把空格也替换成'*',则删除这个if语句
                            i++;
                            continue;
                        }
                        __char__[i] = replace;
                        i++;
                    }
                    i--;
                }
            }
        }
        return new String(__char__);
    }
 
    /**
     * 加载敏感词列表
     * @param words 敏感词数组
     */
    public static void loadWord(ArrayList<String> words){
        if(words == null) return;
        char[] chars;
        List now;
        Word word;
        wordList = new List();
        for(String __word__:words){
            if(__word__ == null) continue;
            chars = __word__.toCharArray();
            now = wordList;
            word = null;
            for(char c:chars){
                if(word != null) {
                    if(word.next == null) word.next = new List();
                    now = word.next;
                }
                word = now.get(c);
                if(word == null) word = now.add(c);
            }
        }
        sort(wordList);
    }
 
    /**
     * 加载敏感词txt文件,每个敏感词独占一行,不可出现空格,空行,逗号等非文字内容,必须使用UTF-8编码
     * @param path txt文件的绝对地址
     */
    public static void loadWordFromFile(String path){
        String encoding = "UTF-8";
        File file = new File(path);
        try{
            if(file.isFile() && file.exists()){
                InputStreamReader inputStreamReader = new InputStreamReader(
                        new FileInputStream(file),encoding
                );
                BufferedReader bufferedReader = new BufferedReader(inputStreamReader);
                String line;
                ArrayList<String> list = new ArrayList<>();
                while ((line = bufferedReader.readLine()) != null){
                    list.add(line);
                }
                bufferedReader.close();
                inputStreamReader.close();
                loadWord(list);
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
 
    /**
     * 对敏感词多叉树递增排序
     * @param list 待排序List
     */
    private static void sort(List list){
        if(list == null) return;
        Collections.sort(list); // 递增排序
        for(Word word:list){
            sort(word.next);
        }
    }
 
    /**
     * 判断是否跳过当前字符
     * @param c 待检测字符
     * @return true:需要跳过   false:不需要跳过
     */
    private static boolean skip(char c){
        for(char c1:skip){
            if(c1 == c) return true;
        }
        return false;
    }
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Main {
    public static void main(String[] args) throws Exception{
        SensitiveWordFilter.loadWordFromFile("D:/SensitiveWordList.txt");
        StringBuilder stringBuilder = new StringBuilder();
        long t1,t2;
        for(int i=0;i<100;i++){
            stringBuilder.append("123TM,D123");
        }
        String s = stringBuilder.toString();
        String result = null;
        t1 = System.nanoTime();
        for(int i=0;i<10000;i++){
            result = SensitiveWordFilter.Filter(s);
        }
        t2 = System.nanoTime();
        System.out.println(result);
        System.out.println((t2 - t1) / 1000000 + "毫秒");
    }
}

测试使用的敏感词库总共包含14596个敏感词(可能有个别重复),在测试代码里生成了一个长度为1000的字符串,总共包含100个相同敏感词,敏感词中间有逗号隔开


重复执行过滤10000次,并打印结果和时间,结果如下
DearXuan
可以看到程序成功地过滤了敏感词,并保留了逗号,总耗时335毫秒,平均每次过滤仅需要0.03毫秒,并且是在上万个敏感词和超长字符串的情况下.

源文件+敏感词列表

在寻找敏感词列表时发现很多人的分享都被取消了,为了防止敏感词列表被检测出敏感词,使用了zip格式并加密.敏感词库存在部分重复,不过不影响使用.

密码:dearxuan

密码:dearxuan

密码:dearxuan

源代码+敏感词列表

https://dearx.lanzoui.com/iIh95ralmrc

单独敏感词列表

https://dearx.lanzoui.com/iFQSrralmsd

更新于：2023年8月5日

算法

评论



😒再看，再看，再看就把你吃掉!