Python 字典树的自动补全与搜索提示功能

2023-04-11 00:00:00 功能提示字典

字典树（Trie树）是一种常用于字符串快速检索和自动补全的数据结构。它可以在很短的时间内完成对大量字符串的插入、删除和查找操作，并且可以很方便地实现自动补全和搜索提示等功能。

下面是一个使用Python实现的简单字典树，它可以实现对字符串的插入、查找和前缀匹配等操作：

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

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

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end

    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

    def autocomplete(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return []
            node = node.children[char]
        return self._fetch_words(node, prefix)

    def _fetch_words(self, node, prefix):
        words = []
        if node.is_end:
            words.append(prefix)

        for char in node.children:
            words += self._fetch_words(node.children[char], prefix + char)

        return words

这个字典树包含两个类：TrieNode和Trie。TrieNode表示字典树的节点，包含一个字典children和一个布尔变量is_end，children存储子节点，is_end表示当前节点是否为一个完整的单词的结尾。Trie表示整个字典树，包含一个根节点root，支持插入、查找、前缀匹配和自动补全等功能。

具体实现中，插入操作从根节点开始，将字符串逐个字符加入到字典树中，并将最后一个字符的节点标记为is_end为True。查找和前缀匹配操作同样从根节点开始，逐个字符查找，并且如果遇到不存在的节点则返回False。自动补全操作则需要首先找到对应的前缀节点，然后从这个节点开始递归地搜索所有单词，将所有以这个前缀为前缀的单词返回。

下面是一个简单的代码演示：

trie = Trie()
trie.insert("pidancode")
trie.insert("pidan")
trie.insert("pida")
trie.insert("皮蛋编程")
trie.insert("python")

print(trie.search("python")) # True
print(trie.search("pidan")) # True
print(trie.search("pid")) # False
print(trie.starts_with("pida")) # True
print(trie.autocomplete("p")) # ['pidan', 'pidancode', 'pida', 'python']

这个例子中我们创建了一个字典树，插入了几个单词，然后测试了查找、前缀匹配和自动补全等功能。可以看到字典树中所有单词都被正确存储和检索了。

相关文章