博客

Python数据结构与算法之字典树实现方法示例

  • Post category:Python

Python数据结构与算法之字典树实现方法示例

什么是字典树？

字典树，又叫Trie树、单词查找树或键树。

是一种树形结构，是一种哈希树的变种。典型应用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

字典树的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。

字典树的构造

  1. 首先构造一个空的字典树，根节点为空。
  2. 从数据集中取出一个字符串s，从第一个字符开始遍历每一个字符，并将它们插入到字典树中。
  3. 对于每个字符，看它是否在当前的节点的子节点中出现了，如果出现了，就继续遍历，如果没有出现，则需要新建一个节点并将其插入到对应的位置。
  4. 当遍历完整个字符串s后，将字符串的结尾标记为一个单词，并将单词的相关属性，如出现次数，存储在叶子节点上。

字典树的搜索

字典树的搜索主要就是从根节点开始，按照要搜索的字符串的每一个字符遍历下去，在字典树中找到与之对应的节点，最后检查该节点是否为单词的结尾。

代码示例

下面是一个简单的Python示例代码，用于构造字典树和搜索：

class Trie:

    def __init__(self):
        self.root = {}
        self.end_of_word = "#"

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            node = node.setdefault(char, {})
        node[self.end_of_word] = True

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node:
                return False
            node = node[char]
        return self.end_of_word in node

该代码定义了一个Trie类，其中包含了insert()和search()两个方法，分别用于插入字符串和搜索字符串。

下面是一个示例说明如何使用该类：

trie = Trie()
words = ["apple", "banana", "cherry", "grape"]
for word in words:
    trie.insert(word)

assert trie.search("apple") == True
assert trie.search("banana") == True
assert trie.search("cherry") == True
assert trie.search("grape") == True
assert trie.search("watermelon") == False

在示例中，首先新建一个Trie对象，并将字符串“apple”，“banana”，“cherry”和“grape”插入到字典树中。然后利用assert语句进行判断，各种搜索字符串是否存在于字典树中，其中“watermelon”不存在于字典树中。

另外，还可以在Trie类中增加count()方法，用于统计字典树中单词出现的次数，代码如下：

def count(self, word: str) -> int:
        node = self.root
        for char in word:
            if char not in node:
                return 0
            node = node[char]
        return self._count(node)

    def _count(self, node) -> int:
        cnt = 0
        if self.end_of_word in node:
            cnt += 1
        for key in node:
            if key != self.end_of_word:
                cnt += self._count(node[key])
        return cnt

这个方法利用递归的方式遍历整棵字典树，统计单词出现的次数。

总结

本篇文章简要介绍了字典树及其实现方法，在Python中实现字典树的方法十分简单，只需要使用嵌套字典即可。字典树适用于文本编辑器、自动补全、拼写检查以及搜索引擎系统等方面。如果对字典树进行深入的研究和掌握，可以给程序开发带来很多的便利，避免不必要的字符串比较，从而提高程序的性能。

Tags: ,