Trie树(字典树)实现

Trie树,又称字典树,单词查找树或者前缀树,是一种用于快速检索的多叉树结构,如英文字母的字典树是一个26叉树,数字的字典树是一个10叉树。

Trie树的概念

Trie树优点是最大限度地减少无谓的字符串比较,查询效率比较高。核心思想是空间换时间,利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
  1. 插入、查找的时间复杂度均为O(N),其中N为字符串长度。
  2. 空间复杂度是26^n级别的,非常庞大(可采用双数组实现改善)。
它有3个基本性质:
  1. 根节点不包含字符,除根节点外每一个节点都只包含一个字符。
  2. 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
  3. 每个节点的所有子节点包含的字符都不相同。

Trie树的应用场景

字符串检索

事先将已知的一些字符串(字典)的有关信息保存到trie树里,查找另外一些未知字符串是否出现过或者出现频率。
举例:
给出N 个单词组成的熟词表,以及一篇全用小写英文书写的文章,请你按最早出现的顺序写出所有不在熟词表中的生词。
给出一个词典,其中的单词为不良单词。单词均为小写字母。再给出一段文本,文本的每一行也由小写字母构成。判断文本中是否含有任何不良单词。例如,若rob是不良单词,那么文本problem含有不良单词。

字符串最长公共前缀

Trie树利用多个字符串的公共前缀来节省存储空间,反之,当我们把大量字符串存储到一棵trie树上时,我们可以快速得到某些字符串的公共前缀。
举例:
给出N 个小写英文字母串,以及Q 个询问,即询问某两个串的最长公共前缀的长度是多少?
解决方案:首先对所有的串建立其对应的字母树。此时发现,对于两个串的最长公共前缀的长度即它们所在结点的公共祖先个数,于是,问题就转化为了离线(Offline)的最近公共祖先(Least Common Ancestor,简称LCA)问题。
而最近公共祖先问题同样是一个经典问题,可以用下面几种方法:
  1. 利用并查集(Disjoint Set),可以采用采用经典的Tarjan 算法;
  2. 求出字母树的欧拉序列(Euler Sequence )后,就可以转为经典的最小值查询(Range Minimum Query,简称RMQ)问题了;

排序

Trie树是一棵多叉树,只要先序遍历整棵树,输出相应的字符串便是按字典序排序的结果。
比如给你N 个互不相同的仅由一个单词构成的英文名,让你将它们按字典序从小到大排序输出。

作为其他数据结构和算法的辅助

如后缀树,AC自动机等

词频统计

trie树在这里的应用类似哈夫曼树,
比如词频统计使用哈希表或者堆都可以,但是如果内存有限,就可以用trie树来压缩空间,因为trie树的公共前缀都是用一个节点保存的。

字符串搜索的前缀匹配

trie树常用于搜索提示。如当输入一个网址,可以自动搜索出可能的选择。当没有完全匹配的搜索结果,可以返回前缀最相似的可能。
Trie树检索的时间复杂度可以做到n,n是要检索单词的长度,
如果使用暴力检索,需要指数级O(N2)的时间复杂度。

Trie树的实现

/*trie.h*/
#ifndef TRIE_H
#define TRIE_H

typedef struct word_trie_t word_trie_t;
typedef enum bool bool;

enum bool
{
    false = 0,
    true = 1,
};

struct word_trie_t
{
    bool (*insert)(word_trie_t *this, char *str);
    bool (*find_word)(word_trie_t *this, char *str);
    int (*find_prefix)(word_trie_t *this, char *str);
    bool (*delete)(word_trie_t *this, char *str);
    void (*destroy)(word_trie_t *this);
};

word_trie_t *word_trie_create();
#endif
#include "trie.h"
#include<stdio.h>
#include<string.h>
#include<malloc.h>

#define TRIE_NODE_MAX 26

typedef struct trie_node_t trie_node_t;

struct trie_node_t
{
    int count;      //用来计算前缀数
    bool is_str;    //用来标识到此的字符串
    trie_node_t *word[TRIE_NODE_MAX];
};

trie_node_t* trie_node_create()
{
    trie_node_t* node=(trie_node_t*)malloc(sizeof(trie_node_t));
    memset(node, 0, sizeof(trie_node_t));       //node->is_str = 0;
    return node;
}

void trie_node_destroy(trie_node_t *node)
{
    free(node);
}

typedef struct private_word_trie_t private_word_trie_t;
struct private_word_trie_t
{
    word_trie_t public;
    trie_node_t *root;
};

bool insert(private_word_trie_t *this, char *str)
{
    printf("comming insert function...\n");
    trie_node_t *current=this->root;
    int word_pos;
    while(*str)
    {
        word_pos = *str-'a';
        if(current->word[word_pos] == NULL)
        {
            current->word[word_pos]=trie_node_create();
        }
        current=current->word[word_pos];
        
        str++;
    }
    current->count++;
    current->is_str = true;
    return true;
}

bool find_word(private_word_trie_t *this, char *str)
{
    printf("comming find_word function...\n");
    trie_node_t *current = this->root;
    int word_pos;
    while(*str)
    {
        word_pos = *str-'a';
        if((current = current->word[word_pos]) == NULL)
        {
            return false;
        }
        str++;
    }
    return current->is_str;
}

int find_prefix(private_word_trie_t *this, char *str)
{
    trie_node_t *current = this->root;
    int word_pos;
    while(*str)
    {
        word_pos=*str-'a';
        if((current = current->word[word_pos]) == NULL)
        {
            return 0;
        }
        str++;
    }
    return current->count;
}

bool delete(private_word_trie_t *this, char *str)
{
    trie_node_t *current = this->root;
    int word_pos;
    trie_node_t *del = NULL;
    if(find_word(this,str))
    {
        while(*str)
        {
            word_pos = *str-'a';
            if(((current->word[word_pos])->count--) == 0)
            {
                del=current->word[word_pos];
                current->word[word_pos] = NULL;
                str++;
                break;
            }
            str++;
        }

        if(del!=NULL)
        {
            while(*str)
            {
                word_pos = *str-'a';
                current = del;
                del=current->word[word_pos];
                trie_node_destroy(current);
                str++;
            }
            trie_node_destroy(del);
        }
        return true;
    }
    else
    {
        return false;
    }
}

void trie_destroy(trie_node_t *node)
{
    int i;
    for(i=0; i<TRIE_NODE_MAX; i++)
    {
        if(node->word[i]!=NULL)
        {
            trie_destroy(node->word[i]);
        }
    }
    trie_node_destroy(node);
}

void destroy(private_word_trie_t *this)
{
    trie_destroy(this->root);
    free(this);
}

word_trie_t *word_trie_create()
{
    private_word_trie_t *this = (private_word_trie_t *)malloc(sizeof(private_word_trie_t));
    this->public.insert = (bool (*)(word_trie_t *, char *))insert;
    this->public.find_word = (bool (*)(word_trie_t *, char *))find_word;
    this->public.find_prefix = (int (*)(word_trie_t *, char *))find_prefix;
    this->public.delete = (bool (*)(word_trie_t *, char *))delete;
    this->public.destroy=(void (*)(word_trie_t *))destroy;
    this->root = trie_node_create();
    return &this->public;
}

int main()
{
    word_trie_t *tree=word_trie_create();
    char str[100];
    while(gets(str)&&str[0])
    {
        printf("input str: [%s]\n",str);
        tree->insert(tree,str);
    }

    while(gets(str)&&str[0])
    {
        printf("前缀:%d\n",tree->find_prefix(tree,str));
        if(tree->find_word(tree,str))
        {
            printf("%s是插入的一个字符串\n",str);
        }
        else
        {
            printf("%s不是一个插入的字符串\n",str);
        }
    }
    tree->destroy(tree);
    return 1;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据