Trie树初步认识

Trie树：

也叫字典树、前缀树，和搜索处理、分词器关系很大，

Trie树是一棵按照字符路径存储字符串的树，用空间换时间，实现快速查找、前缀匹配。

假如有一个词库

apple
app
application
banana
band
bank

而用户的问题是app

最普通的方法，就是每个单词逐一比较，但是如果词库数量很多，检索效率就会非常低

而Trie树则是按如下操作的：

root
|
a
|
p
|
p
/ | \
✓ l l
| |
e i
|
c
|
a
|
t
|
i
|
o
|
n

按字符串的每个字符逐一比较，检索出以app开头的所有词，从而实现快速检索

实际例子：

打开淘宝搜索：华为

立刻出现华为手机、华为手表、华为耳机等等

Trie树：

华
|
为
/ | \
手机 mate60 平板

Trie快速找到带有华为前缀的所有分支，这就是自动补全（Autocomplete）

与倒排索引的区别：Trie树关注的是词本身以及前缀关系，而倒排索引关注的是哪些文档包含这个词，区别还是很大的