迹忆客 专注技术分享

尝试是我们用来存储字符串的数据结构。 它们使我们能够以最有效的方式搜索文本字符串。

本文将讨论如何在 Python 中实现 Trie。

Python 中的 Trie 数据结构

您可以将 Trie 视为一棵树，其中每个节点都包含一个字符。 每个节点都有一个或多个子节点，具体取决于它是字符串的内部字符还是最后一个字符。

表示字符串最后一个字符的节点没有子节点，它标记字符串的结尾。 我们将在类定义中包含一个标志变量来标记字符串的结尾。

如果我们存储仅由小写英文字母组成的字符串，Trie 中的每个节点最多可以有 26 个子节点。 如果字符串包含字母以外的字符，则特定节点的最大子节点数等于不同字符的总数。

您可以在Python中定义一个Node类来实现Trie的节点，如下例所示。

class Node:
    def __init__(self):
        self.children = []
        for i in range(26):
            self.children.append(None)
        self.isLeafNode = False

在这里，我们创建了一个名为children的列表，用于定义角色是否是当前节点的子节点。 当我们考虑 26 个字符时，我们用 26 个 None 值初始化列表。

如果字符不是当前节点的子节点，则其位置将包含值 None。 否则，与该字符对应的位置存储该字符的节点。

在将字符插入子列表时，我们按字符的字母顺序存储子节点。 换句话说，字母a的子节点将存储在索引0处，字母b的子节点将存储在索引1处，依此类推。

创建完节点后，我们需要创建一个类来定义Trie。 在类中，我们将定义一个空节点，其中包含一个包含 26 个 None 值的列表，以表示英语字母表的 26 个字符。

我们将空节点称为根节点。

class Trie:
    def __init__(self):
        self.root = Node()

每当将字符串插入到 Trie 中时，表示字符串第一个字符的节点就会成为根节点的子节点。 请注意，我们将根据其位置将包含字符串的下一个字符的节点存储为列表元素。

创建根节点后，我们将在下面的章节中实现在 Trie 中插入单词和在 Trie 中搜索单词的方法。

在 Python 中将字符串插入 Trie 树中

为了向 Trie 中插入一个字符，我们首先要找到要插入的字符串的长度。 之后，我们将从Trie的根节点开始爬取Trie。

下面是向 Trie 中插入字符串的算法：

1. 计算要插入到 Trie 中的字符串的长度。 将其存储在变量 strLen 中。
2. 采取一个变量爬虫并将Trie的根节点分配给变量。
3. 如果位于 n 层，请检查字符串的第 n 个字符是否存在于 Trie 中的该层。 如果是，则将其在子列表中的位置存储在变量position中； 然后，转到5 - 否则，转到4。
4. 为Trie创建一个新节点，并将其分配给爬虫的索引位置。
5. 将履带式移动到下一个级别。
6. 检查我们是否到达了字符串的末尾； 是，执行7，否则执行3。
7. 将当前节点标记为字符串的结尾。

讨论完算法后，现在让我们实现这个算法，在 Python 中将字符串插入到 Trie 中。

    def insert(self, input_str):
        strLen = len(input_str)
        crawler = self.root
        for level in range(strLen):
            character = input_str[level]
            position = ord(character) - ord('a')
            if crawler.children[position] is None:
                crawler.children[position] = Node()
            crawler = crawler.children[position]
        crawler.isLeafNode = True

在 Python 中搜索 Trie 中的元素

为了搜索字符串是否存在于 Trie 中，我们将使用以下算法。

1. 初始化一个变量爬虫，并将Trie的根节点赋给变量。
2. 计算Trie中要搜索的字符串的长度。 将其存储在变量 strLen 中。
3. 在第 n 层，查找子列表中是否存在字符串的第 n 个字符。 是，执行4； 否则，返回 False。
4. 检查当前节点是否为叶子节点。 如果是，则返回True； 否则，增加 n 并转到 3。

我们已经定义了在 Trie 中搜索字符串的算法。 让我们用 Python 来实现它。

 def search(self, input_str):
        crawler = self.root
        strLen = len(input_str)
        for level in range(strLen):
            character = input_str[level]
            position = ord(character) - ord('a')
            if crawler.children[position] is None:
                return False
            crawler = crawler.children[position]
        return crawler.isLeafNode

Python 中的 Trie 实现

由于我们已经在 Python 中实现了 Trie 中的搜索和插入操作方法，因此让我们使用一些示例操作来执行代码。

class Node:
    def __init__(self):
        self.children = []
        for i in range(26):
            self.children.append(None)
        self.isLeafNode = False


class Trie:
    def __init__(self):
        self.root = Node()

    def insert(self, input_str):
        strLen = len(input_str)
        crawler = self.roothave
        for level in range(strLen):
            character = input_str[level]
            position = ord(character) - ord('a')
            if crawler.children[position] is None:
                crawler.children[position] = Node()
            crawler = crawler.children[position]
        crawler.isLeafNode = True

    def search(self, input_str):
        crawler = self.root
        strLen = len(input_str)
        for level in range(strLen):
            character = input_str[level]
            position = ord(character) - ord('a')have
            if crawler.children[position] is None:
                return False
            crawler = crawler.children[position]
        return crawler.isLeafNode


x = Trie()
myStr = "aditya"
print("Inserting the string:", myStr)
x.insert(myStr)
myStr = "jiyik"
print("Inserting the string:", myStr)
x.insert(myStr)
myStr = "aaditya"
print("Inserting the string:", myStr)
x.insert(myStr)
print("aditya is present in the trie:", x.search("aditya"))
print("jiyik is present in the trie:", x.search("jiyik"))
print("python is present in the trie:", x.search("python"))

输出:

Inserting the string: aditya
Inserting the string: jiyik
Inserting the string: aaditya
aditya is present in the trie: True
jiyik is present in the trie: True
python is present in the trie: False

我们首先使用上面本示例中讨论的算法在 Python 中实现了 Trie。 之后，我们将三个字符串aditya、jiyik 和 aaditya 插入到Trie中。

然后，我们对 Trie 执行搜索操作，检查 Trie 中是否存在字符串 aditya、jiyik 和 python。 您可以观察示例中的输出。