Python 字典树的代码实现与开源项目

2023-04-11 00:00:00 代码 开源 字典

一. 字典树（Trie）是什么？

字典树（Trie），又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。常用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

二. 字典树的代码实现

下面是 Python 字典树的基本实现：

class TrieNode:
    def __init__(self):
        """
        Trie 节点结构体
        """
        self.children = dict()
        self.is_end = False  # 整个单词存储在叶子节点

class Trie:
    def __init__(self):
        """
        初始化 Trie
        """
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        """
        插入一个单词
        """
        node = self.root
        for w in word:
            if w not in node.children:
                node.children[w] = TrieNode()
            node = node.children[w]
        node.is_end = True

    def search(self, word: str) -> bool:
        """
        查找一个单词是否存在
        """
        node = self.root
        for w in word:
            if w not in node.children:
                return False
            node = node.children[w]
        return node.is_end

    def starts_with(self, prefix: str) -> bool:
        """
        查找前缀为 prefix 的单词是否存在
        """
        node = self.root
        for p in prefix:
            if p not in node.children:
                return False
            node = node.children[p]
        return True

在上面的代码实现中，TrieNode 是字典树节点的结构体，包含两个属性：

  • children：该节点的子节点，是一个字典，键为子节点的字符，值为子节点的 TrieNode 对象。
  • is_end：是否为一个完整单词的结尾（即该节点是否为叶子节点）。

Trie 类是字典树的主体，包含三个方法：

  • init: 初始化 Trie，创建根节点。
  • insert: 插入一个单词到 Trie 树中，从根节点开始遍历并插入需要插入的单词字母，直到单词的最后一个字母形成一个叶子节点。is_end 设为 True。
  • search: 在 Trie 树中查找一个单词是否存在，与 insert 操作完全一样，遍历单词的每个字母，并沿着 Trie 树向下移动一步，直到最后一个字母，看是否可以在 Trie 树中找到每个字母节点。
  • starts_with: 查找 Trie 树中是否有以给定前缀开头的单词，该方法与 search 方法类似，只是在查找 Trie 树叶子节点之前，根据给定的前缀沿着 Trie 树下移。

三. 开源项目

如果你想要更多的字典树相关实现代码，可以参考 GitHub 上的以下 Python 开源项目：

  • pytrie
  • ahocorasick
  • pygtrie

这些开源项目提供标准实现，通常包含更多功能和优化选项，可以根据自己的需要选择适合的。

相关文章