使用DFA实现文字过滤

<?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

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







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


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

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

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

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

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

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

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

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

可是当我把 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))

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

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

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

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

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

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