记得之前面试一个很牛的单位的时候,面试官问了一个问题是关于文字过滤的,当时由于水平有限,能想到的方法就是正则表达式了,最近在学习的过程中发现通过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之间的数学关系来实现状态机的转移。
相关推荐
在最近的开发中遇到了敏感词过滤,便去网上查阅了很多敏感词过滤的资料,在这里也和...下面这篇文章主要给大家介绍了关于java利用DFA算法实现敏感词过滤功能的相关资料,需要的朋友可以参考借鉴,下面来一起看看吧。
已在项目中使用,绝对是你想要的,高效的DFA算法实现的敏感词过滤功能。
java使用dfa算法实现敏感词过滤,此算法效率最高,附带了一个敏感词库,轻松搞定论坛网站的敏感词过滤问题。
java。dfa算法实现敏感词过滤
编译原理实验 NFA转DFA python实现
编译原理课的大作业 包含三个小实验 在一个cpp文件里 正则表达式转换为nfa nfa转换为dfa dfa最小化 个人原创代码
高效敏感词过滤JAVA实现(DFA算法) 5000字2ms 节点 + 2进制标识(节省空间/提高查询效率) 附源码、注释,附带专业敏感词库(3396个敏感词) 看得上就拿去用,替换下一两处util方法、改个路径即可 不求什么,...
本人用c++写的一个将NFA转换成DFA的程序,希望大家指教。
自己用C语言做的NFA到DFA的转换 有较为详细的备注,希望有所帮助。
主要介绍了Java使用DFA算法实现过滤多家公司自定义敏感字功能,结合实例形式分析了DFA算法的实现原理及过滤敏感字的相关操作技巧,需要的朋友可以参考下
NFA转换成DFA代码,计算理论Project1
Qt实现DFA敏感词过滤
程序用VS2015,C++来实现的,运用了很多C++的知识,实现了正则式—》NFA—》DFA—》DFA最小化。
DFA全称为:Deterministic Finite Automaton,即确定有穷自动机。其特征为:有一个有限状态集合和一些从一个状态通向另一个状态的边,每条边上标记有一个符号,其中一个状态是初态,某些状态是终态。但不同于不确定的...
NFA转换成DFA 编译原理 编译器 c++实现的转换 NFA转换成DFA 编译原理 编译器 c++实现的转换 NFA转换成DFA 编译原理 编译器 c++实现的转换
存储NFA与DFA,编程实现子集构造法将NFA转换成DFA。 (1)确定NFA与DFA的存储格式,为3个以上测试NFA准备好存储文件。 (2)用C或JAVA语言编写将NFA转换成DFA的子集构造法的程序。 (3)经测试无误。测试不易。可求...
采用c++语言编程,从而实现NFA与DFA之间的转换,代码简单
python实现正规式转换成NFA、NFA转换成DFA、DFA转换成MFA算法,并实现画出三类形图,可以在用户图形界面显示,也可以在文件夹中显示。
包含正则式转NFA、NFA转DFA(NFA确定化)、DFA转MFA(DFA最小化)三个程序,以及对应报告简述类的设计、包含的变量和思路。详细介绍参考:https://blog.csdn.net/newlw/article/details/123116153