使用DFA实现文字过滤

/**
  * author：ahuaxuan(张荣华)
  * date:2009-02-21
  */

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中作状态转移就可以判断出一个违禁词是否出现在输入文本中。

下面贴出ahuaxuan基于以上理论用python写的一段文字过滤脚本：

#encoding:UTF-8
import sys
from time import time
'''
@author: ahuaxuan 
@date: 2009-02-20
'''

wordTree = [None for x in range(256)]
wordTree.append(0)
nodeTree = [wordTree, 0]
def readInputText():
    txt = ''
    for line in open('text.txt', 'rb'):
        txt = txt + line
    return txt

def createWordTree():
    awords = []
    for b in open('words.txt', 'rb'):
        awords.append(b.strip())
    
    for word in awords:
        temp = wordTree
        for a in range(0,len(word)):
            index = ord(word[a])
            if a < (len(word) - 1):
                if temp[index] == None:
                    node = [[None for x in range(256)],0]
                    temp[index] = node
                elif temp[index] == 1:
                    node = [[None for x in range(256)],1]
                    temp[index] = node
                
                temp = temp[index][0]
            else:
                temp[index] = 1
    

def searchWord(str):
    temp = nodeTree
    words = []
    word = []
    a = 0
    while a < len(str):
        index = ord(str[a])
        temp = temp[0][index]
        if temp == None:
            temp = nodeTree
            a = a - len(word)
            word = []
        elif temp == 1 or temp[1] == 1:
            word.append(index)
            words.append(word)
            a = a - len(word) + 1 
            word = []
            temp = nodeTree
        else:
            word.append(index)
        a = a + 1
    
    return words

if __name__ == '__main__':
    #reload(sys)  
    #sys.setdefaultencoding('GBK')  
    input2 = readInputText()
    createWordTree();
    beign=time()
    list2 = searchWord(input2)
    print "cost time : ",time()-beign
    strLst = []
    print 'I have find some words as ', len(list2)
    map = {}
    for w in list2:
        word = "".join([chr(x) for x in w])
        if not map.__contains__(word):
            map[word] = 1
        else:
            map[word] = map[word] + 1
    
    for key, value in map.items():
        print key, value

输入文本就是本文（不包含下面的示例结果文本）
运行结果示例：

python 5
违禁词 12
DFA 12
ahuaxuan 3

       



当然用python实现以上算法只是为了便于理解，事实上python的速度实在是太慢了，同样的违禁词列表，同样的输入文本，python写的比用java写的差了40倍左右。理论上来讲在这个功能上，用python调用c写的功能比较合适。

而这种方式比较大的缺点是内存使用虑较大，因为有很多数组上的元素是None，引用的空间会消耗大量的内存，这个和违禁词的长度和个数成正比。比较好的方式还是用双数组实现DFA，这个方式使用内存空间较小，而基本原理还是一样，通过两个数组的index和value之间的数学关系来实现状态机的转移。

附件中附带违禁词和输入文本的测试，大家可以运行一下看看效果。

由于ahuaxuan水平有限，如代码中出现问题，还望不吝指出，谢谢。

评论

65 楼 mistbow 2014-02-26  

“接着遍历输入文本中的每一个byte”

请问上面数组的例子，这个文本应该怎么去遍历树呢？求教了

64 楼 不是流氓 2010-01-04  

拜读神贴，受益匪浅

敏感词里面有：“中国”，“中国人”这样的场景是不是
elif temp == 1 or temp[1] == 1: 
这句处理？

python数组越界会报错么？好象是会的？
朦胧中.......

63 楼 solonote 2009-12-24  

要实现我提到的那种需求,DAF树上应该需要多个指针吧,而且还要多个word数组来装状态未结束的词.
不过算法确实还是基于回退和继续查找的.
呵呵 看起来有点怪怪的
中(等待获得词状态) -> 中国(获得词状态) -> 有子节点所以继续转换 -> 中国人(获得词状态) -> 没有子节点 退出转换.

62 楼 pf_miles 2009-12-16  

不错，思路清晰～那么稀疏的数组想办法压缩压缩就好了

61 楼 ahuaxuan 2009-12-14  

solonote 写道

text.txt:
中国人
words.txt:
中国
中国人

result:
cost time :  0.0160000324249
I have find some words as  1
中国 1

这种情况有问题的,而且不能以ab,bc这种情况来回退.
请问楼主如何处理?

再复杂一点:
words.txt:
中国 国人 中国人

我期望的结果是:
中国 1
国人 1
中国人 1

请教一下要实现这种需求,应该在算法上做些什么改进?

一般来说如果是违禁词，那么只要有一个满足条件，那么就认为该文是有问题的，你应该不是用在违禁词过滤的场景了吧，像你这样的需求理论上来讲是没有问题，只需要在状态转换的过程中，每次遇到一个符合条件的词之后，继续寻找，以满足最大匹配，那么就可以找出中国，和中国人，我代码中也有体现。而中国人和国人的问题，就需要遇到匹配词之后，指针需要返回到刚才遇到匹配词的位置+1这个位置上，然后重新做状态转移。这样就应该满足你的需求了。

60 楼 ahuaxuan 2009-12-14  

nod0620 写道

还有个问题，我的违禁词汇是av，用户输入have，但是被检测出来了，这个该怎么改进

这个可以用前后是否是空格来判定，你是英文的？如果是中文基本不需要考虑这个问题。

59 楼 nod0620 2009-12-10  

pantiansheng 写道

楼主
你这样做还有一个问题
你采用GBK编码
假如某个代检查的文本的编码为：45，47，12，23，23，20
如果关键字中编码为：[b]47，12，23，23[/b]

红色标记处
这样会导致查询到了关键字，但是实际并不是关键字中的

我现在就遇到这个问题

还有个问题，我的违禁词汇是av，用户输入have，但是被检测出来了，这个该怎么改进

58 楼 solonote 2009-12-04  

text.txt:
中国人
words.txt:
中国
中国人

result:
cost time :  0.0160000324249
I have find some words as  1
中国 1

这种情况有问题的,而且不能以ab,bc这种情况来回退.
请问楼主如何处理?

再复杂一点:
words.txt:
中国 国人 中国人

我期望的结果是:
中国 1
国人 1
中国人 1

请教一下要实现这种需求,应该在算法上做些什么改进?

57 楼 ahuaxuan 2009-11-19  

mikeandmore 写道

ahuaxuan 写道

to 楼上:

你是把while改成xrange吗??
同学,这样改有bug的

   

for a in xrange(10):
        print a
        a = a + 5

这段代码输出的是0-9,也就是说a=a+5并没有影响到xrange里的a,它之所以变快是因为改成这样会跳过很多byte,所以看上去变快了

In [1]: for a in range(10):
   ...:     print a
   ...:     a = a + 5
   ...:
0
1
2
3
4
5
6
7
8
9

In [2]: for a in xrange(10):
   ...:     print a
   ...:     a = a + 5
   ...:
0
1
2
3
4
5
6
7
8
9

我并没有说xrange有bug,你要仔细看一下我的代码，那句话是有上下文的。

56 楼 mikeandmore 2009-11-19  

ahuaxuan 写道

to 楼上:

你是把while改成xrange吗??
同学,这样改有bug的

   

for a in xrange(10):
        print a
        a = a + 5

这段代码输出的是0-9,也就是说a=a+5并没有影响到xrange里的a,它之所以变快是因为改成这样会跳过很多byte,所以看上去变快了

In [1]: for a in range(10):
   ...:     print a
   ...:     a = a + 5
   ...:
0
1
2
3
4
5
6
7
8
9

In [2]: for a in xrange(10):
   ...:     print a
   ...:     a = a + 5
   ...:
0
1
2
3
4
5
6
7
8
9

55 楼 melin 2009-11-18  

我用java写了一个，直接基于字符构造一个树、

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;
		}
	}
}

54 楼 sdh5724 2009-05-23  

20多M内存不算什么了.  这个算法应该是最快的了. O(N)的复杂度. 难道还能写出log(N)的复杂度?  这个算法唯一是在增加和删除, 内存压缩, 内存利用效率上, 看你怎么写程序了. 但是国外有不少关于这个算法增强的paper, 文化低, 看的不是很明白.

这个算法结合动态规划算法 能做出比较精确的中文分词---非专业分词使用是相当好了. 我在实现过一部分:)

很不想做文字过滤....可还是做了. 不然天朝锦衣卫天天找你家麻烦.

53 楼 pantiansheng 2009-05-21  

删除，或者修改的时候还是比较麻烦的

52 楼 ahuaxuan 2009-05-21  

pantiansheng 写道

这个我也考虑过
就是觉得这样的话系统有一段时间占用的内存过大
不过不这样的话
也没有什么好的办法
我测了一下我的
2w个关键字
大约需要23M内存

看了一下，不需要重新构造，只需要把新增的关键词拿出来，执行建树时for循环里的代码就可以了

51 楼 pantiansheng 2009-05-21  

ahuaxuan 写道

灰~机 写道

ahuaxuan 写道

1000个小case了，6w个关键字在jvm占用180m的内存。还说得过去。

写了个PHP的该算法，又用php的array特性，缩小了Trie树占的内存量。效率还算过得去
比preg_match_all那个正则方法效率高6倍左右

pantiansheng 写道

楼主
请教个问题
在实时情况下
如何保证重新加载同步问题

只能重建这颗书，建完之后替换树，呵呵

这个我也考虑过
就是觉得这样的话系统有一段时间占用的内存过大
不过不这样的话
也没有什么好的办法
我测了一下我的
2w个关键字
大约需要23M内存

50 楼 ahuaxuan 2009-05-21  

灰~机 写道

ahuaxuan 写道

1000个小case了，6w个关键字在jvm占用180m的内存。还说得过去。

写了个PHP的该算法，又用php的array特性，缩小了Trie树占的内存量。效率还算过得去
比preg_match_all那个正则方法效率高6倍左右

pantiansheng 写道

楼主
请教个问题
在实时情况下
如何保证重新加载同步问题

只能重建这颗书，建完之后替换树，呵呵

49 楼 pantiansheng 2009-05-21  

楼主
请教个问题
在实时情况下
如何保证重新加载同步问题

48 楼 灰~机 2009-05-21  

ahuaxuan 写道

1000个小case了，6w个关键字在jvm占用180m的内存。还说得过去。

写了个PHP的该算法，又用php的array特性，缩小了Trie树占的内存量。效率还算过得去
比preg_match_all那个正则方法效率高6倍左右

47 楼 bachmozart 2009-05-21  

ahuaxuan 写道

bachmozart 写道

为了能看懂楼主的代码，又复习了一遍python,呵呵
`````````````````

文本abc
关键词，ab，bc，回退一步是为了尽量搜索出其他关键字

明白了，多谢

46 楼 ahuaxuan 2009-05-21  

bachmozart 写道

为了能看懂楼主的代码，又复习了一遍python,呵呵
`````````````````

文本abc
关键词，ab，bc，回退一步是为了尽量搜索出其他关键字

灰~机 写道

对于这种方法，如果用PHP来写的话，如果有1000个禁用词语，光一个Trie树就需要相当大的内存占用量，速度应该快不了，貌似不怎么可取哦

1000个小case了，6w个关键字在jvm占用180m的内存。还说得过去。