敏感词过滤算法

Dfa和文字过滤

文字过滤是一般大型网站必不可少的一个功能，而且很多文字类网站更是需要。那么如何设计一个高效的文字过滤系统就是非常重要的了。

文字过滤需求简要描述：判断集合A中哪些子集属于集合B，拿javaeye来说，如果用户发表一篇文章（集合A），我们需要判断这篇文章里是否存在一些关键字是属于集合B，B一般来说就是违禁词列表。

看到这里，没有接触过的同学可能会想到contains,正则之类的方法，但是很遗憾，这些方法都是行不通的。唯一比较好的算法是DFA。

一，DFA简介：
学过编译原理的同学们一定知道，在词法分析阶段将源代码中的文本变成语法的集合就是通过确定有限自动机实现的。但是DFA并不只是词法分析里用到，DFA的用途非常的广泛，并不局限在计算机领域。

DFA的基本功能是可以通过event和当前的state得到下一个state，即event+state=nextstate,
我们来看一张到处都能找到的状态图：

大写字母是状态，小写字母是动作：我们可以看到S+a=U,U+a=Q,S+b=V等等。一般情况下我们可以用矩阵来表示整个状态转移过程：
－－－－－－－－－－－－－－－
状态/字符 a       b
S        U       V
U        Q       V
V        U       Q
Q        Q       Q

但是表示状态图可以有很多数据结构，上面的矩阵只是一个便于理解的简单例子。而接下来在本文提到的文字过滤系统中会使用另外的数据结构来实现自动机模型

二，文字过滤
在文字过滤系统中，为了能够应付较高的并发，有一个目标比较重要，就是尽量的减少计算，而在DFA中，基本没有什么计算，有的只是状态的转移。而要把违禁文字列表构造成一个状态机，用矩阵来实现是比较麻烦的，下面介绍一种比较简单的实现方式，就是树结构。

所有的违禁词其本质来说是有ascii码组成的，而待过滤文本其本质也是ascii码的集合，比如说：
输入是A=[101,102,105,97,98,112,110]
违禁词列表：
[102,105]
[98,112]
那么我们的任务就是把上面两个违禁词构造成一个DFA，这样输入的A就可以通过在这个DFA上的转移来实现违禁词查找的功能。

树结构实现这个DFA的基于的基本方法是数组的index和数组value之间的关系（在双数组trie中同样是基于这一基本方法）
那么102其实可以看作一个数组索引，而105是102这个索引指向的下一个数组中的一个索引，105后面没有值了，那就代表这个违禁词结束了。

通过这样一种方式，就可以构造出一颗DFA的树结构表示。

接着遍历输入文本中的每一个byte，然后在DFA中作状态转移就可以判断出一个违禁词是否出现在输入文本中。

public class DFA {
private String[] arr = {"DFA", "恶心", "DA"};
private Node rootNode = new Node('R');
private String content = "Hello DFA World DFA, HaHa! 恶心";
private List<String> words = new ArrayList<String>();
private List<String> word = new ArrayList<String>();
int a = 0;
private void searchWord() {
char[] chars = content.toCharArray();
Node node = rootNode;
while(a<chars.length) {
node = findNode(node,chars[a]);
if(node == null) {
node = rootNode;
a = a - word.size();
word.clear();
} else if(node.flag == 1) {
word.add(String.valueOf(chars[a]));
StringBuffer sb = new StringBuffer();
for(String str : word) {
sb.append(str);
}
words.add(sb.toString());
a = a - word.size() + 1;
word.clear();
node = rootNode;
} else {
word.add(String.valueOf(chars[a]));
}
a++;
}
}
private void createTree() {
for(String str : arr) {
char[] chars = str.toCharArray();
if(chars.length > 0)
insertNode(rootNode, chars, 0);
}
}
private void insertNode(Node node, char[] cs, int index) {
Node n = findNode(node, cs[index]);
if(n == null) {
n = new Node(cs[index]);
node.nodes.add(n);
}
if(index == (cs.length-1))
n.flag = 1;
index++;
if(index<cs.length)
insertNode(n, cs, index);
}
private Node findNode(Node node, char c) {
List<Node> nodes = node.nodes;
Node rn = null;
for(Node n : nodes) {
if(n.c==c) {
rn = n;
break;
}
}
return rn;
}
public static void main(String[] args) {
DFA dfa = new DFA();
dfa.createTree();
dfa.searchWord();
System.out.println(dfa.words);
}
private static class Node {
public char c;
public int flag; //1：表示终结，0：延续
public List<Node> nodes = new ArrayList<Node>();
public Node(char c) {
this.c = c;
this.flag = 0;
}
public Node(char c, int flag) {
this.c = c;
this.flag = flag;
}
}
}

秒客网

敏感词过滤算法

使用DFA实现文字过滤

相关文章