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

评论

25 楼 ahuaxuan 2009-02-28  

javaeyebird 写道

ps: 对别人说的仅仅几句话就做出"装"的判断，未免太草率了，有这个功夫还是多看看书，多学学理论

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

关于等价不等价的问题，你认为只要能实现同样功能的就叫等价，而我认为不同的方式实现同一个功能，代价不一样，我们只是从不同角度考虑问题，大家都没有必要继续把这牛角尖钻下去了

2关于多看看书多学学理论这件事我向来都是这样做的，最近也在复习数据结构，编译原理，而且在复习的过程中我也领悟到了很多东西，比如我现在就可以不用参考任何代码自己开发一个搜索引擎，这些都是从多看书多学理论里得来的，同时我也在没有参考任何代码的情况下自己写了一个python的工作流引擎（也是基于dfa），所以多看书多学理论的建议是正确的，我也会一直贯彻下去


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


ps:昨天为了省事把两个回帖放在一起，导致你的误会，我表示道歉，因为尊重是相互的

24 楼 javaeyebird 2009-02-28  

ahuaxuan 写道

1,nfa是可以转化成dfa,但是nfa和dfa是等价的我还是头一会听说,转化的话意味着其他代价,内存或者cpu等等,当然我的理解未必100%正确,我建议大家都回去再看看,到底nfa转成dfa需要哪些代价,如果不需要代价就是等价的，如果需要代价就不是等价的.查过之后你就不会"晕"了

等价不等价，不是看代价，而是看能力
对于每一个nfa N，必然存在一个dfa D，N所能接受的所有输入，D都能接受，并且，D所能接受的所有输入，N都能接受，这就是等价
许多自动机、形式语言、编译的书上都有证明和转换方法，这个链接可以参考：http://en.wikipedia.org/wiki/Powerset_construction
等价与否和效率没有关系，效率只是说对于需求，是否合适

正则即可以用NFA实现，也可以用DFA实现，《精通正则表达式》这本书上也有许多例子
诸如(ab|12|xyz)这样的正则表达式，使用DFA引擎的实现，预编译之后，匹配的时间复杂度和手工写的DFA是相当的，效率在一个等级上，当然实际的系数有所差别

这种基本的关键字匹配，是在严格的regular languages范围内，但是许多正则表达式库的语言能力已经超过了数学定义上的regular languages
我说“误导”，就是说，对于没有接触过这些理论的同学，楼主“行不通”的说法，会让他们以为正则表达式“不能”实现关键字匹配，而事实是不合适的正则引擎处理关键字匹配效率低，并非“不能”

ps: 对别人说的仅仅几句话就做出"装"的判断，未免太草率了，有这个功夫还是多看看书，多学学理论

23 楼 sdh5724 2009-02-28  

javaeyebird 写道

ahuaxuan 写道

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

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

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

引用

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

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

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

22 楼 ahuaxuan 2009-02-27  

javaeyebird 写道

ahuaxuan 写道

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

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

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

引用

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

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

1,nfa是可以转化成dfa,但是nfa和dfa是等价的我还是头一会听说,转化的话意味着其他代价,内存或者cpu等等,当然我的理解未必100%正确,我建议大家都回去再看看,到底nfa转成dfa需要哪些代价,如果不需要代价就是等价的，如果需要代价就不是等价的.查过之后你就不会"晕"了

2,是不是只是sun的正则不怎么样,前面其他兄弟的回帖已经说明问题了,我不重复了,看看前面兄弟用python和php的测试结果吧,再想想这段代码用c写之后的效率
----------------------------------------------------------------------

tanleihaoren 写道

这个呢！
http://www.cnblogs.com/sumtec/archive/2008/02/01/1061742.html

你真的看过了本文的内容和上面连接的这篇文章的内容了吗,你没发现有什么是相同的什么是不同的吗

----------------------------------------------------------------------

ps:其实我不想用这种语气说话,但是我更不喜欢 装 的回贴,我希望能看到有价值的建议,而不是压根就没有看过别人在说什么,就上来凑一句让自己可以得到自我满足的但是价值等于0的话,优秀的程序员不会做这种事情.

21 楼 javaeyebird 2009-02-27  

ahuaxuan 写道

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

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

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

引用

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

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

20 楼 tanleihaoren 2009-02-26  

这个呢！
http://www.cnblogs.com/sumtec/archive/2008/02/01/1061742.html

19 楼 ahuaxuan 2009-02-24  

sdh5724 写道

看看我的blog, 我已经详细阐述过违禁过滤算法。 使用的是dfa理论. 数据结构使用的是双数组。  如果想实时过滤， 那么使用正则表达就是死路一条。

你的blog之前我看过,当你写到分词实现文本过滤的时候,我当时还不知道怎么做,后来才知道其根本在于双数组算法.也看了你blog中双数组算法的描述,不过我觉得那篇文章(转载的那篇)写不咋滴,故意绕弯子,我搞了6个小时终于搞明白其原理

双数组方式我也知道怎么做,准备这个周末写一个试试,不想参考其他代码,等写不出来了再来参考,呵呵,谢谢

这个文章只是文字过滤的核心算法,对文字过滤系统来说只是一个半成品,我也只花了两个小时在上面,如果要做完善,还有很多工作要做

18 楼 sdh5724 2009-02-24  

看看我的blog, 我已经详细阐述过违禁过滤算法。 使用的是dfa理论. 数据结构使用的是双数组。  如果想实时过滤， 那么使用正则表达就是死路一条。不过。 楼主还有很多功能没有实现， 我实现了降噪出了， 简体／繁体， 拆字处理，有限同音字处理等等。

使用DFA是提高性能的最佳办法， 没有别的算法能超过了， 因为DFA过滤和词汇数量无关， 当然DFA在数据结构上的表示是非常困难的， 如果做不好就会造成性能反而非常不好。 目前使用双数组算法是比较好的。 不过我看过所有OPEN SOURCE的算法， 都有BUG。

17 楼 ahuaxuan 2009-02-24  

duka 写道

可是当我把 text.txt 文档加到 1.5MB 后：

py DFA:
cost time :  3.39100003242
I have find some words as  10848
python 1695
违禁词 4068
DFA 4068
ahuaxuan 1017

py 正规:
cost time :  0.047000169754
I have find some words as  10848
python: 1695
DFA: 4068
违禁词: 4068
ahuaxuan: 1017

在违禁词数量比较少的情况下(你的测试只有4个违禁词),正则表达式肯定有优势,因为python的正则是用c实现的,所以当然快啊,如果我的代码用c写,肯定不会比正则慢呀,所以如果要真正的比较,你还需要用2m的违禁词库来测试,这样当构造一个巨大的nfa,然后再在这个nfa上作状态转移,那么即使用c写的正则也未必有python写的快,你可以试一下

16 楼 duka 2009-02-24  

可是当我把 text.txt 文档加到 1.5MB 后：

py DFA:
cost time :  3.39100003242
I have find some words as  10848
python 1695
违禁词 4068
DFA 4068
ahuaxuan 1017

py 正规:
cost time :  0.047000169754
I have find some words as  10848
python: 1695
DFA: 4068
违禁词: 4068
ahuaxuan: 1017

#encoding:UTF-8  
import sys,re
from time import time

beign=time()  
txt = open('text.txt', 'rb').read()
wf = open('words.txt', 'rb')
ws = [w.strip() for w in wf]
ws = set(ws)
r = re.compile('|'.join(ws))
found = r.findall(txt)

print "cost time : ", time()-beign  
print "I have find some words as ", len(found)  
for k in ws:  
    print "%s: %s" % (k, found.count(k))

15 楼 ahuaxuan 2009-02-23  

syre 写道

不过一般违禁词也就几千个了，常用词总共才百万吧

这样吧,假设常用词是1w个,这个应该还算少的,问题是构造正则表达式,然后匹配有两个缺点:
1,速度慢
2,硬件消耗高(正则方式对cpu消耗应该比这个dfa的高很多)

综上而言,我觉得还是自己用树构造dfa来得好

14 楼 syre 2009-02-23  

不过一般违禁词也就几千个了，常用词总共才百万吧

13 楼 ahuaxuan 2009-02-23  

python的正则也是用c写的,上面这个要7毫秒,而同样的算法(本文的算法),同样的文本和违禁词(就是附件中的)用java写只要0.9毫秒,速度不是一个级别的.当然这个也可以撇开不说.

但是我有一个重要的问题:就是一旦词汇较多的时候,比如拿1000个违禁词,或者10000,10w个违禁词,那么正则的方法将如何呢,只有把这个测试一下才能说明问题.不过在java里我已经测试过了,真的很慢,和自己用树实现DFA的算法比实在太慢了.

如果把这个算法的python实现改成c的实现,然后用python调用,速度可想而知了(可惜俺的c不咋滴)

12 楼 syre 2009-02-23  

python 的正则版本：

#encoding:UTF-8
import sys
from time import time
import re

txt = unicode(open('text.txt', 'rb').read(), 'utf-8')
wf = open('words.txt', 'rb').readlines()
ws = []
for w in wf:
    ws.append(re.escape(unicode(w.strip(), 'utf-8')))

reg = '|'.join(ws)

beign=time()
found = re.findall(reg, txt)
result = {}

for m in found:
    if result.has_key(m):
        result[m]+= 1
    else:
        result[m] = 1

print "cost time : ", time()-beign
print "I have find some words as ", len(found)
for k in result:
    print "%s: %s" % (k, result[k])

结果：

cost time :  0.00756096839905
I have find some words as  32
python: 5
DFA: 12
违禁词: 12
ahuaxuan: 3

试了一下1000个 word 的列表
确实你的实现更快一些

lz的dfa：
0.0169320106506

python正则：
0.168184995651

php正则：
0.038794040679932

11 楼 ahuaxuan 2009-02-23  

syre 写道

写了一个 php 的用正则实现的版本


结果：
0.00029492378234863
32
Array
(
    [违禁词] => 12
    [DFA] => 12
    [ahuaxuan] => 3
    [python] => 5
)


同一台机器上python程序的结果：
cost time :  0.0110309123993
I have find some words as  32
python 5
违禁词 12
DFA 12
ahuaxuan 3

php 实际上用的是 pcre

pcre是用c写得吧,如果我得那段脚本用c写不知道要快多少倍了,而且我之前也说过,python写这个确实不怎么快.







-----------------------------------


对了还有一个问题,就是违禁词多得时候,你拿1000个词汇构造一个正则试试,看看速度怎么样,词汇少得话,NFA很小,所以速度快,词汇一多,就不行了

10 楼 syre 2009-02-23  

<?php
$f = file('words.txt');
$words = array();
foreach ($f as $w) {
    $words[]= preg_quote(trim($w), '/');
}
$text = file_get_contents('text.txt');

$start = microtime(true);
$reg = '/' . implode('|', $words) . '/S';

preg_match_all($reg, $text, $m);

$result = array();
$total = 0;
foreach ($m[0] as $w) {
    if (!isset($result[$w])) {
        $result[$w] = 1;
    } else {
        $result[$w]++;
    }
    $total++;
}
$end = microtime(true);
echo $end - $start, "\n";
echo $total, "\n";

print_r($result);

写了一个 php 的用正则实现的版本


结果：
0.00029492378234863
32
Array
(
    [违禁词] => 12
    [DFA] => 12
    [ahuaxuan] => 3
    [python] => 5
)


同一台机器上python程序的结果：
cost time :  0.0110309123993
I have find some words as  32
python 5
违禁词 12
DFA 12
ahuaxuan 3

php 实际上用的是 pcre

9 楼 syre 2009-02-23  

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

8 楼 ahuaxuan 2009-02-23  

syre 写道

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

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

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

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

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

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

7 楼 syre 2009-02-23  

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

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

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

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

6 楼 ahuaxuan 2009-02-23  

to 楼上:

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

   

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

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