6.7 KiB
用 Python 实现 Trie 数据结构
原文：https://www.askpython.com/python/examples/trie-data-structure
数据结构在信息检索方面非常有效。它主要用于实现字典和电话簿。
它对于实现在键盘上键入时看到的自动文本建议也很有用。
在本教程中，我们将了解如何用 Python 实现我们自己的 trie 数据结构。
在本教程中，您将学习以下内容:
- 如何实现你自己的 Trie 数据结构。
- 如何在 Trie 数据结构中插入数据？
- 如何在 Trie 数据结构中查询单词？
实现 TrieNode 类
让我们从编写 TrieNode 类的代码开始。每个 trie 节点需要具有以下字段:
- 一个角色
- 儿童名单
- 一个布尔值，它表明一个单词是否在该节点结束。
让我们为 TrieNode 类编写代码:
class TrieNode:
def __init__(self, char):
self.char = char
self.is_end = False
self.children = {}
初始化 TrieNode 时，我们需要提供一个字符。
。is_end 标记一个字是否在当前节点结束。默认情况下，它被设置为 false。
编写 Trie 数据结构类
让我们继续为我们的 Trie 类编写代码。
要初始化一个 trie，我们需要初始化一个 trie 节点，并提供在 trie 中插入和搜索的方法。
class Trie(object):
def __init__(self):
self.root = TrieNode("")
这部分负责初始化一个空的 TrieNode。
如何在我们的 Trie 中执行插入操作？
让我们看看插入是如何在 Trie 数据结构中发生的。
为了进行插入，我们需要逐个字符地遍历要插入的单词。
同时，我们需要从根开始向下移动 Trie，看看孩子的列表是否有那个字符。如果该字符不存在，那么我们需要用该字符创建一个新的 TrieNode，并将其添加到孩子列表中。
当我们到达单词的末尾时，我们需要为对应于单词最后一个字符的节点设置 is_end 为真。
下面是上面讨论的方法的实现。
def insert(self, word):
node = self.root
#traverse the word character by character
for char in word:
#check if the character is there in the list of children
if char in node.children:
node = node.children[char]
else:
# else make a new TrieNode corresponding to that character
new_node = TrieNode(char)
# add the new node to the list of children
node.children[char] = new_node
node = new_node
#after traversig the word set .is_end to true for the last #char
node.is_end = True
这将照顾我们所有的插入。
考虑一个包含以下单词的 Trie:
- 这里
- 听
- 她
- 男性
- 你好
- 怎么
对应于这些单词的 trie 将如下所示:
Trie
这里的绿色节点对应于该节点的为真。
如何在我们的 Trie 中搜索？
现在让我们看看如何在我们的特里搜索单词。我们不想为搜索执行精确匹配。相反，我们想要的是获得以我们要搜索的字符串开始的单词列表。
在搜索时，我们将只提供前缀，搜索功能应该能够返回以该前缀开始的所有单词。
例如，如果我们搜索**“他”**，我们应该得到以下单词。
- 男性
- 这里
- 听
- 她
- 你好
这些都是以“他”开头的词。trie 的这一方面使得它对于在键盘中实现自动完成非常有用。
在搜索单词时，我们以 DFS 的方式进行搜索。因此，我们需要编写一个函数，用于在我们的 trie 中执行 DFS 搜索。
def dfs(self, node, pre):
if node.is_end:
self.output.append((pre + node.char))
for child in node.children.values():
self.dfs(child, pre + node.char)
在调用函数时，我们需要传递一个节点和到目前为止搜索到的前缀。每当搜索到达一个节点，并且 为真时，它会将该单词附加到输出列表中。
否则，它继续以 DFS 方式在子节点中搜索。
搜索功能如下:
def search(self, x):
node = self.root
# traverse the search query and move down the trie
for char in x:
if char in node.children:
node = node.children[char]
else:
#if query doesn't match the nodes in trie
return []
self.output = []
#call DFS
self.dfs(node, x[:-1])
return self.output
在搜索时，我们遍历搜索查询并同时向下移动 trie。
然后，我们在与查询的最后一个字符对应的节点上调用 DFS。
然后，DFS 函数从最后一个字符开始向下移动，将所有完整的单词添加到输出列表中。
完全码
本教程的完整代码如下所示:
class TrieNode:
def __init__(self, char):
self.char = char
self.is_end = False
self.children = {}
class Trie(object):
def __init__(self):
self.root = TrieNode("")
def insert(self, word):
node = self.root
for char in word:
if char in node.children:
node = node.children[char]
else:
new_node = TrieNode(char)
node.children[char] = new_node
node = new_node
node.is_end = True
def dfs(self, node, pre):
if node.is_end:
self.output.append((pre + node.char))
for child in node.children.values():
self.dfs(child, pre + node.char)
def search(self, x):
node = self.root
for char in x:
if char in node.children:
node = node.children[char]
else:
return []
self.output = []
self.dfs(node, x[:-1])
return self.output
行动中的尝试
让我们试着向一个 trie 中添加一些单词，并进行搜索查询。
tr = Trie()
tr.insert("here")
tr.insert("hear")
tr.insert("he")
tr.insert("hello")
tr.insert("how ")
tr.insert("her")
这将创建一个 trie，并将这五个单词添加到其中。
现在我们可以使用下面一行进行查询:
tr.search("he")
输出:
['he', 'her', 'here', 'hear', 'hello']
让我们做另一个查询:
tr.search("her")
输出:
['her', 'here']
结论
本教程讲述了 Python 中 Trie 数据结构的实现。我们学习了如何创建一个 trie 类，如何执行插入，以及如何在 Trie 中查询单词。