12.5.1 什么是字典树？
字典树又称单词查找树，Trie树，是一种树形结构。字典树的三个基本性质：
(1) 根节点不包含字符，除根节点外每一个节点都只包含一个字符；
(2) 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
(3) 每个节点的所有子节点包含的字符都不相同
下图所示的结构就是字典树:
上图中的root表示根节点，红色的节点表示从根节点到该节点路径的所有字符构成一个完整的单词。比如图中的王八就是一个单词，王子文就是一个单词。王八和王子文有一个共同的前缀:王。这也是为什么使用字典树可以查找共同前缀。
12.5.2 字典树实现及使用场景
我们现在利用Python中的字典来构造这棵字典树:
"""
@author: 薯条老师
@desc: 实现字典树结构
"""
names = ["王八", "王子文", "李唐"]
trie = {"root": {}}
for name in names:
prev = trie_next = trie["root"]
for ch in name:
if ch not in trie_next:
trie_next[ch] = {}
prev = trie_next
trie_next = trie_next[ch]
else:
# 键为None时即为红色节点
prev[ch] = {None: 0}
print(trie)字典树常用于字符串检索，以及查找字符串的公共前缀等。我们现在根据字典树结构，来写一个识别文本中的敏感词算法。Python代码如下：
"""
@author: 薯条老师
@desc: 根据字典树来识别文本中的敏感词
"""
# 定义敏感词列表，后续根据该列表来构造字典树
sensitive_words = ["他妈的", "你妹"]
trie = {"root": {}}
for sensitive_word in sensitive_words:
prev = trie_next = trie["root"]
for ch in sensitive_word:
if ch not in trie_next:
trie_next[ch] = {}
prev = trie_next
trie_next = trie_next[ch]
else:
prev[ch] = {None: 0}
# text系用户在某论坛发表的一些评论
text = "我跟他妈在街上偶遇，没想到被你妹妹看到了"
length_of_text = len(text)
for index in range(length_of_text):
pos = index
sensitive_word = ""
trie_next = trie["root"]
while text[pos] in trie_next and pos < length_of_text:
sensitive_word += text[pos]
trie_next = trie_next[text[pos]]
if None in trie_next:
print(f"发现了敏感词汇{sensitive_word}")
break
pos += 112.5.3 最具实力的小班培训
薯条老师在广州有开设线下培训班，小班授课模式，一班最多6个人。也可一对一授课，全程帮助你学好计算机，实现高薪就业。不在广州的同学可提供住宿，也可以报名线上小班，用腾讯会议上直播课。
(1) Python后端工程师高薪就业班，月薪11K-18K，免费领取课程大纲
(2) Python高级爬虫+安卓逆向工程师就业班，月薪15K-25K，包拿Offer
(3) Python数据分析+商业分析+数据科学就业班，企业级项目实战，月薪10K-20K
(4) Python量化交易就业班，A股+期货+数字货币量化，月薪10K-40K
(5) Python机器学习+深度学习算法工程师，月薪20-50K
跟薯条老师学习的学生有拿到花生日记，林氏家居，南方电网，中国邮政集团，京东, 阿里等公司的offer, 学生的最低薪资有6K，最高薪资有18K， 平均就业薪资有11000。
扫码咨询薯条老师：
