一個通用的Trie樹，標准C++實現

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: [email protected] or [email protected] 
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. * http://www.linuxidc.com
11. * Version: 0.1 
12. * Last update: 2012-4-2 
13. *********************************************************************/  
14. /********************************************************************* 
15.  
16. *********************************************************************/  
17. #ifndef TRIE_H   
18. #define TRIE_H   
19. #include <iostream>   
20. #include <fstream>   
21. #include <string>   
22. #include <vector>   
23. #include <stdio.h>   
24. namespace MyUtility  
25. {  
26.     /*用於存儲原子數據的數據結構*/  
27.     typedef struct TrieNode  
28.     {  
29.         char* token;/*Trie節點的token值*/  
30.         bool terminal;/*當前節點是否是終結點*/  
31.         struct TrieNode* sons;/*子節點*/  
32.         struct TrieNode* next;/*兄弟節點*/  
33.     }TrieNode;  
34.     /*輸出結果的數據結構*/  
35.     typedef struct StrFreq  
36.     {  
37.         std::string Str;/*字符串*/  
38.         int Freq;/*頻率*/  
39.     }StrFreq;  
40.     class Trie  
41.     {  
42.     public:  
43.         Trie()  
44.         {  
45.             CreateRoot();  
46.             travel_path.clear();  
47.             result.clear();  
48.             threshhold = 3;  
49.             maxLength = 9 ;  
50.             fout.open("result.txt");  
51.         }  
52.         ~Trie()  
53.         {  
54.             Destroy();  
55.         }  
56.         /*設置輸出重復字符串頻率的阈值*/  
57.         void SetThreshhold(int ts)  
58.         {  
59.             if(ts<=1)  
60.             {  
61.                 return ;  
62.             }  
63.             threshhold = ts;  
64.         }  
65.         /*設置最長的字符串匹配長度的阈值*/  
66.         void SetMaxLength(int max_leng)  
67.         {  
68.             if(max_leng <= 1)  
69.             {  
70.                 return ;  
71.             }  
72.             maxLength = max_leng;  
73.         }  
74.         /*輸出結果*/  
75.         void Print(std::vector<StrFreq>& result);  
76.         void Print();  
77.         bool AddString(const std::string& str);  
78.         /*取得一個字符串的重復頻率*/  
79.         int StrFrequency(const char* str);  
80.         /*清空Trie樹*/  
81.         bool Clear();  
82.     private:  
83.         std::ofstream fout;  
84.         TrieNode * Root;/*Trie樹根節點*/  
85.         std::vector<std::string>travel_path;/*遍歷是的訪問路徑*/  
86.         std::vector<StrFreq>result;/*重復字符串的輸出結果*/  
87.         int sub_sons;/*一個節點的子節點數量*/  
88.         int threshhold;/*重復字符串輸出阈值，默認為2*/  
89.         int maxLength;/*最長的Tokens序列長度，默認為9*/  
90.         void Tokenize(const std::string& str,std::vector<std::string>&vec_tokens);  
91.         TrieNode * InsertNode(TrieNode* node,const char *token,bool end = false);  
92.         /*查找一個節點是否有子節點值為token的節點，返回子節點的指針*/  
93.         TrieNode * FindNode(TrieNode* p_node,const char *token);  
94.         /*初始化一個新的Trie節點*/  
95.         inline TrieNode* NewNode()  
96.         {  
97.             TrieNode * newNode  = new TrieNode();  
98.             newNode->sons = NULL;  
99.             newNode->next = NULL;  
100.             newNode->token = NULL;  
101.             newNode->terminal = false;  
102.             return newNode;  
103.         }  
104.         /*初始化一個新的Trie樹根節點*/  
105.         void CreateRoot()  
106.         {  
107.             if( NULL != Root)  
108.             {  
109.                 delete Root;  
110.                 Root = NULL;  
111.             }  
112.             Root = NewNode();  
113.             char * root_tag ="Root";  
114.             Root->token = new char[sizeof(char)*strlen(root_tag)];  
115.             strcpy(Root->token,root_tag);  
116.         }  
117.         /*銷毀Trie樹*/  
118.         void Destroy();  
119.         /*銷毀Trie子樹*/  
120.         void Destroy(TrieNode * node);  
121.         /*遍歷樹結構*/  
122.         void Travel(TrieNode* node);  
123.         /*取得一個節點的子節點數*/  
124.         void TrieNodeSons(const TrieNode* node);  
125.         void TrieNodeSons(const TrieNode* node,const TrieNode* root);  
126.     };  
127.   
128. }  
129. #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.   
167.             if((sub_sons >= threshhold))  
168.             //if((sum != sub_sons) && (sum >= threshhold))   
169.             {  
170.                 std::string buf="";  
171.                 for(int i=0;i<travel_path.size();i++)  
172.                 {  
173.                     buf += travel_path[i];  
174.                 }  
175.                 if(!buf.empty())  
176.                 {  
177.                     //fout<<buf<<"\t"<<sum<<std::endl;   
178.                     fout<<buf<<"\t"<<sub_sons<<std::endl;  
179.                 }  
180.             }  
181.             if(travel_path.size() > 0)  
182.             {  
183.                 travel_path.pop_back();  
184.             }  
185.             /********************************************************/  
186.             Travel(node->next);  
187.             /********************************************************/  
188.               
189.             /********************************************************/  
190.         }  
191.         else  
192.         {  
193.             return ;  
194.         }  
195.     }  
196.     void Trie::Print()  
197.     {  
198.         travel_path.clear();  
199.         result.clear();  
200.         Travel(Root);  
201.         std::cout<<"String\tFrequency"<<std::endl;  
202.         for(int i=0;i<result.size();i++)  
203.         {  
204.             std::cout<<result[i].Str <<"\t"<<result[i].Freq <<std::endl;  
205.         }  
206.         result.clear();  
207.     }  
208.     void Trie::Print(std::vector<StrFreq>& re_result)  
209.     {  
210.         travel_path.clear();  
211.         result.clear();  
212.         Travel(Root);  
213.         //re_result = result;   
214.         //result.clear();   
215.     }  
216.     /*   
217.     ************************************************* 
218.     功能   : 輸入Trie樹字符串 
219.     參數   :  
220.     返回值 :  
221.     ------------------------------------------------- 
222.     備注   : 
223.     ------------------------------------------------- 
224.     作者   ：Li Yachao 
225.     時間   ：2012-4-3 
226.     ************************************************* 
227.     */  
228.     bool Trie::AddString(const std::string &str)  
229.     {  
230.         std::vector<std::string>val;  
231.         std::vector<std::string>val_tmp;  
232.         Tokenize(str,val);  
233.         int step = maxLength;  
234.         for(int i=0;i<val.size();i++)  
235.         {  
236.             val_tmp.clear();  
237.             while((i+step) > val.size())  
238.             {  
239.                 step --;  
240.             }  
241.             for(int j=i;j< (i+step);j++)  
242.             {  
243.                 val_tmp.push_back(val[j]);  
244.             }  
245.             TrieNode* cur = Root;  
246.             for(int j=0;j<val_tmp.size();j++)  
247.             {  
248.                 if(j == val_tmp.size() - 1)  
249.                 {  
250.                     InsertNode(cur,val_tmp[j].c_str(),true);  
251.                 }  
252.                 else  
253.                 {  
254.                     cur = InsertNode(cur,val_tmp[j].c_str());  
255.                 }  
256.             }  
257.         }  
258.         return true;  
259.     }  
260.       
261.     /*   
262.     ************************************************* 
263.     功能   : 插入Trie樹節點 
264.     參數   :  
265.     返回值 : 插入節點的指針 
266.     ------------------------------------------------- 
267.     備注   : 
268.     ------------------------------------------------- 
269.     作者   ：Li Yachao 
270.     時間   ：2012-4-3 
271.     ************************************************* 
272.     */  
273.     TrieNode * Trie::InsertNode(TrieNode* node,const char *token,bool end)  
274.     {  
275.         if(NULL == node)  
276.         {  
277.             return NULL;  
278.         }  
279.         if(NULL == node->sons)  
280.         {  
281.             node->sons = NewNode();  
282.             node->sons->token = new char[sizeof(char)*strlen(token)];  
283.             strcpy(node->sons->token,token);  
284.             if(end)  
285.             {  
286.                 node->sons->terminal = true;  
287.             }  
288.             return node->sons;  
289.         }  
290.         else  
291.         {  
292.             TrieNode* cur = node->sons;  
293.             while(NULL != cur->next)  
294.             {  
295.                 if(strcmp(cur->token,token) == 0)  
296.                 {  
297.                     if(end)  
298.                     {  
299.                         cur->terminal = true;  
300.                     }  
301.                     return cur ;  
302.                 }  
303.                 if( NULL != cur->next)  
304.                 {  
305.                     cur = cur->next ;  
306.                 }  
307.                 else  
308.                 {  
309.                     break;  
310.                 }  
311.             }  
312.             if(strcmp(cur->token ,token) == 0)  
313.             {  
314.                 if(end)  
315.                 {  
316.                     cur->terminal = true;  
317.                 }  
318.                 return cur;  
319.             }  
320.             TrieNode* n = NewNode();  
321.             n->token = new char[sizeof(char)*strlen(token)];  
322.             strcpy(n->token ,token);  
323.             if(end)  
324.             {  
325.                 n->terminal = true;  
326.             }  
327.             cur->next = n;  
328.             return n;  
329.         }  
330.       
331.     }  
332.     /*   
333.     ************************************************* 
334.     功能   : 查找一個字符串的重復次數 
335.     參數   :  
336.     返回值 :  
337.     ------------------------------------------------- 
338.     備注   : 
339.     ------------------------------------------------- 
340.     作者   ：Li Yachao 
341.     時間   ：2012-4-3 
342.     ************************************************* 
343.     */  
344.     int Trie::StrFrequency(const char* str)  
345.     {  
346.         std::vector<std::string>tokens;  
347.         Tokenize(str,tokens);  
348.         TrieNode * cur = Root;  
349.         for(int i=0;i<tokens.size();i++)  
350.         {  
351.             cur = FindNode(cur,tokens[i].c_str());  
352.         }  
353.         if(NULL == cur)  
354.         {  
355.             return 0;  
356.         }  
357.         else  
358.         {  
359.             sub_sons =0;  
360.             TrieNodeSons(cur, cur);  
361.             return sub_sons;  
362.         }  
363.     }  
364.     /*   
365.     ************************************************* 
366.     功能   : 查找一個節點的指針 
367.     參數   :  
368.     返回值 :  
369.     ------------------------------------------------- 
370.     備注   : 
371.     ------------------------------------------------- 
372.     作者   ：Li Yachao 
373.     時間   ：2012-4-3 
374.     ************************************************* 
375.     */  
376.     TrieNode * Trie::FindNode(TrieNode *p_node, const char *token)  
377.     {  
378.         if((NULL != p_node) && (NULL != p_node->sons))  
379.         {  
380.             TrieNode *cur = p_node->sons;  
381.             while(NULL != cur)  
382.             {  
383.                 if(strcmp(cur->token,token) == 0)  
384.                 {  
385.                     return cur;  
386.                 }  
387.                 cur = cur->next;  
388.             }  
389.             return NULL;  
390.         }  
391.         else  
392.         {  
393.             return NULL;  
394.         }  
395.     }  
396. }