设为首页收藏本站

编程十万个为什么,属于程序员的编程论坛

 找回密码
 5秒快速注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

搜索
查看: 8119|回复: 11

[原创] 一个通用的Trie树,标准C++实现

[复制链接]
发表于 2012-4-3 17:17:30 | 显示全部楼层 |阅读模式
1 Trie简介
       Trie树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。
        在本文中,对于输入的进行序列化,比如输入“单词查找树”,序列化为“单/词/查/找/树”,这样可以进行任何一种自定义的数据插入和查询。序列化输入可以根据自己的需要进行相应的改动,这样可以把Trie树结构应用到很多其他的语言和领域。
        本Trie树结构的优点在于:
       1 不限制子节点的数量;
       2 自定义的输入序列化,突破了具体语言、应用的限制,成为一个通用的框架;
       3 可以进行最大Tokens序列长度的限制;
       4 根据已定阈值输出重复的字符串;
       5 提供单个字符串频度查找功能;
       6 速度快,在两分钟内完成1998年1月份人民日报(19056行)的重复字符串抽取工作。
2 结构示意图
3  实现代码
Trie.h
  1. /********************************************************************
  2. * Copyright (C) 2012 Li Yachao
  3. * Contact: liyc7711@gmail.com or harry_lyc@foxmail.com
  4. *
  5. * Permission to use, copy, modify, and distribute this software for
  6. * any non-commercial purpose is hereby granted without fee, provided
  7. * that the above copyright notice appear in all copies and that both
  8. * that copyright notice.
  9. * It is provided "as is" without express or implied warranty.
  10. *
  11. * Version: 0.1
  12. * Last update: 2012-4-2
  13. *********************************************************************/
  14. /*********************************************************************

  15. *********************************************************************/
  16. #ifndef TRIE_H
  17. #define TRIE_H
  18. #include <iostream>
  19. #include <fstream>
  20. #include <string>
  21. #include <vector>
  22. #include <stdio.h>
  23. namespace MyUtility
  24. {
  25.         /*用于存储原子数据的数据结构*/
  26.         typedef struct TrieNode
  27.         {
  28.                 char* token;/*Trie节点的token值*/
  29.                 bool terminal;/*当前节点是否是终结点*/
  30.                 struct TrieNode* sons;/*子节点*/
  31.                 struct TrieNode* next;/*兄弟节点*/
  32.         }TrieNode;
  33.         /*输出结果的数据结构*/
  34.         typedef struct StrFreq
  35.         {
  36.                 std::string Str;/*字符串*/
  37.                 int Freq;/*频率*/
  38.         }StrFreq;
  39.         class Trie
  40.         {
  41.         public:
  42.                 Trie()
  43.                 {
  44.                         CreateRoot();
  45.                         travel_path.clear();
  46.                         result.clear();
  47.                         threshhold = 3;
  48.                         maxLength = 9 ;
  49.                         fout.open("result.txt");
  50.                 }
  51.                 ~Trie()
  52.                 {
  53.                         Destroy();
  54.                 }
  55.                 /*设置输出重复字符串频率的阈值*/
  56.                 void SetThreshhold(int ts)
  57.                 {
  58.                         if(ts<=1)
  59.                         {
  60.                                 return ;
  61.                         }
  62.                         threshhold = ts;
  63.                 }
  64.                 /*设置最长的字符串匹配长度的阈值*/
  65.                 void SetMaxLength(int max_leng)
  66.                 {
  67.                         if(max_leng <= 1)
  68.                         {
  69.                                 return ;
  70.                         }
  71.                         maxLength = max_leng;
  72.                 }
  73.                 /*输出结果*/
  74.                 void Print(std::vector<StrFreq>& result);
  75.                 void Print();
  76.                 bool AddString(const std::string& str);
  77.                 /*取得一个字符串的重复频率*/
  78.                 int StrFrequency(const char* str);
  79.                 /*清空Trie树*/
  80.                 bool Clear();
  81.         private:
  82.                 std::ofstream fout;
  83.                 TrieNode * Root;/*Trie树根节点*/
  84.                 std::vector<std::string>travel_path;/*遍历是的访问路径*/
  85.                 std::vector<StrFreq>result;/*重复字符串的输出结果*/
  86.                 int sub_sons;/*一个节点的子节点数量*/
  87.                 int threshhold;/*重复字符串输出阈值,默认为2*/
  88.                 int maxLength;/*最长的Tokens序列长度,默认为9*/
  89.                 void Tokenize(const std::string& str,std::vector<std::string>&vec_tokens);
  90.                 TrieNode * InsertNode(TrieNode* node,const char *token,bool end = false);
  91.                 /*查找一个节点是否有子节点值为token的节点,返回子节点的指针*/
  92.                 TrieNode * FindNode(TrieNode* p_node,const char *token);
  93.                 /*初始化一个新的Trie节点*/
  94.                 inline TrieNode* NewNode()
  95.                 {
  96.                         TrieNode * newNode  = new TrieNode();
  97.                         newNode->sons = NULL;
  98.                         newNode->next = NULL;
  99.                         newNode->token = NULL;
  100.                         newNode->terminal = false;
  101.                         return newNode;
  102.                 }
  103.                 /*初始化一个新的Trie树根节点*/
  104.                 void CreateRoot()
  105.                 {
  106.                         if( NULL != Root)
  107.                         {
  108.                                 delete Root;
  109.                                 Root = NULL;
  110.                         }
  111.                         Root = NewNode();
  112.                         char * root_tag ="Root";
  113.                         Root->token = new char[sizeof(char)*strlen(root_tag)];
  114.                         strcpy(Root->token,root_tag);
  115.                 }
  116.                 /*销毁Trie树*/
  117.                 void Destroy();
  118.                 /*销毁Trie子树*/
  119.                 void Destroy(TrieNode * node);
  120.                 /*遍历树结构*/
  121.                 void Travel(TrieNode* node);
  122.                 /*取得一个节点的子节点数*/
  123.                 void TrieNodeSons(const TrieNode* node);
  124.                 void TrieNodeSons(const TrieNode* node,const TrieNode* root);
  125.         };

  126. }
  127. #endif
复制代码
  1. #include "Trie.h"
  2. namespace MyUtility
  3. {
  4.         /*  
  5.         *************************************************
  6.         功能   : 中文文本预处理,序列化输入
  7.         参数   :
  8.         返回值 :
  9.         -------------------------------------------------
  10.         备注   :
  11.         -------------------------------------------------
  12.         作者   :Li Yachao
  13.         时间   :2012-4-3
  14.         *************************************************
  15.         */
  16.         void Trie::Tokenize(const std::string &str, std::vector<std::string> &vec_tokens)
  17.         {
  18.                 vec_tokens.clear();
  19.                 std::string tmp ="";
  20.                 if(str.empty())
  21.                 {
  22.                         return ;
  23.                 }
  24.                 for(int i=0;i<str.size();i++)
  25.                 {
  26.                         unsigned char c = str[i];
  27.                         if(c < 128)
  28.                         {
  29.                                 tmp = str.substr(i,1);
  30.                                 vec_tokens.push_back(tmp);
  31.                         }
  32.                         else
  33.                         {
  34.                                 tmp = str.substr(i,2);
  35.                                 vec_tokens.push_back(tmp);
  36.                                 i++;
  37.                         }
  38.                 }
  39.         }
  40.         /*  
  41.         *************************************************
  42.         功能   : 销毁Trie树
  43.         参数   :
  44.         返回值 :
  45.         -------------------------------------------------
  46.         备注   :
  47.         -------------------------------------------------
  48.         作者   :Li Yachao
  49.         时间   :2012-4-3
  50.         *************************************************
  51.         */
  52.         void Trie::Destroy()
  53.         {
  54.                 Destroy(Root);
  55.         }
  56.         void Trie::Destroy(TrieNode * node)
  57.         {
  58.                 if(NULL != node)
  59.                 {
  60.                         Destroy(node->sons);
  61.                         Destroy(node->next);
  62.                         delete node;
  63.                         node = NULL;
  64.                 }
  65.                 else
  66.                 {
  67.                         return ;
  68.                 }
  69.         }
  70.         /*  
  71.         *************************************************
  72.         功能   : 清空Trie树
  73.         参数   :
  74.         返回值 :
  75.         -------------------------------------------------
  76.         备注   :
  77.         -------------------------------------------------
  78.         作者   :Li Yachao
  79.         时间   :2012-4-3
  80.         *************************************************
  81.         */
  82.         bool Trie::Clear()
  83.         {
  84.                 Destroy();
  85.                 CreateRoot();
  86.                 travel_path.clear();
  87.                 result.clear();
  88.                 return true;
  89.         }
  90.         /*  
  91.         *************************************************
  92.         功能   : 取得一个Trie数节点的子节点数,即一个Token序列的重复次数。
  93.         参数   :
  94.         返回值 :
  95.         -------------------------------------------------
  96.         备注   :
  97.         -------------------------------------------------
  98.         作者   :Li Yachao
  99.         时间   :2012-4-3
  100.         *************************************************
  101.         */
  102.         void Trie::TrieNodeSons(const TrieNode * node,const TrieNode* root)
  103.         {
  104.                 if(NULL != node)
  105.                 {
  106.                         TrieNodeSons(node->sons,root);
  107.                         if(node->terminal)
  108.                         {
  109.                                 sub_sons++;/*以Token序列是否是序列结尾为标志*/
  110.                         }
  111.                         if(node != root)
  112.                         {/*根节点不能遍历其兄弟节点*/
  113.                                 TrieNodeSons(node->next,root);
  114.                         }
  115.                 }
  116.                 else
  117.                 {
  118.                         return  ;
  119.                 }
  120.         }
  121.         /*void Trie::TrieNodeSons(const TrieNode * node)
  122.         {
  123.                 if(NULL != node)
  124.                 {
  125.                         TrieNodeSons(node->sons);
  126.                         if(node->terminal)
  127.                         {
  128.                                 sub_sons++;
  129.                         }
  130.                         if(node != Root)
  131.                         {
  132.                                 TrieNodeSons(node->next);
  133.                         }
  134.                 }
  135.                 else
  136.                 {
  137.                         return  ;
  138.                 }
  139.         }*/
  140.         /*  
  141.         *************************************************
  142.         功能   : 遍历Trie数所有的节点,根据设定的threashold输出Token序列
  143.         参数   :
  144.         返回值 :
  145.         -------------------------------------------------
  146.         备注   :
  147.         -------------------------------------------------
  148.         作者   :Li Yachao
  149.         时间   :2012-4-3
  150.         *************************************************
  151.         */
  152.         void Trie::Travel(TrieNode* node)
  153.         {
  154.                 if(NULL != node)
  155.                 {
  156.                         if(node != Root)
  157.                         travel_path.push_back(node->token);
  158.                         Travel(node->sons);
  159.                         /********************************************************/
  160.                         sub_sons =0;
  161.                         //TrieNodeSons(node);
  162.                         TrieNodeSons(node,node);
  163.                         int sum = sub_sons;
  164.                         //sub_sons = 0;
  165.                         //TrieNodeSons(node->sons,node->sons);

  166.                         if((sub_sons >= threshhold))
  167.                         //if((sum != sub_sons) && (sum >= threshhold))
  168.                         {
  169.                                 std::string buf="";
  170.                                 for(int i=0;i<travel_path.size();i++)
  171.                                 {
  172.                                         buf += travel_path[i];
  173.                                 }
  174.                                 if(!buf.empty())
  175.                                 {
  176.                                         //fout<<buf<<"\t"<<sum<<std::endl;
  177.                                         fout<<buf<<"\t"<<sub_sons<<std::endl;
  178.                                 }
  179.                         }
  180.                         if(travel_path.size() > 0)
  181.                         {
  182.                                 travel_path.pop_back();
  183.                         }
  184.                         /********************************************************/
  185.                         Travel(node->next);
  186.                         /********************************************************/
  187.                        
  188.                         /********************************************************/
  189.                 }
  190.                 else
  191.                 {
  192.                         return ;
  193.                 }
  194.         }
  195.         void Trie::Print()
  196.         {
  197.                 travel_path.clear();
  198.                 result.clear();
  199.                 Travel(Root);
  200.                 std::cout<<"String\tFrequency"<<std::endl;
  201.                 for(int i=0;i<result.size();i++)
  202.                 {
  203.                         std::cout<<result[i].Str <<"\t"<<result[i].Freq <<std::endl;
  204.                 }
  205.                 result.clear();
  206.         }
  207.         void Trie::Print(std::vector<StrFreq>& re_result)
  208.         {
  209.                 travel_path.clear();
  210.                 result.clear();
  211.                 Travel(Root);
  212.                 //re_result = result;
  213.                 //result.clear();
  214.         }
  215.         /*  
  216.         *************************************************
  217.         功能   : 输入Trie树字符串
  218.         参数   :
  219.         返回值 :
  220.         -------------------------------------------------
  221.         备注   :
  222.         -------------------------------------------------
  223.         作者   :Li Yachao
  224.         时间   :2012-4-3
  225.         *************************************************
  226.         */
  227.         bool Trie::AddString(const std::string &str)
  228.         {
  229.                 std::vector<std::string>val;
  230.                 std::vector<std::string>val_tmp;
  231.                 Tokenize(str,val);
  232.                 int step = maxLength;
  233.                 for(int i=0;i<val.size();i++)
  234.                 {
  235.                         val_tmp.clear();
  236.                         while((i+step) > val.size())
  237.                         {
  238.                                 step --;
  239.                         }
  240.                         for(int j=i;j< (i+step);j++)
  241.                         {
  242.                                 val_tmp.push_back(val[j]);
  243.                         }
  244.                         TrieNode* cur = Root;
  245.                         for(int j=0;j<val_tmp.size();j++)
  246.                         {
  247.                                 if(j == val_tmp.size() - 1)
  248.                                 {
  249.                                         InsertNode(cur,val_tmp[j].c_str(),true);
  250.                                 }
  251.                                 else
  252.                                 {
  253.                                         cur = InsertNode(cur,val_tmp[j].c_str());
  254.                                 }
  255.                         }
  256.                 }
  257.                 return true;
  258.         }
  259.        
  260.         /*  
  261.         *************************************************
  262.         功能   : 插入Trie树节点
  263.         参数   :
  264.         返回值 : 插入节点的指针
  265.         -------------------------------------------------
  266.         备注   :
  267.         -------------------------------------------------
  268.         作者   :Li Yachao
  269.         时间   :2012-4-3
  270.         *************************************************
  271.         */
  272.         TrieNode * Trie::InsertNode(TrieNode* node,const char *token,bool end)
  273.         {
  274.                 if(NULL == node)
  275.                 {
  276.                         return NULL;
  277.                 }
  278.                 if(NULL == node->sons)
  279.                 {
  280.                         node->sons = NewNode();
  281.                         node->sons->token = new char[sizeof(char)*strlen(token)];
  282.                         strcpy(node->sons->token,token);
  283.                         if(end)
  284.                         {
  285.                                 node->sons->terminal = true;
  286.                         }
  287.                         return node->sons;
  288.                 }
  289.                 else
  290.                 {
  291.                         TrieNode* cur = node->sons;
  292.                         while(NULL != cur->next)
  293.                         {
  294.                                 if(strcmp(cur->token,token) == 0)
  295.                                 {
  296.                                         if(end)
  297.                                         {
  298.                                                 cur->terminal = true;
  299.                                         }
  300.                                         return cur ;
  301.                                 }
  302.                                 if( NULL != cur->next)
  303.                                 {
  304.                                         cur = cur->next ;
  305.                                 }
  306.                                 else
  307.                                 {
  308.                                         break;
  309.                                 }
  310.                         }
  311.                         if(strcmp(cur->token ,token) == 0)
  312.                         {
  313.                                 if(end)
  314.                                 {
  315.                                         cur->terminal = true;
  316.                                 }
  317.                                 return cur;
  318.                         }
  319.                         TrieNode* n = NewNode();
  320.                         n->token = new char[sizeof(char)*strlen(token)];
  321.                         strcpy(n->token ,token);
  322.                         if(end)
  323.                         {
  324.                                 n->terminal = true;
  325.                         }
  326.                         cur->next = n;
  327.                         return n;
  328.                 }
  329.        
  330.         }
  331.         /*  
  332.         *************************************************
  333.         功能   : 查找一个字符串的重复次数
  334.         参数   :
  335.         返回值 :
  336.         -------------------------------------------------
  337.         备注   :
  338.         -------------------------------------------------
  339.         作者   :Li Yachao
  340.         时间   :2012-4-3
  341.         *************************************************
  342.         */
  343.         int Trie::StrFrequency(const char* str)
  344.         {
  345.                 std::vector<std::string>tokens;
  346.                 Tokenize(str,tokens);
  347.                 TrieNode * cur = Root;
  348.                 for(int i=0;i<tokens.size();i++)
  349.                 {
  350.                         cur = FindNode(cur,tokens[i].c_str());
  351.                 }
  352.                 if(NULL == cur)
  353.                 {
  354.                         return 0;
  355.                 }
  356.                 else
  357.                 {
  358.                         sub_sons =0;
  359.                         TrieNodeSons(cur, cur);
  360.                         return sub_sons;
  361.                 }
  362.         }
  363.         /*  
  364.         *************************************************
  365.         功能   : 查找一个节点的指针
  366.         参数   :
  367.         返回值 :
  368.         -------------------------------------------------
  369.         备注   :
  370.         -------------------------------------------------
  371.         作者   :Li Yachao
  372.         时间   :2012-4-3
  373.         *************************************************
  374.         */
  375.         TrieNode * Trie::FindNode(TrieNode *p_node, const char *token)
  376.         {
  377.                 if((NULL != p_node) && (NULL != p_node->sons))
  378.                 {
  379.                         TrieNode *cur = p_node->sons;
  380.                         while(NULL != cur)
  381.                         {
  382.                                 if(strcmp(cur->token,token) == 0)
  383.                                 {
  384.                                         return cur;
  385.                                 }
  386.                                 cur = cur->next;
  387.                         }
  388.                         return NULL;
  389.                 }
  390.                 else
  391.                 {
  392.                         return NULL;
  393.                 }
  394.         }
  395. }
复制代码
发表于 2012-4-18 19:52:02 | 显示全部楼层
长时间没来看了 ~~  
发表于 2012-4-18 19:52:02 | 显示全部楼层
知道了 不错~~~  
发表于 2012-6-12 10:28:22 | 显示全部楼层
讲得很好,学习一下。
发表于 2012-8-19 10:19:00 | 显示全部楼层
先看看怎么样!  
发表于 2012-12-19 10:52:04 | 显示全部楼层
不错不错.,..我喜欢  
发表于 2012-12-19 10:52:04 | 显示全部楼层
谢谢分享  
发表于 2012-12-19 10:52:04 | 显示全部楼层
这个贴不错!!!!!  
发表于 2013-1-12 10:34:08 | 显示全部楼层
看看..  
发表于 2013-2-5 10:33:34 | 显示全部楼层
不错啊! 一个字牛啊!  
您需要登录后才可以回帖 登录 | 5秒快速注册

本版积分规则

关闭

BcWhy推荐上一条 /1 下一条

QQ|关于我们|最新帖子|小黑屋|手机版|编程十万个为什么 ( 粤ICP备16108587号-2  

GMT+8, 2017-3-26 13:21 , Processed in 0.235897 second(s), 26 queries , File On.

Powered by Discuz! X3.3

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表