数据结构 Trie 字典树

[SihangWu]

1. 简述

• Trie树，又称单词查找树、字典树，从字面意思即可理解，这种树的结构像英文字典一样，相邻的单词一般前缀相同，是一种用于快速检索的多叉树结构。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。之所以时间复杂度低，是因为其采用了以空间换取时间的策略。

  举个栗子：Trie树可以利用字符串的公共前缀来节约存储空间。如下图所示，该trie树用10个节点保存了6个字符串tea，ten，to，in，inn，int：

---

---

在该trie树中，字符串in，inn和int的公共前缀是“in”，因此可以只存储一份“in”以节省空间。当然，如果系统中存在大量字符串且这些字符串基本没有公共前缀，则相应的trie树将非常消耗内存，这也是trie树的一个缺点。

现在我们就可以归纳出trie树的三个基本特性：

1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。　
3. 每个节点的所有子节点包含的字符都不相同。
   另一个栗子，给出一组单词，inn, int, at, age, adv, ant, 我们可以得到下面的Trie：

---

---

可以看出：

1. 每条边对应一个字母。
2. 每个节点对应一项前缀。叶节点对应最长前缀，即单词本身。
3. 单词inn与单词int有共同的前缀“in”, 因此他们共享左边的一条分支，root->i->in。4）同理，ate, age, adv, 和ant共享前缀"a"，所以他们共享从根节点到节点"a"的边。
4. 查询操纵非常简单。比如要查找int，顺着路径i -> in -> int就找到了。

2.Trie树的基本实现

trie基本操作有：查找、插入和删除。

• 首先定义trie树节点，例如对于纯英文字母的trie数，我们知道字母有26个，那么我们构建的trie树就是一个26叉树，每个节点包含26个子节点。
• 插入：
  对于一个单词，从根开始，沿着单词的各个字母所对应的树中的节点分支向下走，直到单词遍历完，将最后的节点标记为红色（或者记录该点的count，+1），表示该单词已插入trie树。
• 删除：
  类似反过来的插入操作，我们不仅要删除该节点的字符串编号，还要对词频减一操作。
• 查找：
  1. 从根结点开始一次搜索；
     取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索；
  2. 在相应的子树上，取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。
  3. 迭代过程……
  4. 在某个结点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。其他操作类似处理.
     
     例如从根开始按照单词的字母顺序向下遍历trie树，一旦发现某个节点标记不存在或者单词遍历完成而最后的节点未标记为红色，则表示该单词不存在，若最后的节点标记为红色，表示该单词存在。如下图中：trie树中存在的就是abc、d、da、dda四个单词。在实际的问题中可以将标记颜色的标志位改为数量count等其他符合题目要求的变量。

3. Trie树的高级实现

可以采用双数组（Double-Array）实现。利用双数组可以大大减小内存使用量，具体实现细节见参考资料。

4. Trie树的应用

• 字符串检索，词频统计，搜索引擎的热门查询
• 字符串最长公共前缀
  Trie树利用多个字符串的公共前缀来节省存储空间，反之，当我们把大量字符串存储到一棵trie树上时，我们可以快速得到某些字符串的公共前缀。
• 排序
  Trie树是一棵多叉树，只要先序遍历整棵树，输出相应的字符串便是按字典序排序的结果。
• 作为其他数据结构和算法的辅助结构
  如后缀树，AC自动机等。

5. Trie树复杂度分析

（1） 插入、查找的时间复杂度均为O(N)，其中N为字符串长度。
（2） 空间复杂度是26^n级别的，非常庞大（可采用双数组实现改善）。

6. Code

　　良玉最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀)
输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给良玉统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.
（注意:本题只有一组测试数据,处理到文件结束.）
对于每个提问,给出以该字符串为前缀的单词的数量.

#include <iostream>
using namespace std;
typedef struct Trie
{
    int v;
    Trie *next[26];
 }Trie;

Trie root;
void createTrie(char *str)
{
    int len = strlen(str);
    Trie *p = &root, *q;
    for(int i=0; i<len; ++i)
    {
        int id = str[i]-'a';
        if(p->next[id] == NULL)
          {
              q = (Trie *)malloc(sizeof(root));
              q->v = 1;
              for(int j=0; j<26; ++j)
              q->next[j] = NULL;
              p->next[id] = q;
              p = p->next[id];
          }
         else
         {
              p->next[id]->v++;
              p = p->next[id];
         }
    }
}

int findTrie(char *str)
 {
    int len = strlen(str);
    Trie *p = &root;
    for(int i=0; i<len; ++i)
        {
         int id = str[i]-'a';
         p = p->next[id];
         if(p == NULL) return 0;
        }
    return p->v;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    char str[15];
    int i;
    for(i=0; i<26; ++i)
    root.next[i] = NULL;
    while(gets(str) && str[0]!='\0')
    createTrie(str);
    memset(str, 0, sizeof(str));
    while(scanf("%s", str) != EOF)
    {
        int ans = findTrie(str);
        printf("%d\n", ans);
    }
    return 0;
}

/***************************************************   
Name: Trie树的基本实现 
Description: Trie树的基本实现，包括查找、插入和删除操作
***************************************************/
#include<algorithm>
#include<iostream>
using namespace std;
const int sonnum=26,base='a';
struct Trie
{
    int num;//记录多少单词途径该节点，即多少单词拥有以该节点为末尾的前缀
    bool terminal;//若terminal==true，该节点没有后续节点
    int count;//记录单词的出现次数，此节点即一个完整单词的末尾字母
    struct Trie *son[sonnum];//后续节点
};
/*********************************
创建一个新节点
*********************************/
Trie *NewTrie()
{
    Trie *temp=new Trie;
    temp->num=1;
    temp->terminal=false;
    temp->count=0;
    for(int i=0;i<sonnum;++i)temp->son[i]=NULL;
    return temp;
}
/*********************************
插入一个新词到字典树
pnt:树根
s  :新词
len:新词长度
*********************************/
void Insert(Trie *pnt,char *s,int len)
{
    Trie *temp=pnt;
    for(int i=0;i<len;++i)
        {
            if(temp->son[s[i]-base]==NULL)temp->son[s[i]-base]=NewTrie();
            else {temp->son[s[i]-base]->num++;temp->terminal=false;}
            temp=temp->son[s[i]-base];
        }
    temp->terminal=true;
    temp->count++;
}
/*********************************
删除整棵树
pnt:树根
*********************************/
void Delete(Trie *pnt)
{
    if(pnt!=NULL)
    {
        for(int i=0;i<sonnum;++i)if(pnt->son[i]!=NULL)Delete(pnt->son[i]);
        delete pnt; 
        pnt=NULL;
    }
}
/*********************************
查找单词在字典树中的末尾节点
pnt:树根
s  :单词
len:单词长度
*********************************/
Trie* Find(Trie *pnt,char *s,int len)
{
    Trie *temp=pnt;
    for(int i=0;i<len;++i)
    if(temp->son[s[i]-base]!=NULL)temp=temp->son[s[i]-base];
    else return NULL;
    return temp;
}

7. 总结

Trie树是一种非常重要的数据结构，它在信息检索，字符串匹配等领域有广泛的应用，同时，它也是很多算法和复杂数据结构的基础，如后缀树，AC自动机等。

8. 参考资料

wiki：http://en.wikipedia.org/wiki/Trie
Trie树：应用于统计和排序http://blog.csdn.net/hguisu/article/details/8131559
数据结构之Trie树：http://dongxicheng.org/structure/trietree/
Trie树http://www.cnblogs.com/huangxincheng/archive/2012/11/25/2788268.html
Trie树|字典树(字符串排序)
http://www.cnblogs.com/shuaiwhu/archive/2012/05/05/2484676.html
Trie（数字树、字典树、前缀树）http://blog.sina.com.cn/s/blog_72ef7bea0101drz3.html
HDOJ 1251 统计难题解http://www.wutianqi.com/?p=1364
字典树简介和简易应用http://blog.csdn.net/ly01kongjian/article/details/8743100
深入双数组Trie（Double-Array Trie）http://blog.csdn.net/zhoubl668/article/details/6957830
双数组Trie树(DoubleArrayTrie)Java实现http://www.hankcs.com/program/java/%E5%8F%8C%E6%95%B0%E7%BB%84trie%E6%A0%91doublearraytriejava%E5%AE%9E%E7%8E%B0.html

[Zhangjd]

写得不错，请更新下首页目录。

[joyking7]

近期复习数据结构，不错不错