利用trie树实现前缀输入提示及trie的python实现

时间:2022-02-23 23:58:17

代码来自https://github.com/wklken/suggestion/blob/master/easymap/suggest.py

还实现了缓存功能,搜索某个前缀超过一定次数时,进行缓存,减少搜索时间:将词后缀部分存储在节点

使用了词频信息,可以对返回的列表进行排序

使用dict实现trie,效率较高

trie的原理及实现参考https://segmentfault.com/a/1190000008877595

trie有三种实现方式,其中DoubleArrayTrie时间复杂度最优

待研究DoubleArrayTrie的实现

suggest.py