概念

Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。

Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

它有3个基本性质：

• 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
• 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
• 每个节点的所有子节点包含的字符都不相同。

Trie 结构

• 关键码对象空间分解，“trie”这个词来源于“retrieval”
• 主要应用
  • 信息检索 (information retrieval)
  • 自然语言大规模的英文词典
• 常用结构
  • 字符树——26叉Trie
  • 二叉Trie树
    • 用每个字母(或数值)的二进制编码来代表
    • 编码只有0和1

词频统计实际例子（采用一纬数组存储子节点）：

/*** 在终端输入英文单词，crtl + z结束程序*/#include 
    
     #include 
     
      #include 
      
       #define TREE_WIDTH 256 //只搜索ASCII字符#define WORDLENMAX 128struct trie_node_st {        int count;        int pass; //统计前缀出现次数        struct trie_node_st *next[TREE_WIDTH];  //节点采用数组存储};static struct trie_node_st root={0,0, {NULL}};const char *spaces=" \t\n/.\"\'()";void myfree(struct trie_node_st * rt){    for(int i=0; i
       
        next[i]!=NULL){            myfree(rt->next[i]);            rt->next[i] = NULL;        }    }    free(rt);    return;}static intinsert (const char *word){        int i;        struct trie_node_st *curr, *newnode;        if (word[0]=='\0'){                return 0;        }        curr = &root;        for (i=0; ; ++i) {                if (word[i] == '\0') {                        break;                }                curr->pass++;//count                if (curr->next[ word[i] ] == NULL) {                        newnode = (struct trie_node_st*)malloc(sizeof(struct trie_node_st));                        memset (newnode, 0, sizeof(struct trie_node_st));                        curr->next[ word[i]] = newnode;                }                 curr = curr->next[ word[i] ];        }        curr->count ++;        return 0;}static voidprintword (const char *str, int n){        printf ("%s\t%d\n", str, n);}//深度优先static intdo_travel (struct trie_node_st *rootp){        static char worddump[WORDLENMAX+1];        static int pos=0;        int i;        if (rootp == NULL) {                return 0;        }        if (rootp->count) {                worddump[pos]='\0';                printword (worddump, rootp->count+rootp->pass);        }        for (i=0;i
        
         next[i]);                pos--;        }        return 0;}intmain (void){        char *linebuf=NULL, *line, *word;        size_t bufsize=0;        int ret;        while (1) {                ret=getline (&linebuf, &bufsize, stdin);                if (ret==-1) {                        break;                }                line=linebuf;                while (1) {                        word = strsep (&line, spaces);                        if (word==NULL) {                                break;                        }                        if (word[0]=='\0') {                                continue;                        }                        insert (word);                }        }        printf("\n");        do_travel (&root);        free (linebuf);    for(int i=0; i
        
       
      
     
    

然而上述的例子在实际中应用会很占内存，因为子节点每次都新建了大小为256的数组，为了兼顾查询与内存有三数组trie和

Trie的应用

• 自动补全 例如,你在百度搜索的输入框中,输入一个单词的前半部分,它能够自动补全出可能的单词结果。
• 拼写检查 例如,在word中输入一个拼写错误的单词, 它能够自动检测出来。
• IP路由表 在IP路由表中进行路由匹配时, 要按照最长匹配前缀的原则进行匹配。
• T9预测文本 在大多手机输入法中, 都会用9格的那种输入法. 这个输入法能够根据用户在9格上的输入,自动匹配出可能的单词。
• 填单词游戏 相信大多数人都玩过那种在横竖的格子里填单词的游戏。

Trie的优点

还有其他几种数据结构，如平衡树和哈希表，它们可以在字符串数据集中搜索一个单词。那为什么我们还需要trie？ 虽然哈希表在查找某个关键字时有O（1）的时间复杂度，但以下操作效率不高：

• 用共同的前缀查找所有的键。
• 以字典顺序列举字符串数据集。
• trie优于哈希表的另一个原因是，随着哈希表的大小增加，会有很多哈希冲突，搜索时间复杂度可能会恶化到O（n），其中n是插入的f关键字的数量。当存储具有相同前缀的多个关键字时，Trie可以使用比哈希表少的空间。在这种情况下，使用trie只有O（m）时间复杂度，其中m是关键字长度。而在平衡树中查找关键字的时间复杂度为O（mlogn）。

Trie的时间复杂度

插入和搜索都是O(m)的，m位关键字长度。 创建是O(字符串个数*字符串平均长度) 同理，空间复杂度也是上面的值。

压缩靠近叶结点的单路径

二叉Trie 结构

Patricia Trie(PAT trie)

将trie数中所有的单个子节点合并起来形成压缩trie树，又名Patricia Trie（Linux内核中叫做Radix Tree）。

PAT tree 在字符串子串匹配上有这非常优异的表现，这使得它经常成为一种高效的全文检索算法，在自然语言处理领域也有广泛的应用。其算法中最突出的特点就是采用半无限长字串(semi-infinite string 简称 sistring) 作为字符串的查找结构。

由于#结束符标记被看作是一个叶子结点，那么一颗Patricia Trie的任何内部结点有2个或以上的孩子结点。

Patricia Trie的基本操作包括：插入、删除和查询。插入操作可能会涉及到split（拆分），删除操作可能会涉及到merge（合并）。基于Patricia Trie的基本性质，split和merge操作都是局部的，这样实现起来比较简单。

Suffix Trees后缀数组与后缀树

主要是为了解决模式P在文本T中的位置的问题（比如KMP，BM算法）。在实际中Tkennel是很大的文档，我们需要反复搜索不同模式下的文档，这种情况我们希望对T预处理，是的求解该问的的时间是O(T)。 这种处理的数据结构就是后缀数组和后缀树，实际上他们是等价的，并且可以时空交换。

后缀数组

文本T的后缀数组就是T的按序排列的所有后缀的数组。 如果模式P在文本中出现，那么它必然是某个后缀的一个前缀。 通过对后缀数组二分查找来确定模式P是否存在于文本中。 计算后缀数组的运行时间受到排序时间影响，设字符串总长度为N，一般为O(NlogN)。但是如果是DNA的模式搜索，最长公共字串可能达到200 000个字符，在最极端情况下那么每次比较的时间就会达到O(N^2logN).

后缀树

后缀数组通过折半查找很容易搜索，但是折半查找会增加logT的开销。如果我们把后缀都存储起来比如存在一颗trie树中，就可以更有效第找到匹配的后缀。 同时如果树中存在许多只有一个子节点的节点的话，会很浪费空间，我们可以把这些但分支节点压缩成一个节点。 可以看出模式P的查找只依赖于模式P的长度。 如果原始字符串长度为N，则总的分支数小雨2N，但是由于树的边需要标记字符信息所以树的空间并不是线性的。还好我们可以用线性的空间简化trie树，做法如下：

1. 在叶节点上，使用后缀开始处的下标
2. 在内部节点上，存储从根直到该内部节点所匹配的公共字符数。这个数字代表字母代表探测深度。 如果我们有一颗后缀树，就可以通过对树进行一次中序遍历而计算出后缀数组和LCP数组。

后缀树与后缀数组的线性时间构建

。

算法的思想是：

1. 把后缀数组T分为两部分，每一部分的按照下标imod3来划分，然后合并imod3≠0的这两个后缀数组Sc。
2. 然后对Sc进行基数排序。
   • 我们取Sc对应的后缀的前3个字符，如果不够补一个T中没有出现的字符比如0，组成一个数组R.对R排序实际上就得到了对Sc的排序。
   • 对R基数排序得到R数组对应的名次数组R'.如果R中的某个元素的3个字符互不相等那么排序码就是后缀数组的排序码；否则的话需要递归地去求他们的名次数组的后缀数组（具体实现见代码）。然后把这个名次数组与相应的后缀数组对应上，我们就得到了rank(Si)数组，(Si属于Sc）同时rank(Sn+1)=rankS(n+2)=0;rank(S0)未定义。
3. 对mod3=0的进行排序，显而易见的是我们可以按照(ti,rank(Si+1))进行基数排序，因为按照Si的定义i后面的数就是Si+1，而Si+1又是已经拍好序了，这样就会节省时间。
4. 合并这三部分。同样，我们进行基数排序的比较方式合并。
   • i∈ B1 :Si ≤ Sj ⇐⇒ (ti , rank(Si+1)) ≤ (tj , rank(Sj+1))
   • i ∈ B2 : Si ≤ Sj ⇐⇒ (ti ,ti+1, rank(Si+2)) ≤ (tj ,tj+1, rank(Sj+2))
5. 他的时间复杂度是O(n)