python 实现敏感词过滤的方法
作者:isoleo 发布时间:2022-08-09 10:22:51
标签:python,敏感词,过滤
如下所示:
#!/usr/bin/python2.6
# -*- coding: utf-8 -*-
import time
class Node(object):
def __init__(self):
self.children = None
# The encode of word is UTF-8
def add_word(root,word):
node = root
for i in range(len(word)):
if node.children == None:
node.children = {}
node.children[word[i]] = Node()
elif word[i] not in node.children:
node.children[word[i]] = Node()
node = node.children[word[i]]
def init(path):
root = Node()
fp = open(path,'r')
for line in fp:
line = line[0:-1]
#print len(line)
#print line
#print type(line)
add_word(root,line)
fp.close()
return root
# The encode of word is UTF-8
# The encode of message is UTF-8
def is_contain(message, root):
for i in range(len(message)):
p = root
j = i
while (j<len(message) and p.children!=None and message[j] in p.children):
p = p.children[message[j]]
j = j + 1
if p.children==None:
#print '---word---',message[i:j]
return True
return False
def dfa():
print '----------------dfa-----------'
root = init('/tmp/word.txt')
message = '四处乱咬乱吠,吓得家中11岁的女儿躲在屋里不敢出来,直到辖区派出所民警赶到后,才将孩子从屋中救出。最后在征得主人同意后,民警和村民合力将这只发疯的狗打死'
#message = '不顾'
print '***message***',len(message)
start_time = time.time()
for i in range(1000):
res = is_contain(message,root)
#print res
end_time = time.time()
print (end_time - start_time)
def is_contain2(message,word_list):
for item in word_list:
if message.find(item)!=-1:
return True
return False
def normal():
print '------------normal--------------'
path = '/tmp/word.txt'
fp = open(path,'r')
word_list = []
message = '四处乱咬乱吠,吓得家中11岁的女儿躲在屋里不敢出来,直到辖区派出所民警赶到后,才将孩子从屋中救出。最后在征得主人同意后,民警和村民合力将这只发疯的狗打死'
print '***message***',len(message)
for line in fp:
line = line[0:-1]
word_list.append(line)
fp.close()
print 'The count of word:',len(word_list)
start_time = time.time()
for i in range(1000):
res = is_contain2(message,word_list)
#print res
end_time = time.time()
print (end_time - start_time)
if __name__ == '__main__':
dfa()
normal()
测试结果:
1) 敏感词 100个
----------------dfa-----------
***message*** 224
0.325479984283
------------normal--------------
***message*** 224
The count of word: 100
0.107350111008
2) 敏感词 1000 个
----------------dfa-----------
***message*** 224
0.324251890182
------------normal--------------
***message*** 224
The count of word: 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 算法的时间复杂度基本上是与敏感词的个数无关的。
来源:https://blog.csdn.net/isoleo/article/details/72379829


猜你喜欢
- 1.MySQL官网下载压缩版文件,放至安装路径下载zip安装包MySQL :: Download MySQL Community Serve
- 目录十大经典的排序算法 一、交换排序1、冒泡排序(前后比较-交换)2、快速排序(选取一个基准值,小数在左大数在右)二、插入排序1、
- 这个操作现在看来真没啥难的,但是我找相关的资料真的找了好久。多数大佬都是直接pandas官网甩我脸上,然后举一个入门级的例子。https:/
- Logo是品牌图形区别的点睛之处,我们每天都要接触很多logo - 在高速公路上,在购买商品时,以及浏览各种网站。我们查看很多logo设计,
- build.js中的代码会去调用UglifyJS的接口函数以执行压缩任务。 1,去github下载最新的UglifyJS。两种方式下载,如果
- 一、上传表单的HTML代码 <form action="UpLoad.php" method="post
- 啥也不说了,还是看代码吧! [root@yyjk DATABASE]# cat DBI.py# -*- coding: utf-8 -*-
- 问题出现与解决Pandas进行数据处理之后,假如想将其转化为json,会出现一个bug,就是中文文字是以乱码存储的,也就是\uXXXXXX的
- 实现效果通过源图片,在当前工作目录的/img目录下生成1000张,分别从1*1到1000*1000像素的图片。效果如下:目录结构实现示例#
- 第一步.开启mysql慢查询方式一:修改配置文件Windows:Windows 的配置文件为 my.ini,一般在 MySQL 的安装目录下
- python中有一个略微奇怪的表达式叫yield expression,本文就来探究一下这是个什么东西。一步一步来。iterablemyli
- 环境:python3.5,pycharm2017.2.3目录结构a.pyt=5b.pyfrom a import tprint(t)平台显示
- 我就废话不多说了,大家还是直接看代码吧~print(np.shape(X))#(1920, 45, 20)X=sequence.pad_se
- 这篇文章主要介绍了Django多进程滚动日志问题解决方案,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的
- 最近在使用layui前端框架,在使用单选按钮、下拉菜单select、checkbox等控件的时候 往往遇到一些初始化的东西。有时候会发现,自
- echo是PHP语句, print和print_r是函数,语句没有返回值,函数可以有返回值(即便没有用) print只
- 总的来说:1、数据库设计和表创建时就要考虑性能2、sql的编写需要注意优化3、分区、分表、分库设计表的时候:1、字段避免null值出现,nu
- 实例如下:<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional
- smtplib模块负责发送邮件:是一个发送邮件的动作,连接邮箱服务器,登录邮箱,发送邮件(有发件人,收信人,邮件内容)。email模块负责构
- 起因之前写了一篇《 vue2.0+vue-video-player实现hls播放》,里边有提到在用vue-video-player之前,我尝