Trie 数据结构在信息检索方面非常有效。它主要用于字典和电话簿的实现。它对于实现您在键盘上打字时看到的自动文本建议也很有用。在本教程中，我们将了解如何使用专门为前缀搜索操作定制的 Python 来实现我们自己的 trie 数据结构。
在这里，您将学到以下内容：
- 如何在 Python 中实现您自己的 Trie 数据结构以进行高效的前缀搜索。
- 如何在 Trie 数据结构中进行插入。
- 如何在 Trie 数据结构中查询单词。
实现 TrieNode 类
创建 Trie 数据结构类
- 一个人物
- 儿童名单
- 一个布尔值，指示单词是否在该节点结束。
让我们为 TrieNode 类编写代码：
class TrieNode: def __init__(self, char): self.char = char self.is_end = False self.children = {} |
在初始化 TrieNode 时，我们需要提供一个字符。
.is_end标记单词是否在当前节点结束。默认设置为 false。
创建 Trie 数据结构类
现在我们有了 TrieNode 类，我们将使用 Python 围绕它构建 trie 数据结构。为了初始化一个 trie，我们需要初始化一个 trie 节点并提供在 trie 中插入和搜索的方法。
class Trie(object): def __init__(self): self.root = TrieNode("") |
这部分负责初始化一个空的 TrieNode。
将元素插入 Trie 结构
让我们看看 Trie 数据结构中插入是如何发生的。
为了将单词插入到 trie 中，我们将逐个字符地遍历单词，并根据需要添加节点。
同时，我们需要从根部向下移动 Trie，看看子列表中是否有该字符。如果该角色不存在，那么我们需要使用该角色创建一个新的 TrieNode 并将其添加到子级列表中。
当我们到达单词的末尾时，我们需要将与单词的最后一个字符对应的节点的is_end设置为 true。
这是上面讨论的方法的实现。
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 树：
- 这里
- 听到
- 她
- 他
- 你好
- 如何
对应于这些单词的字典树将如下所示：
这里绿色节点对应于该节点的is_end 为 true 。
在 Python 中搜索 Trie 中的单词
现在让我们看看如何在基于 Python 的 trie 数据结构中执行搜索操作。我们不想执行完全匹配的搜索。相反，我们想要的是获取以我们正在搜索的字符串开头的单词列表。
在实现 trie 时，搜索函数将前缀树作为输入，并有效地返回以该公共前缀开头的所有单词。
例如，如果我们搜索“He”，我们应该得到以下单词。
- 他
- 这里
- 听到
- 她
- 你好
这些都是以“他”开头的词。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) |
当使用我们的 trie 实现进行搜索时，我们传递一个节点和搜索到的前缀作为参数。每当搜索到达is_end为 true 的节点时，它就会将该单词附加到输出列表中。
否则，它会继续以 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 函数从最后一个字符向下移动，并将所有完整的单词添加到我们的输出列表中。
Trie数据结构的Python实现
本教程的完整代码如下：
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 实现
让我们尝试向 trie 添加一些单词并进行搜索查询。
tr = Trie()tr.insert("here")tr.insert("hear")tr.insert("he")tr.insert("hello")tr.insert("how ")tr.insert("her") |
利用我们的 Python trie 实现，我们将向 trie 数据结构插入单词。这将进行尝试并将这五个单词添加到其中。
现在我们可以使用以下行进行查询：
tr.search("he") |
输出 ：
['he', 'her', 'here', 'hear', 'hello'] |
让我们再做一个查询：
tr.search("her") |
输出 ：
['her', 'here'] |
结论
我们成功地用 Python 实现了 Trie 数据结构，允许高效的基于前缀的搜索操作。在本教程中，我们探索了 Python 中高效的 Trie 数据结构。我们构建了一个支持插入和单词查询操作的 Trie 类。如何将此实现用于特定应用程序，例如自动完成功能？
参考