Trie树的C++实现

Trie—单词查找树

Trie,又称单词查找树、前缀树,是一种哈希树的变种。应用于字符串的统计与排序,经常被搜索引擎系统用于文本词频统计。

性质:
1.根节点不包含字符,除根节点外的每一个节点都只包含一个字符。
2.从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
3.每个节点的所有子节点包含的字符都不相同。

优点:
1.查询快。对于长度为m的键值,最坏情况下只需花费O(m)的时间;而BST需要O(m log n)的时间。
2.当存储大量字符串时,Trie耗费的空间较少。因为键值并非显式存储的,而是与其他键值共享子串。

操作:
1.初始化或清空:遍历Trie,删除所有节点,只保留根节点。

2.插入字符串
1).设置当前节点为根节点,设置当前字符为插入字符串中的首个字符;
2).在当前节点的子节点上搜索当前字符,若存在,则将当前节点设为值为当前字符的子节点;否则新建一个值为当前字符的子节点,并将当前结点设置为新创建的节点。
3).将当前字符设置为串中的下个字符,若当前字符为0,则结束;否则转2.

3.查找字符串
搜索过程与插入操作类似,当字符找不到匹配时返回假;若全部字符都存在匹配,判断最终停留的节点是否为树叶,若是,则返回真,否则返回假。

4.删除字符串
首先查找该字符串,边查询边将经过的节点压栈,若找不到,则返回假;否则依次判断栈顶节点是否为树叶,若是则删除该节点,否则返回真。

#include <iostream>
using namespace std;

/* trie的节点类型 */
template <int Size> //Size为字符表的大小
struct trie_node
{
    bool terminable; //当前节点是否可以作为字符串的结尾
    int node; //子节点的个数
    trie_node *child[Size]; //指向子节点指针

    /* 构造函数 */
    trie_node() : terminable(false), node(0) { memset(child, 0, sizeof(child)); }
};

/* trie */
template <int Size, typename Index> //Size为字符表的大小,Index为字符表的哈希函数
class trie
{
public:
    /* 定义类型别名 */
    typedef trie_node<Size> node_type;
    typedef trie_node<Size>* link_type;

    /* 构造函数 */
    trie(Index i = Index()) : index(i){ }

    /* 析构函数 */
    ~trie() { clear(); }

    /* 清空 */
    void clear()
    {
        clear_node(root);
        for (int i = 0; i < Size; ++i)
            root.child[i] = 0;
    }

    /* 插入字符串 */
    template <typename Iterator>
    void insert(Iterator begin, Iterator end)
    {
        link_type cur = &root; //当前节点设置为根节点
        for (; begin != end; ++begin)
        {
            if (!cur->child[index[*begin]]) //若当前字符找不到匹配,则新建节点
            {
                cur->child[index[*begin]] = new node_type;
                ++cur->node; //当前节点的子节点数加一
            }
            cur = cur->child[index[*begin]]; //将当前节点设置为当前字符对应的子节点
        }
        cur->terminable = true; //设置存放最后一个字符的节点的可终止标志为真
    }

    /* 插入字符串,针对C风格字符串的重载版本 */
    void insert(const char *str)
    {
        insert(str, str + strlen(str));
    }

    /* 查找字符串,算法和插入类似 */
    template <typename Iterator>
    bool find(Iterator begin, Iterator end)
    {
        link_type cur = &root;
        for (; begin != end; ++begin)
        {
            if (!cur->child[index[*begin]])
                return false;
            cur = cur->child[index[*begin]];
        }
        return cur->terminable;
    }

    /* 查找字符串,针对C风格字符串的重载版本 */
    bool find(const char *str)
    {
        return find(str, str + strlen(str));
    }

    /* 删除字符串 */
    template <typename Iterator>
    bool erase(Iterator begin, Iterator end)
    {
        bool result; //用于存放搜索结果
        erase_node(begin, end, root, result);
        return result;
    }

    /* 删除字符串,针对C风格字符串的重载版本 */
    bool erase(char *str)
    {
        return erase(str, str + strlen(str));
    }

    /* 按字典序遍历单词树 */
    template <typename Functor>
    void traverse(Functor &execute = Functor())
    {
        visit_node(root, execute);
    }

private:
    /* 访问某结点及其子结点 */
    template <typename Functor>
    void visit_node(node_type cur, Functor &execute)
    {
        execute(cur);
        for (int i = 0; i < Size; ++i)
        {
            if (cur.child[i] == 0) continue;
            visit_node(*cur.child[i], execute);
        }
    }
    /* 清除某个节点的所有子节点 */
    void clear_node(node_type cur)
    {
        for (int i = 0; i < Size; ++i)
        {
            if (cur.child[i] == 0) continue;
            clear_node(*cur.child[i]);
            delete cur.child[i];
            cur.child[i] = 0;
            if (--cur.node == 0) break;
        }
    }

    /* 边搜索边删除冗余节点,返回值用于向其父节点声明是否该删除该节点 */
    template <typename Iterator>
    bool erase_node(Iterator begin, Iterator end, node_type &cur, bool &result)
    {
        if (begin == end) //当到达字符串结尾:递归的终止条件
        {
            result = cur.terminable; //如果当前节点可以作为终止字符,那么结果为真
            cur.terminable = false;  //设置该节点为不可作为终止字符,即删除该字符串
            return cur.node == 0;    //若该节点为树叶,那么通知其父节点删除它
        }
        //当无法匹配当前字符时,将结果设为假并返回假,即通知其父节点不要删除它
        if (cur.child[index[*begin]] == 0) return result = false;
        //判断是否应该删除该子节点
        else if (erase_node((++begin)--, end, *(cur.child[index[*begin]]), result))
        {
            delete cur.child[index[*begin]]; //删除该子节点
            cur.child[index[*begin]] = 0; //子节点数减一
            //若当前节点为树叶,那么通知其父节点删除它
            if (--cur.node == 0 && cur.terminable == false) return true;
        }
        return false; //其他情况都返回假
    }

    /* 根节点 */
    node_type root;

    /* 将字符转换为索引的转换表或函数对象 */
    Index index;
};

//index function object
class IndexClass
{
public:
    int operator[](const char key)
    {
        return key % 26;
    }
};

int main()
{
    trie<26,IndexClass> t;
    t.insert("tree");
    t.insert("tea");
    t.insert("A");
    t.insert("ABC");

    if(t.find("tree"))
        cout<<"find tree"<<endl;
    else
        cout<<"not find tree"<<endl;

    if(t.find("tre"))
        cout<<"find tre"<<endl;
    else
        cout<<"not find tre"<<endl;

    if(t.erase("tree"))
        cout<<"delete tree"<<endl;
    else
        cout<<"not find tree"<<endl;

    if(t.find("tree"))
        cout<<"find tree"<<endl;
    else
        cout<<"not find tree"<<endl;

    return 0;
}

http://en.wikipedia.org/wiki/Trie

 

作者:阿凡卢

出处:http://www.cnblogs.com/luxiaoxun/

本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。

http://www.cnblogs.com/luxiaoxun/archive/2012/09/03/2668611.html

时间: 2016-05-20

Trie树的C++实现的相关文章

从Trie树(字典树)谈到后缀树(10.28修订)

作者:July.yansha. 出处:http://blog.csdn.net/v_JULY_v .  引言     常关注本blog的读者朋友想必看过此篇文章:从B树.B+树.B*树谈到R 树,这次,咱们来讲另外两种树:Tire树与后缀树.不过,在此之前,先来看两个问题.     第一个问题: 一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前10个词,请给出思想,给出时间复杂度分析.     之前在此文:海量数据处理面试题集锦与Bit-map详解中给出的参考答案:用trie

字典树(Trie树)的实现及应用

一.字典树的概念 Trie树,又称字典树,单词查找树或者前缀树,是一种用于快速检索的多叉树结构,如英文字母的字典树是一个26叉树,数字的字典树是一个10叉树. 与二叉查找树不同,Trie树的键不是直接保存在节点中,而是由节点在树中的位置决定.一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串.一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值. Trie树优点是最大限度地减少无谓的字符串比较,查询效率比较高.核心思想是空间换时

关于Trie树的模板

Trie树又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种.典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计.它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高. ---百度百科 具体给出代码,这也是根据大牛们的一些代码整的,,还是太渣了..... #include <iostream> #include <cstdio> #include <cstring&g

Hash树(散列树)和Trie树(字典树、前缀树)

1.Hash树 理想的情况是希望不经过任何比较,一次存取便能得到所查的记录, 那就必须在记的存储位置和它的关键字之间建立一个确定的对应关系f,使每个关键字和一个唯一的存储位置相对应.因而在查找时,只要根据这个对应关系f找到 给定值K的像f(K).由此,不需要进行比较便可直接取得所查记录.在此,我们称这个对应关系为哈希(Hash)函数,按这个思想建立的表为哈希表. 在哈希表中对于不同的关键字可能得到同一哈希地址,这种现象称做冲突.在一般情况下,冲突只能尽可能地减少,而不能完全避免.因为哈希函数是从

trie树

最近接触到数据处理这一块,也就自然接触到了Trie树.它又称字典树,是一种树形结构,是一种哈希树的变种.典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索系统用于文本词频统计,与比哈希表比查询效率要高. 主要思想 它的主要思想是空间换时间,利用字符串的公共前缀来降低查询时间的开销. 作为一种树型结构,利用不同的节点来保存某一信息的一位信息,该信息的的最大位数决定了tire数的深度.为了能表示所有可能的信息,它的每个节点的出度的最大值就是信息所包含的不同字符的最多个数.在每个

java-关于自然语言中Trie树修改版 请大家帮我填个注释吧 尤其是treeset

问题描述 关于自然语言中Trie树修改版 请大家帮我填个注释吧 尤其是treeset package MyTrie; import java.util.TreeSet; public class MyTrieUnit implements Comparable { int ch; // 某字符的ASCII码值 int val; // 标记是否为词的最后一位,并记录词对应的编号 TreeSet<MyTrieUnit> sons; public MyTrieUnit(int v) { ch = v

Python Trie树实现字典排序_python

一般语言都提供了按字典排序的API,比如跟微信公众平台对接时就需要用到字典排序.按字典排序有很多种算法,最容易想到的就是字符串搜索的方式,但这种方式实现起来很麻烦,性能也不太好.Trie树是一种很常用的树结构,它被广泛用于各个方面,比如字符串检索.中文分词.求字符串最长公共前缀和字典排序等等,而且在输入法中也能看到Trie树的身影. 什么是Trie树 Trie树通常又称为字典树.单词查找树或前缀树,是一种用于快速检索的多叉树结构.如图数字的字典是一个10叉树: 同理小写英文字母或大写英文字母的字

Java中实现双数组Trie树实例_java

传统的Trie实现简单,但是占用的空间实在是难以接受,特别是当字符集不仅限于英文26个字符的时候,爆炸起来的空间根本无法接受. 双数组Trie就是优化了空间的Trie树,原理本文就不讲了,请参考An Efficient Implementation of Trie Structures,本程序的编写也是参考这篇论文的. 关于几点论文没有提及的细节和与论文不一一致的实现: 1.对于插入字符串,如果有一个字符串是另一个字符串的子串的话,我是将结束符也作为一条边,产生一个新的结点,这个结点新节点的Ba

6天通吃树结构—— 第五天 Trie树

原文:6天通吃树结构-- 第五天 Trie树      很有段时间没写此系列了,今天我们来说Trie树,Trie树的名字有很多,比如字典树,前缀树等等. 一:概念      下面我们有and,as,at,cn,com这些关键词,那么如何构建trie树呢? 从上面的图中,我们或多或少的可以发现一些好玩的特性.       第一:根节点不包含字符,除根节点外的每一个子节点都包含一个字符.       第二:从根节点到某一节点,路径上经过的字符连接起来,就是该节点对应的字符串.       第三:每个

Trie树_字典树(字符串排序)简介及实现_其它综合

1.综述 又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种.典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计.它的优点是:利用字符串的公共前缀来节约存储空间,最大限度地减少无谓的字符串比较,查询效率比哈希表高. Trie树结构的优点在于:1) 不限制子节点的数量: 2) 自定义的输入序列化,突破了具体语言.应用的限制,成为一个通用的框架: 3) 可以进行最大Tokens序列长度的限制:4) 根据已定阈值输出重复的字符串:5) 提