Trie (pronounced 'try')是一种树形数据结构，存储字符串用于字符结构匹配。Trie结构的主要应用是信息检索(information retrieval).字典树的名字也来自于单词retrieval.应用字段树的操作主要是结构匹配(pattern matching)和前缀匹配(prefix matching).
标准字典树(standard tries):
定义S是字母表西格玛中的s个字符的集合，S中没有任何字符是其他字符的前缀。满足下列条件的S的有序树T称为一个标准字典树:
1 除根节点外，其他结点用西格玛中的字符做标记(labeled with a character of sigma);
2 内部节点的子节点的各不相同(the children of an internal node have distinct labels);
3 该树的s个子叶分别对应了S中的字符，从根节点到任一子叶v，将路径上的标签(label)拼接，形成S中与子叶v对应的字符。
一个重要假设: S中没有任何字符串是其他字符串的前缀prefix. 这保证了S中字符串与T中的子叶一一对应.
命题/性质:
1 字典树T的高度与S中最长的字符串长度相同;
2 每个内部节点最多有|sigma|个子节点 (|sigma|是sigma字符集中字符串的个数);
3 字典树T有s个叶节点(s是S中字符串的个数);
4 字典树T的结点数不超过n+1 (n是S中所有字符串的总长度).
字典树T结点数的最坏情况发生在没有任何两个字符串有相同的非空前缀，也就是，除了根节点，所有内部节点都只有一个子结点。
应用:
可用于生成以S中字符串为key的字典，从根节点到叶节点拼接路径中结点的标签生成一个key，如果正在检索的key没有终止于叶节点，或T中不含有能拼接成该key的路径，则这个key在S中不存在。
检索一个长度为m的字符的复杂度是O(m*|sigma|)，最坏情况是检索T中的所有路径，也就是遍历S中的所有字符串，并且每个字符串都在最后一位得到检索结果。
Pattern matching的算法: word matching
生成字典树的算法: incremental algorithm
2020.02.23
一个假设:S中没有任何一个字符串是另一个字符串的前缀。在一个trie中插入一个新的长度为m的字符串X，跟踪路径并插入新的节点，复杂度是O(m*|sigma|)。而建立整个trie的复杂度是O(n)，其中n是S中所有字符串的总长度。
压缩字典树Compressed trie
针对standard trie中很多结点只有单一子结点的情况压缩字典树被提出。
描述性定义: 类似于标准字典树，但其每个内部节点有至少两个子结点。
定义结点为冗余(redundant)，如果结点含有一个子结点并且该结点不是根节点。
对于一个内部节点都是冗余的path，变成压缩字典树的算法如下，
从任意节点到最后一个冗余结点的每个hop，用tuple表示成(v0, v1), (v1, v2)...(vi-1, vi)，中v0和vi不是
冗余，其余冗余，则该path可表示成(v0, vi).
压缩字典树中的结点用字符串做标记(对比标准字典树中是字母)。
定理
一个压缩字典树T来自字符串集合S共s个字符串，其字母来自有d个元素的字母集，有如下性质
1 T中的每个内部结点有最少两个子节点，最多d个子节点;
2 T有s个叶节点;
3 T的结点个数是O(s).
压缩字典树的表达方式: 用字符串s的index表示。(有个图)
注意，检索压缩字典树并不一定比标准字典树更快，因为在traversing path的过程中仍然需要比较目标string和树中结点。
suffix trie后缀字典树: 不知道在说什么，略。
search engine indexing搜索引擎原理:
搜索引擎的核心是称为inverted index/file的字典，key-value pair是(w, L)，其中w是一个词，L是包含w的页面的collection。w称为index terms，是个尽可能大的词汇表。该字典中的元素称为occurrence lists并尽可能包含多的页面。搜索引擎用两类数据结构，
1 一个array用来保存不同index的occurrence lists,
2 一个压缩字典树保存index terms，每个叶结点保存该term对应的occurrence list在array中的index.
occurrence lists与字典树分离是为了保证树结构足够小以适应internal memory(放在内存里)。而occurrence lists的尺寸使得它们只能放在disk上。
用搜索引擎对关键字的检索如同用字典树做匹配检索。找到keyword，返回对应的occurrence lists。
使用多个keywords检索时，返回包含kw的所有页面，对不同kw的ol做交集(intersection). ol需要用根据地址排序的序列或map形式实现。
此外，每个ks的ol还要根据revelance对页面做ranking，ranking算法是搜索引擎的主要挑战。
reference:
1 M. Goodrich and etc, Data Structures and Algorithms in Python.
