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
0
投稿
猜你喜欢
- 大家都用过企业管理器中的--“收缩数据库”,里面的功能的确可以收缩数据库的日志文件(.ldf)和数据文件(.mdf),但都会发现同样的问题,
- 本文实例讲述了PHP变量作用域(全局变量&局部变量)&global&static关键字用法。分享给大家供大家参考,具
- 本文实例讲述了python执行子进程实现进程间通信的方法。分享给大家供大家参考。具体实现方法如下:a.py:import subproces
- 我们可用一个函数来实现小数转分数,不过只能转换能够整除的分数:Public Function XtoF(str 
- 前言本篇来学习pytest中内置fixture中临时目录的使用tmpdirtmpdir作用范围是函数级别,创建临时文件供单个测试点调用# -
- 窗外下着小雨,作为单身程序员的我逛着逛着发现一篇好东西,来自知乎 你都用 Python 来做什么?的第一个高亮答案。到上面去看了看,地址都是
- 1.相关基础python3中有两种字符串类型:str和bytespython编码问题可以参考文章str以unicode编码格式保存在内存所以
- 由于一些读者对于960 Grid System CSS Framework的原理和使用方法比较感兴趣,暴风彬彬今天将和大家一同分享这篇关于9
- 1.nginx使用哪种网络协议? nginx是应用层 我觉得从下往上的话 传输层用的是tcp/ip 应用层用的是http fastcgi负责
- 想使用正则表达式来获取一段文本中的任意字符,写出如下匹配规则: (.*) 结果运行之后才发现,无法获得换行之后的文本。于是查了一下手册,才发
- 本文实例讲述了PHP实现的curl批量请求操作。分享给大家供大家参考,具体如下:<?php$ch = array();$res = a
- 多进程&多线程服务端:多进程和多线程的开启方式相同。缺点:<1> 由于Cpython的GIL,导致同一时间无法运行多个线
- 前言几乎每个程序都需要用到图片。下面就来给大家介绍前端+PHP后端实现微信小程序实现图片上传功能,分享出来供大家参考学习,下面话不多说了,来
- 1. 安装pip install PyExecJS # 需要注意, 包的名称:
- 本文介绍了Python日期的加减等操作的示例,分享给大家,也给自己留个笔记1. 日期输出格式化所有日期、时间的api都在datetime模块
- 简介Type Hint(或者叫做PEP-484)提供了一种针对Python程序的类型标注标准。为什么使用Type Hint?对于动态语言而言
- opendir – 打开一个目录句柄,可用于之后的 closedir(),readdir() 和 rewinddir()
- 说明:这个例子,首先是把SPAN里的内容用display:none;干掉,就是不显示; 然后在A:HOVER时,再把SPAN里的内容disp
- 最近朋友需要一个可以识别图片中的文字的程序,以前做过java验证码识别的程序;刚好最近在做一个python项目,所以顺便用Python练练手
- 换脸!这段时间,deepfakes搞得火热,比方说把《射雕英雄传》里的朱茵换成了杨幂,看下面的图!毫无违和感!其实早在之前,基于AI换脸的技