Trie树初步认识

Trie树也叫字典树、前缀树和搜索处理、分词器关系很大Trie树是一棵按照字符路径存储字符串的树用空间换时间实现快速查找、前缀匹配。假如有一个词库appleappapplicationbananabandbank而用户的问题是app最普通的方法就是每个单词逐一比较但是如果词库数量很多检索效率就会非常低而Trie树则是按如下操作的root|a|p|p/ | \✓ l l| |e i|c|a|t|i|o|n按字符串的每个字符逐一比较检索出以app开头的所有词从而实现快速检索实际例子打开淘宝搜索华为立刻出现华为手机、华为手表、华为耳机等等Trie树华|为/ | \手机 mate60 平板Trie快速找到带有华为前缀的所有分支这就是自动补全Autocomplete与倒排索引的区别Trie树关注的是词本身以及前缀关系而倒排索引关注的是哪些文档包含这个词区别还是很大的