python 实现敏感词过滤的方法
如下所示:
#!/usr/bin/python2.6 #-*-coding:utf-8-*- importtime classNode(object): def__init__(self): self.children=None #TheencodeofwordisUTF-8 defadd_word(root,word): node=root foriinrange(len(word)): ifnode.children==None: node.children={} node.children[word[i]]=Node() elifword[i]notinnode.children: node.children[word[i]]=Node() node=node.children[word[i]] definit(path): root=Node() fp=open(path,'r') forlineinfp: line=line[0:-1] #printlen(line) #printline #printtype(line) add_word(root,line) fp.close() returnroot #TheencodeofwordisUTF-8 #TheencodeofmessageisUTF-8 defis_contain(message,root): foriinrange(len(message)): p=root j=i while(j测试结果:
1)敏感词100个
----------------dfa----------- ***message***224 0.325479984283 ------------normal-------------- ***message***224 Thecountofword:100 0.1073501110082)敏感词1000个
----------------dfa----------- ***message***224 0.324251890182 ------------normal-------------- ***message***224 Thecountofword:1000 1.05939006805从上面的实验我们可以看出,在DFA算法只有在敏感词较多的情况下,才有意义。在百来个敏感词的情况下,甚至不如普通算法
下面从理论上推导时间复杂度,为了方便分析,首先假定消息文本是等长的,长度为lenA;每个敏感词的长度相同,长度为lenB,敏感词的个数是m。
1)DFA算法的核心是构建一棵多叉树,由于我们已经假设,敏感词的长度相同,所以树的最大深度为lenB,那么我们可以说从消息文本的某个位置(字节)开始的某个子串是否在敏感词树中,最多只用经过lenB次匹配.也就是说判断一个消息文本中是否有敏感词的时间复杂度是lenA*lenB
2)再来看看普通做法,是使用for循环,对每一个敏感词,依次在消息文本中进行查找,假定字符串是使用KMP算法,KMP算法的时间复杂度是O(lenA+lenB)
那么对m个敏感词查找的时间复杂度是(lenA+lenB)*m
综上所述,DFA算法的时间复杂度基本上是与敏感词的个数无关的。
以上这篇python实现敏感词过滤的方法就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持毛票票。