【问题描述】
文档检查的时候,我们希望过滤掉敏感词,例如有字符串A="asbcd",我们希望过滤掉B=“sb”,需要在A中找到B,然后,做相关的标记或者替换。
【可行思路】
1、暴力匹配--这个就算了,只是说说而已,实际应用中很少的。
2、正则表达式
3、利用DFA实现文字过滤
在文章中提到正则表达式不是一个很好的选择,DFA才是。
本文将实现正则表达式和DFA的方法,并从时间上给出二者比较。
【算法选择】
==========================DFA=================================
#encoding:utf-8 from time import time words = [ 'fuck', ] #wordTree = wordTree.append(0) def create_word_tree(words_list): wordTree = [None for i in range(0,256)] wordTree = [wordTree,0] for word in words_list: # 每个单词对应一个tree tree = wordTree[0] for i in range(0,len(word)): little = word[i] index = ord(little) # 已经到最后一个字母了 if i == len(word) -1: tree[index] = 1 else: tree[index] = [[None for x in range(0,256)],1] tree = tree[index][0] return wordTree def translate(string,tree): temp = tree result = '' for little in string: index = ord(little) temp = temp[0][index] if temp == None: temp = tree #print 'can not find' else: result += chr(index) if temp == 1: return string.replace(result,'*') tree = create_word_tree(words) fileP = open('test.txt') s = fileP.read() beginTime = time() s2 = translate(s,tree) endTime = time() print endTime - beginTime fileQ = open('test_result2.txt', 'w') fileQ.write(s2) fileP.close() fileQ.close()
PS:本程序基本用的上面链接中给出的程序的写法,逻辑上好像有点问题,后面的时间上的比较在保证输出结果一致的情况下给出。
==========================正则================================
#encoding:utf-8 import re from time import time words = [ 'fuck' ] print 'start...' def translate(s): reStr = '' wordLen = len(words) count = 0; for word in words: count = count + 1 if wordLen == count: reStr = reStr + word else: reStr = reStr + word + '|' #print reStr pattern = re.compile(reStr) s2 = re.sub(pattern, '**', s) #print s2 return s2 fileP = open('test.txt') s = fileP.read() beginTime = time() s2 = translate(s) endTime =time() print endTime - beginTime fileQ = open('test_result.txt', 'w') fileQ.write(s2) fileP.close() fileQ.close()
【注意】-------------------------------
正则方法中的translate函数
reStr = '' wordLen = len(words) count = 0; for word in words: count = count + 1 if wordLen == count: reStr = reStr + word else: reStr = reStr + word + '|'
这一段代码是用敏感词求正则表达式(和DFA中建立wordTree一样属于过滤的前处理)比较的时候应该移到translate函数外。
重新计算时间,不影响结论。
-------------------------------------------
时间上的比较PS : 真的要给一个大一点的输入文件才行。
DFA | 正则 | |
秒数 | 0.09 | 0.31 |
正则表示式来实现这个问题更直观容易实现,但DFA在计算上更有效。