使用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水平有限，如代码中出现问题，还望不吝指出，谢谢。

评论

45 楼 灰~机 2009-05-21  

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

44 楼 bachmozart 2009-05-21  

为了能看懂楼主的代码，又复习了一遍python,呵呵
有个问题没弄明白，能否请教一下：
就是在searchWord函数里面，应该是对传入参数str文本进行DFA状态转移,代码大意是

while a < len(str):      
        if temp == None:
            //状态转移失败，回溯字符串指针
            //如果之前word已经保存了2个字符，则 指针-2
            a = a - len(word)           
        elif temp == 1 or temp[1] == 1:
            //状态转移结束，成功匹配到一个字符串
            //这里不理解了，既然已经成功匹配到一个串，那么无需回溯指针呀
            //直接跳过当前成功匹配的串，继续DFA为什么不可以呢？
           
            a = a - len(word) + 1    //为什么成功还要回溯指针呢？        
        else:
            //状态转移，未结束
            word.append(index)
        a = a + 1

不知道我那里理解的有问题，还望不吝赐教，先谢过啦

43 楼 ahuaxuan 2009-05-19  

pantiansheng 写道

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

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

我现在就遇到这个问题

这个只要转码就行了，把关键字和文本弄成一样编码的，然后再匹配

42 楼 pantiansheng 2009-05-18  

刚才提的问题是我这两天碰到的
不过我用的是AC算法实现

41 楼 pantiansheng 2009-05-18  

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

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

我现在就遇到这个问题

40 楼 dd2086 2009-03-21  

谁有java版的DFA文字过滤？

39 楼 sdh5724 2009-03-15  

xdsnet 写道

上W的违禁词？这个从社会生活的领域来看，是不可能的吧，如果这样，大家就不用说话啦，呵呵。
估计这个量到K级别就很多很多啦。

这个算法不仅仅可以用在违禁词过滤上， 实际上， 在分词中用的最多的。  上百万的词汇， 随便就有了。

开拓点思路吧。

38 楼 ahuaxuan 2009-03-12  

joshzhu 写道

首先，我声明一下我的政治态度：
我反对限制言论自由的行为。

然后，我想说的是：
短期山寨是可以的，但是不要长期山寨下去。在串匹配领域早已经有一大堆成熟的算法，最起码像AC、WM这些算法应该听说过才对，而不是发明方形的轮子。想扫盲的，看看这本书吧：
http://www.dcc.uchile.cl/~gnavarro/FPMbook/
中文版名字叫《柔性字符串匹配》。

我也声明我的政治态度,我更坚决反对言论自由,这一点俺们是一致得

对于AC算法,我也刚刚也上网找了一点资料,那我先贴点我找到的:

引用

AC的局限性是对空间需求比较大，如果匹配模式太多，会造成空间的大量占用，甚至系统崩溃。所以在模式有限不多的模式下，AC是能够很好满足需求的要求的。

其实我在主贴也说过这样的话,再来一段呗:

引用

AC自动机匹配算法基于一种精巧的模式树(Trie)性质的一棵树

本文的算法也是这样呢(注意名字:使用DFA实现文字过滤),只是无意中出奇的类似,难道本文就是山寨版的AC?

只是俺之前不知道AC也是这种思路而已,难道是不识庐山真面目,只缘身在此山中

37 楼 joshzhu 2009-03-12  

首先，我声明一下我的政治态度：
我反对限制言论自由的行为。

然后，我想说的是：
短期山寨是可以的，但是不要长期山寨下去。在串匹配领域早已经有一大堆成熟的算法，最起码像AC、WM这些算法应该听说过才对，而不是发明方形的轮子。想扫盲的，看看这本书吧：
http://www.dcc.uchile.cl/~gnavarro/FPMbook/
中文版名字叫《柔性字符串匹配》。

36 楼 xdsnet 2009-03-12  

上W的违禁词？这个从社会生活的领域来看，是不可能的吧，如果这样，大家就不用说话啦，呵呵。
估计这个量到K级别就很多很多啦。

35 楼 sdh5724 2009-03-04  

我是是完成过整个代码的， 信不信随便楼上的了。

34 楼 acdc 2009-03-03  

sdh5724 写道

javaeyebird 写道

ahuaxuan 写道

这种方法早想过了,不行滴
java里的正则是NFA实现的,由于NFA是不确定的自动机,event+state并不能准确的得到下一个state,所以性能上```,呵呵.

而且这种方式也不能准确的得到每个词汇出现的频率,这也是个大问题.

晕，NFA和DFA是等价的。。。。
正则表达式完全可以做到关键字过滤，当然sun jre的正则实现，效率不怎么样
所以，你的原话：

引用

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

对没有接触过的同学，会产生误导，应该说是"....contains,jre的正则实现...这些方法的效率都是太差的..."

谁要能正则做到DFA 关键字匹配效率的效率. 我就转行.

建议考虑直接出家～～～

33 楼 hh9527 2009-03-03  

不知道 PERFECT HASH 对这项工作有没有帮助？楼主有没有分析过？
-- 对这个领域不了解仔细想了一下，发现 PERFECT HASH 也没有用，就当我没说，呵呵 --

32 楼 sdh5724 2009-03-02  

codeutil 写道

在实际应用中，实时输出是没半点问题的，因为关键字树是全局的，
java的hashcode是int，而字符仅仅是char，也就是说char自己就是hash值。
如果说需要优化的话，也只需要初始化map的时候把容量分配大点，减少hash冲突即可。

还有就是不定制 CharHashMap的话，就为避免自动拆装箱产生太多临时对象。
需要对Character对象进行缓存，不试用自动拆装箱，而用数组下标来获取Character对象。

 static final Character cache[] = new Character[65536];

 static {
  for (int i = 0; i < cache.length; i++)
   cache[i] = new Character((char) i);
 }

Character 的hashcode方法是：

    public int hashCode() {
        return (int)value;
    }

sdh5724 写道

codeutil 写道

关键字过滤使用正则是死路一条.

现在有些时候连长七八十个字符的url地址都要加到关键字列表。

用hashmap将关键字库包装构造成多节点树，Hashmap的key是单个char，value是树节点，对文本进行树查找就可以了。

对char稍作转换，就可以实现按同音字过滤，或繁简体，或全半角，或非汉字字符隔开的，或火星文等，通杀。

对于过滤关键字， 估计你说的是够用了。 但是， 如果想做输出实时过滤， 还是困难了点。 HASH还是很消耗时间。 另外， 如果字典大了， 内存收集管理很消耗的， 节点会变的非常多， 对于DFA树， 本来用HASH是最容易表述的， 但是性能诧异还是很大。 最好的办法使用双数组表述DFA状态。

类似处理char的时候， 如果每个char都call一次函数， 你测试看看， 性能差别是多少。 以前我就用charAt(i)来处理String, 性能差别一倍。 hash对于dfa来说， 确实代码很容易写， 如果是给予dfa的分词基础系统，那就很恶心了， 如果你有一个1百万词汇的字典， 这个hash数会变的异常大。 而且都是对象包对象。

31 楼 codeutil 2009-03-01  

在实际应用中，实时输出是没半点问题的，因为关键字树是全局的，
java的hashcode是int，而字符仅仅是char，也就是说char自己就是hash值。
如果说需要优化的话，也只需要初始化map的时候把容量分配大点，减少hash冲突即可。

还有就是不定制 CharHashMap的话，就为避免自动拆装箱产生太多临时对象。
需要对Character对象进行缓存，不试用自动拆装箱，而用数组下标来获取Character对象。

 static final Character cache[] = new Character[65536];

 static {
  for (int i = 0; i < cache.length; i++)
   cache[i] = new Character((char) i);
 }

Character 的hashcode方法是：

    public int hashCode() {
        return (int)value;
    }

sdh5724 写道

codeutil 写道

关键字过滤使用正则是死路一条.

现在有些时候连长七八十个字符的url地址都要加到关键字列表。

用hashmap将关键字库包装构造成多节点树，Hashmap的key是单个char，value是树节点，对文本进行树查找就可以了。

对char稍作转换，就可以实现按同音字过滤，或繁简体，或全半角，或非汉字字符隔开的，或火星文等，通杀。

对于过滤关键字， 估计你说的是够用了。 但是， 如果想做输出实时过滤， 还是困难了点。 HASH还是很消耗时间。 另外， 如果字典大了， 内存收集管理很消耗的， 节点会变的非常多， 对于DFA树， 本来用HASH是最容易表述的， 但是性能诧异还是很大。 最好的办法使用双数组表述DFA状态。

30 楼 ahuaxuan 2009-03-01  

我也用hash做过dfa，但是不是用在文字过滤里，而是用在工作流引擎里，用在工作流引擎里是没有问题的，不过用在高性能场景的文字过滤里，hash函数确实会消耗更多的cpu，从python的测试代码来看用hash方式消耗的时间是本文所给方法的2倍以上。这还是没有并发的场景。

不过用在工作流引擎里我觉得倒确实比较合适的。因为流程状态转化的时候不需要象文字过滤那样循环文字的长度，只要根据当前状态和动作＋条件就能得到下一个状态，所以速度上是能够满足要求的。

29 楼 sdh5724 2009-03-01  

codeutil 写道

关键字过滤使用正则是死路一条.

现在有些时候连长七八十个字符的url地址都要加到关键字列表。

用hashmap将关键字库包装构造成多节点树，Hashmap的key是单个char，value是树节点，对文本进行树查找就可以了。

对char稍作转换，就可以实现按同音字过滤，或繁简体，或全半角，或非汉字字符隔开的，或火星文等，通杀。

对于过滤关键字， 估计你说的是够用了。 但是， 如果想做输出实时过滤， 还是困难了点。 HASH还是很消耗时间。 另外， 如果字典大了， 内存收集管理很消耗的， 节点会变的非常多， 对于DFA树， 本来用HASH是最容易表述的， 但是性能诧异还是很大。 最好的办法使用双数组表述DFA状态。

28 楼 javaeyebird 2009-02-28  

ahuaxuan 写道

3但是有点我们必须承认的是，正则（不光是java实现，还有python，php）在效率上确实比不上本文的方法和双数组，这个我们应该能够达成共识，如果不能达成共识，那么你可以拿出你的测试数据来证明，我是很欢迎的

python, php我没有详细了解过，而sun jre的NFA的正则实现对于关键字过滤确实效率不够高

codeutil 写道

关键字过滤使用正则是死路一条.
现在有些时候连长七八十个字符的url地址都要加到关键字列表。
用hashmap将关键字库包装构造成多节点树，Hashmap的key是单个char，value是树节点，对文本进行树查找就可以了。
对char稍作转换，就可以实现按同音字过滤，或繁简体，或全半角，或非汉字字符隔开的，或火星文等，通杀。

你说的和楼主说的，都是DFA中常采用的数据结构
但除此之外，再采用如状态最少化、dead状态消除等优化措施，对关键字过滤会有更好的效果，龙书上有对这两个优化有简明的描述

27 楼 javaeyebird 2009-02-28  

ahuaxuan 写道

1你可能有点误会，装不是说你的，你提出的建议也是不错的，回头我去看看。正则可以用dfa也可以用nfa，但是遗憾的是据我所知，只有as里的正则是dfa，其他语言的好像都是nfa，如果我说错了，请指正

egrep支持dfa, awk也支持, 《精通正则表达式》那本书还有其他例子
当然这些东西在程序员里流行度还是不够的

26 楼 codeutil 2009-02-28  

关键字过滤使用正则是死路一条.

现在有些时候连长七八十个字符的url地址都要加到关键字列表。

用hashmap将关键字库包装构造成多节点树，Hashmap的key是单个char，value是树节点，对文本进行树查找就可以了。

对char稍作转换，就可以实现按同音字过滤，或繁简体，或全半角，或非汉字字符隔开的，或火星文等，通杀。