# DFA算法之内容敏感词过滤

DFA 算法是通过提前构造出一个 树状查找结构，之后根据输入在该树状结构中就可以进行非常高效的查找。

[En]

Let’s say we have a sensitive thesaurus, and the words in Ciku are:

[En]

Then you can construct a tree structure like this:

[En]

Set the string entered by the player as: Baiju I love you, ha.

str[0] = ‘白’ 时，此时 tree[i] 没有指向值为 ‘白’ 的节点，所以不满足匹配条件，继续往下遍历
str[1] = ‘菊’，同样不满足匹配条件，继续遍历
str[2] = ‘我’，此时 tree[i] 有一条路径连接着 ‘我’ 这个节点，满足匹配条件，i 指向 ‘我’ 这个节点，然后继续遍历
str[3] = ‘爱’，此时 tree[i] 有一条路径连着 ‘爱’ 这个节点，满足匹配条件，i 指向 ‘爱’，继续遍历
str[4] = ‘你’，同样有路径，i 指向 ‘你’，继续遍历
str[5] = ‘呀’，同样有路径，i 指向 ‘呀’

[En]

At this time, the string entered by our player has not yet been traversed, so continue to traverse:

str[6] = ‘哈’，不满足匹配条件，继续遍历
str[7] = ‘哈’ …

str[8] = ‘哈’ …

[En]

We can see that we iterated through the string entered by the player and found the sensitive words in it.

[En]

Set the string entered by the player as: Baiju I love you, ha.

str[0] = ‘白’ 时，此时 tree[i] 没有指向值为 ‘白’ 的节点，所以不满足匹配条件，继续往下遍历
str[1] = ‘菊’，同样不满足匹配条件，继续遍历
str[2] = ‘我’，此时 tree[i] 有一条路径连接着 ‘我’ 这个节点，满足匹配条件，i 指向 ‘我’ 这个节点，然后继续遍历
str[3] = ‘爱’，此时 tree[i] 有一条路径连着 ‘爱’ 这个节点，满足匹配条件，i 指向 ‘爱’，继续遍历
str[4] = ‘你’，同样有路径，i 指向 ‘你’，继续遍历
str[5] = ‘呀’，同样有路径，i 指向 ‘呀’

[En]

At this time, the string entered by our player has not yet been traversed, so continue to traverse:

str[6] = ‘哈’，不满足匹配条件，继续遍历
str[7] = ‘哈’ …

str[8] = ‘哈’ …

[En]

We can see that we iterated through the string entered by the player and found the sensitive words in it.

DFA算法python实现：

1 class DFA:
2     """DFA 算法
3        敏感字中"*"代表任意一个字符
4     """
5
6     def __init__(self, sensitive_words: list, skip_words: list):  # 对于敏感词sensitive_words及无意义的词skip_words可以通过数据库、文件或者其他存储介质进行保存
7         self.state_event_dict = self._generate_state_event(sensitive_words)
8         self.skip_words = skip_words
9
10     def __repr__(self):
11         return '{}'.format(self.state_event_dict)
12
13     @staticmethod
14     def _generate_state_event(sensitive_words) -> dict:
15         state_event_dict = {}
16         for word in sensitive_words:
17             tmp_dict = state_event_dict
18             length = len(word)
19             for index, char in enumerate(word):
20                 if char not in tmp_dict:
21                     next_dict = {'is_end': False}
22                     tmp_dict[char] = next_dict
23                     tmp_dict = next_dict
24                 else:
25                     next_dict = tmp_dict[char]
26                     tmp_dict = next_dict
27                 if index == length - 1:
28                     tmp_dict['is_end'] = True
29         return state_event_dict
30
31     def match(self, content: str):
32         match_list = []
33         state_list = []
34         temp_match_list = []
35
36         for char_pos, char in enumerate(content):
37             if char in self.skip_words:
38                 continue
39             if char in self.state_event_dict:
40                 state_list.append(self.state_event_dict)
41                 temp_match_list.append({
42                     "start": char_pos,
43                     "match": ""
44                 })
45             for index, state in enumerate(state_list):
46                 is_match = False
47                 state_char = None
48                 if '*' in state: # 对于一些敏感词，比如大傻X，可能是大傻B，大傻×，大傻...，采用通配符*，一个*代表一个字符
49                     state_list[index] = state['*']
50                     state_char = state['*']
51                     is_match = True
52                 if char in state:
53                     state_list[index] = state[char]
54                     state_char = state[char]
55                     is_match = True
56                 if is_match:
57                     if state_char["is_end"]:
58                         stop = char_pos + 1
59                         temp_match_list[index]['match'] = content[
60                                                           temp_match_list[index]['start']:stop]
61                         match_list.append(copy.deepcopy(temp_match_list[index]))
62                         if len(state_char.keys()) == 1:
63                             state_list.pop(index)
64                             temp_match_list.pop(index)
65                 else:
66                     state_list.pop(index)
67                     temp_match_list.pop(index)
68         for index, match_words in enumerate(match_list):
69             print(match_words['start'])
70         return match_list

_generate_state_event方法生成敏感词的树状结构，（以字典保存），对于上面的例子，生成的树状结构保存如下：

if __name__ == '__main__':
dfa = DFA(['我爱你', '我爱他', '我爱她', '我爱你呀', '我爱他呀', '我爱她呀', '我爱她啊'], skip_words=[])  # 暂时不配置skip_words
print(dfa)结果：{'我': {'is_end': False, '爱': {'is_end': False, '你': {'is_end': True, '呀': {'is_end': True}}, '他': {'is_end': True, '呀': {'is_end': True}}, '她': {'is_end': True, '呀': {'is_end': True}, '啊': {'is_end': True}}}}}


if __name__ == '__main__':
dfa = DFA(['我爱你', '我爱他', '我爱她', '我爱你呀', '我爱他呀', '我爱她呀', '我爱她啊'], ['\n', '\r\n', '\r'])
# print(dfa)
print(dfa.match('白菊我爱你呀哈哈哈'))结果：[{'start': 2, 'match': '我爱你'}, {'start': 2, 'match': '我爱你呀'}]


DFA 算法是通过提前构造出一个 树状查找结构，之后根据输入在该树状结构中就可以进行非常高效的查找。

[En]

Let’s say we have a sensitive thesaurus, and the words in Ciku are:

[En]

Then you can construct a tree structure like this:

[En]

Set the string entered by the player as: Baiju I love you, ha.

str[0] = ‘白’ 时，此时 tree[i] 没有指向值为 ‘白’ 的节点，所以不满足匹配条件，继续往下遍历
str[1] = ‘菊’，同样不满足匹配条件，继续遍历
str[2] = ‘我’，此时 tree[i] 有一条路径连接着 ‘我’ 这个节点，满足匹配条件，i 指向 ‘我’ 这个节点，然后继续遍历
str[3] = ‘爱’，此时 tree[i] 有一条路径连着 ‘爱’ 这个节点，满足匹配条件，i 指向 ‘爱’，继续遍历
str[4] = ‘你’，同样有路径，i 指向 ‘你’，继续遍历
str[5] = ‘呀’，同样有路径，i 指向 ‘呀’

[En]

At this time, the string entered by our player has not yet been traversed, so continue to traverse:

str[6] = ‘哈’，不满足匹配条件，继续遍历
str[7] = ‘哈’ …

str[8] = ‘哈’ …

[En]

We can see that we iterated through the string entered by the player and found the sensitive words in it.

[En]

Set the string entered by the player as: Baiju I love you, ha.

str[0] = ‘白’ 时，此时 tree[i] 没有指向值为 ‘白’ 的节点，所以不满足匹配条件，继续往下遍历
str[1] = ‘菊’，同样不满足匹配条件，继续遍历
str[2] = ‘我’，此时 tree[i] 有一条路径连接着 ‘我’ 这个节点，满足匹配条件，i 指向 ‘我’ 这个节点，然后继续遍历
str[3] = ‘爱’，此时 tree[i] 有一条路径连着 ‘爱’ 这个节点，满足匹配条件，i 指向 ‘爱’，继续遍历
str[4] = ‘你’，同样有路径，i 指向 ‘你’，继续遍历
str[5] = ‘呀’，同样有路径，i 指向 ‘呀’

[En]

At this time, the string entered by our player has not yet been traversed, so continue to traverse:

str[6] = ‘哈’，不满足匹配条件，继续遍历
str[7] = ‘哈’ …

str[8] = ‘哈’ …

[En]

We can see that we iterated through the string entered by the player and found the sensitive words in it.

DFA算法python实现：

1 class DFA:
2     """DFA 算法
3        敏感字中"*"代表任意一个字符
4     """
5
6     def __init__(self, sensitive_words: list, skip_words: list):
7         self.state_event_dict = self._generate_state_event(sensitive_words)
8         self.skip_words = skip_words
9
10     def __repr__(self):
11         return '{}'.format(self.state_event_dict)
12
13     @staticmethod
14     def _generate_state_event(sensitive_words) -> dict:
15         state_event_dict = {}
16         for word in sensitive_words:
17             tmp_dict = state_event_dict
18             length = len(word)
19             for index, char in enumerate(word):
20                 if char not in tmp_dict:
21                     next_dict = {'is_end': False}
22                     tmp_dict[char] = next_dict
23                     tmp_dict = next_dict
24                 else:
25                     next_dict = tmp_dict[char]
26                     tmp_dict = next_dict
27                 if index == length - 1:
28                     tmp_dict['is_end'] = True
29         return state_event_dict
30
31     def match(self, content: str):
32         match_list = []
33         state_list = []
34         temp_match_list = []
35
36         for char_pos, char in enumerate(content):
37             if char in self.skip_words:
38                 continue
39             if char in self.state_event_dict:
40                 state_list.append(self.state_event_dict)
41                 temp_match_list.append({
42                     "start": char_pos,
43                     "match": ""
44                 })
45             for index, state in enumerate(state_list):
46                 is_match = False
47                 state_char = None
48                 if '*' in state:
49                     state_list[index] = state['*']
50                     state_char = state['*']
51                     is_match = True
52                 if char in state:
53                     state_list[index] = state[char]
54                     state_char = state[char]
55                     is_match = True
56                 if is_match:
57                     if state_char["is_end"]:
58                         stop = char_pos + 1
59                         temp_match_list[index]['match'] = content[
60                                                           temp_match_list[index]['start']:stop]
61                         match_list.append(copy.deepcopy(temp_match_list[index]))
62                         if len(state_char.keys()) == 1:
63                             state_list.pop(index)
64                             temp_match_list.pop(index)
65                 else:
66                     state_list.pop(index)
67                     temp_match_list.pop(index)
68         return match_list


View Code

_generate_state_event方法生成敏感词的树状结构，（以字典保存），对于上面的例子，生成的树状结构保存如下：

if __name__ == '__main__':
dfa = DFA(['我爱你', '我爱他', '我爱她', '我爱你呀', '我爱他呀', '我爱她呀', '我爱她啊'], skip_words=[])  # 暂时不配置skip_words
print(dfa)结果：{'我': {'is_end': False, '爱': {'is_end': False, '你': {'is_end': True, '呀': {'is_end': True}}, '他': {'is_end': True, '呀': {'is_end': True}}, '她': {'is_end': True, '呀': {'is_end': True}, '啊': {'is_end': True}}}}}


if __name__ == '__main__':
dfa = DFA(['我爱你', '我爱他', '我爱她', '我爱你呀', '我爱他呀', '我爱她呀', '我爱她啊'], ['\n', '\r\n', '\r'])
# print(dfa)
print(dfa.match('白菊我爱你呀哈哈哈'))结果：[{'start': 2, 'match': '我爱你'}, {'start': 2, 'match': '我爱你呀'}]


48                 if '*' in state: # 对于一些敏感词，比如大傻X，可能是大傻B，大傻×，大傻...，采用通配符*，一个*代表一个字符
49                     state_list[index] = state['*']
50                     state_char = state['*']
51                     is_match = True


if __name__ == '__main__':
dfa = DFA(['大傻*'], [])
print(dfa)
print(dfa.match('大傻X安乐飞大傻B'))结果：{'大': {'is_end': False, '傻': {'is_end': False, '*': {'is_end': True}}}}[{'start': 0, 'match': '大傻X'}, {'start': 6, 'match': '大傻B'}]


if __name__ == '__main__':
dfa = DFA(['大傻*'], [])
print(dfa)
print(dfa.match('大%傻X安乐飞大&傻B'))结果：{'大': {'is_end': False, '傻': {'is_end': False, '*': {'is_end': True}}}}[


[En]

Configure unintentional words, and then check sensitive words, as follows, it can be seen that the damaged sensitive words can also be identified.

if __name__ == '__main__':
dfa = DFA(['大傻*'], ['%', '&'])
print(dfa)
print(dfa.match('大%傻X安乐飞大&傻B'))结果：{'大': {'is_end': False, '傻': {'is_end': False, '*': {'is_end': True}}}}[{'start': 0, 'match': '大%傻X'}, {'start': 7, 'match': '大&傻B'}]


Original: https://www.cnblogs.com/fdzwdt/p/16174752.html
Author: fdzwdt
Title: DFA算法之内容敏感词过滤

(0)

### 大家都在看

• #### RabbitMQ 入门系列：10、扩展内容：延时队列：延时队列插件及其有限的适用场景（系列大结局）。

延迟队列用于事件发生后间隔一段时间后需要做特定处理的场景，如： 1、电商支付系统中，用户下单后N分钟不支付，自动取消订单。 2、用户浏览商品长时间后还没下单，后续推送相关产品和优惠…

Python 2023年10月23日
085
• #### scrapy框架入门和使用实践

文章目录 scrapy框架入门和使用实践 * 一、前言 二、正文 1.架构简介 2.使用实践 – 1）创建项目 2）配置文件 3）请求及解析 4）数据存储 5）隐藏身份…

Python 2023年10月4日
078
• #### 技术分享 | 语音AI如何驱动虚拟人

关于虚拟数字人的起源最早可以追溯到上个世纪八十年代的 日本经典动画片《超时空要塞》的女主角林明美。作为虚拟偶像的开端，动画公司以她的虚拟形象发行唱片，虚拟人第一次进入了现实世界。 …

Python 2023年10月26日
0121
• #### pygame使用

初始化：pygame.init() 设置窗口：screen = pygame.display.set_mode((400,400)) 设置标题：pygame.display.set…

Python 2023年9月19日
063
• #### 接口自动化pytest+allure+yaml

该框架使用的是pytest+allure+yaml 暂未对数据库进行数据删除，待优化源码下载地址：https://github.com/jwb-1221/pytest.git文件具…

Python 2023年9月12日
0119

Python 2023年8月13日
072
• #### 【python】待君有余暇,看春赏樱花，这不得来一场浪漫的樱花旅~

Original: https://www.cnblogs.com/Qqun261823976/p/16826143.htmlAuthor: python倩Title: 【pyth…

Python 2023年10月31日
080

Python 2023年8月13日
084
• #### Windows 10 – Python 的虚拟环境 Virtualenv – 全局 python 环境切换问题

目录 1. 虚拟环境 2. 解决全局 python 环境切换的 bug * virtualenv 虚拟环境与本地 python 环境的测试 3. virtualenv 虚拟环境 个…

Python 2023年8月4日
099
• #### 备战数学建模26 & 科研必备-Python数据可视化之matplotlib

一、绘制折线图 二、绘制散点图 三、绘制条形图 一、绘制折线图 matplotlib:最流行的python底层绘图库，主要做数据可视化图表，名字取材于MATLAB，模仿MATLAB…

Python 2023年9月2日
0123
• #### 使用conda配置tensorflow环境

目录 * – 前置条件： – 操作步骤： – + 1.创建虚拟环境 + 2.激活虚拟环境 + 3.安装tensorflow + 4.配置pych…

Python 2023年9月8日
0108
• #### 超详细Anaconda安装教程

文章目录 * – 附Anaconda彻底卸载教程 – 一、Anaconda下载（官网和清华源） – + 1.1、Anaconda官网首页地址 +…

Python 2023年7月31日
0100
• #### 盘点10个冷门Python库，原来Python还能实现这些功能？

目录 👉 1 PrettyErrors 👉 2 Rich 👉 3 Dear PyGui 👉 4 HummingBird 👉 5 HiPlot 👉 6 Norfair 👉 7 Geo…

Python 2023年10月8日
0129
• #### python网络爬虫的第三方库_以下选项中,Python网络爬虫方向的第三方库是A.()scrapy()B.()numpy()C.()openpyxl()D.()PyQt5…

[填空题] 水泥浆体由初凝到终凝的过程称为水泥的()。 [单选] 肝脏是人体最大的实质性器官，其重量约() [填空题] 由箭线、节点和线路组成的，用来表示工作流程的有序、有向的网络…

Python 2023年10月3日
080
• #### django配置日志

在项目目录创建logs文件夹 CONSOLE_LOG = os.path.join(BASE_DIR, ‘logs’) LOGGING = { ‘version’: 1, ‘dis…

Python 2023年8月5日
070
• #### 【项目设计】自主HTTP服务器

文章目录 项目介绍 网络协议栈介绍 * 协议分层 数据的封装与分用 HTTP相关知识介绍 * HTTP的特点 URL格式 URI、URL、URN HTTP的协议格式 HTTP的请求…

Python 2023年10月10日
094