一個通用的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. /*********************************************************************
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. };
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);
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. /********************************************************/
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. }
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. }
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. }