字典树学习与应用
前言
最近在使用公司的系统发现智能问答系统的输入提醒挺有意思。具体的效果类似百度搜索时候的文本提醒。今天就研究一下具体的实现，主要的数据结构就是字典树。
先看看具体要实现的效果（这里以百度搜索为例）：
解读一下：通过输入文字联想到想要搜索的文字。非常适合特定领域以及知识库的搜索。
正文
字典树简介
字典树，英文名 trie。顾名思义，就是一个像字典一样的树。
字典树的特点如下：
根节点不包含字符，除根节点外每一个节点都只包含一个字符。
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节点包含的字符都不相同。
如图即为一颗字典树 1->2->6->11 即为字符串 aba。
字典树的实现
具体的实现可以参考 letcode
字典树的应用
如前言中的图片展示，可以用在搜索时候的自动补齐。下面就用 Python 实现一颗字典树，除了基本的功能外，完成数据的自动推荐。
class Trie: def __init__(self): self.root = {} def insert(self, word: str) -> None: node = self.root for s in word: if s in node.keys(): node = node[s] else: node[s] = {} node = node[s] node['is_word'] = True def search(self, word: str) -> bool: node = self.root for s in word: if s in node.keys(): node = node[s] else: return False if 'is_word' in node.keys(): return True else: return False def startsWith(self, prefix: str) -> bool: node = self.root for s in prefix: if s in node.keys(): node = node[s] else: return False return True def startsWithWords(self, prefix: str): node = self.root for s in prefix: if s in node.keys(): node = node[s] else: return [""] res = [] self.printWords(node, prefix, res) return res def printWords(self, node: dict, start: str, res): if node.get('is_word'): res.append(start) return for k in node.keys(): self.printWords(node[k], start+k, res) 复制代码下面就手动插入数据进行测试，结果如下：
t = Trie() t.insert("餐饮发票") t.insert("加班餐费怎么报销") t.insert("打车发票怎么获取") t.insert("差旅费用的标准") t.insert("发票邮寄") t.insert("餐饮发票类型的要求") t.insert("发票抬头怎么写") print(t.startsWithWords("发票")) # ['发票邮寄', '发票抬头怎么写'] 复制代码PS： 这里只演示代码中的实现，具体搜索框的实现感兴趣的小伙伴可以自行封装 API 。
总结
上面只是介绍基本字典树的实现，这里推荐一个谷歌基于 Python 实现的字典树
简单的使用如下，功能类似为根据前缀匹配出可能的结果：
import pygtrie t = pygtrie.StringTrie() t['发票'] = '发票' t['发票/快递'] = '发票快递' t['发票/报销'] = '发票报销' t['发票/税率'] = '发票税率' t['餐饮/发票'] = '餐饮发票' t['交通/发票'] = '交通发票' print(t.items(prefix='发票')) # [('发票', '发票'), ('发票/快递', '发票快递'), ('发票/报销', '发票报销'), ('发票/税率', '发票税率')] 复制代码这里关于字典树的实现并没有考虑空间复杂度，关于更多字典树的种类以及实现可以参考 小白详解 Trie 树 。
letcode 上有很多关于字典树的实现，感兴趣的小伙伴可以自行了解。
作者：西红柿蛋炒饭
链接：https://juejin.cn/post/7025508904784101389