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 类。如何将此实现用于特定应用程序,例如自动完成功能?
参考