1. 什么是字典树？
字典树（Trie Tree），又称单词查找树或键树，是一种有序的树形数据结构，常用于搜索和排序。其基本性质是节点本身不存完整单词，从根节点到某一节点，路径上经过的字符连接起来即为该节点所代表的字符串。数据量大时，字典树可以节约查询时间，减少计算量。
字典树的结构可以看做是一个多叉树，其中每个节点记录着从根节点到该节点路径代表的字符串和以该节点为结尾的字符串列表。
在Python中我们可以使用嵌套字典的方式来实现字典树，其中每个字典表示一个节点，键值为该节点代表的字符，值为下一个字典节点。
class Trie:
def __init__(self):
self.root = {}
def insert(self, word):
node = self.root
for c in word:
if c not in node:
node[c] = {}
node = node[c]
node["end"] = True
def search(self, word):
node = self.root
for c in word:
if c not in node:
return False
node = node[c]
return "end" in node
def startsWith(self, prefix):
node = self.root
for c in prefix:
if c not in node:
return False
node = node[c]
return True
2. 字典树在文本匹配中的应用
2.1 前缀匹配
我们可以使用字典树来实现字符串的前缀匹配，即在一段文本中查找以某个字符串为前缀的所有单词。
在字典树中，如果某个节点的"end"键值为True，表示从根节点到该节点的路径代表了一个完整的单词。因此，我们可以在搜索的过程中记录该节点是否可以结束一段单词，并将其加入结果列表。
class Trie:
def __init__(self):
self.root = {}
def insert(self, word):
node = self.root
for c in word:
if c not in node:
node[c] = {}
node = node[c]
node["end"] = True
def search(self, word):
node = self.root
for c in word:
if c not in node:
return False
node = node[c]
return "end" in node
def startsWith(self, prefix):
node = self.root
for c in prefix:
if c not in node:
return []
node = node[c]
res = []
self.dfs(node, prefix, res)
return res
def dfs(self, node, path, res):
if "end" in node:
res.append(path)
for c, nxt in node.items():
if c != "end":
self.dfs(nxt, path + c, res)
我们可以使用startsWith方法来实现前缀匹配，该方法返回以传入字符串为前缀的所有单词。
2.2 关键词匹配
对于一段文本，我们可以使用字典树来查找其中是否包含多个关键词。具体做法是，将所有关键词插入到字典树中，然后遍历文本，对每一个字符，从根节点开始根据其在字典树中的路径进行遍历。如果能够到达一个代表单词结束的节点，说明文本中包含了该关键词。
在遍历的过程中，如果发现一个字符在字典树中的路径中没有对应节点，那么说明以该字符为前缀的单词不存在于所有关键词中，可以直接跳过。
class Trie:
def __init__(self):
self.root = {}
def insert(self, word):
node = self.root
for c in word:
if c not in node:
node[c] = {}
node = node[c]
node["end"] = True
def search(self, word):
node = self.root
for c in word:
if c not in node:
return False
node = node[c]
return "end" in node
def keywordsMatch(self, text):
res = set()
for i in range(len(text)):
node = self.root
if text[i] not in node:
continue
for j in range(i, len(text)):
if text[j] not in node:
break
node = node[text[j]]
if "end" in node:
res.add(text[i:j+1])
return res
我们可以使用keywordsMatch方法来实现文本中关键词的匹配，该方法返回所有匹配的关键词集合。
3. 总结
字典树是一种多叉树结构，常用于字符串的搜索和排序。在Python中，我们可以使用嵌套字典的方式来实现字典树。对于文本匹配问题，我们可以使用字典树来实现字符串的前缀匹配和关键词匹配。具体做法是，将所有关键词插入到字典树中，然后根据字典树中的路径遍历文本，并记录是否到达了代表单词结束的节点。在遍历的过程中，如果发现当前字符在字典树中的路径中没有对应节点，可以直接跳过。该算法可以有效地减少比较次数和计算量，使得文本匹配问题的效率得到了提高。