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

40倍？
用xrange试试？
现在手头没环境，周一测下看。应该不会差这么多，也许是程序有问题。

xrange用在什么地方？把while替换掉吗？

在输入文本达到1m违禁词超过2000的时候确实相差40倍。python需要1600毫秒，而java只要40-50毫秒

而如果用附件中的输入文本和违禁词列表两者差距则只有5倍，在我的机器上，python是5毫秒，而java是1毫秒

要实现文字过滤有很多很好的算法，自己网上查查，用不着这么“高级”。

还有哪些算法,我能查到的只有一篇什么通过散列记录首字的方法,这个方法太小学生了.

看到你回复中"高级"两个字给了引号,让我感到汗颜,想必你有更好的算法,能否讨教一二(别跟我说双数组之类的,那个算法我早搞懂了)

本文给出的方法在时间复杂度上和双数组是一样的,但是空间复杂度比双数组要高,当然如果你能介绍一些比trie或者双数组trie更好的算法给我学习学习我也是非常感谢的,期待中

啥也不说了，看图

第一次运行是原程序，第二次是全部改用xrang以后的。

 

to 楼上:

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

   

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

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

其实，正则表达式和有限状态机是同构的。
所以…………

可以试试看这样的正则表达式

(关键词1|关键词2|关键词3)

还可以根据前缀再处理一下

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

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

一个正则表达是是 DFA 还是 NFA 就看表达式怎么写了
难道 java 不管如何都是 NFA 么？？？
另外，NFA 也是可以转化为 DFA 的么