原文:6天通吃树结构—— 第五天 Trie树
很有段时间没写此系列了，今天我们来说Trie树，Trie树的名字有很多，比如字典树，前缀树等等。
一：概念
下面我们有and,as,at,cn,com这些关键词，那么如何构建trie树呢？
从上面的图中，我们或多或少的可以发现一些好玩的特性。
第一：根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
第二：从根节点到某一节点，路径上经过的字符连接起来，就是该节点对应的字符串。
第三：每个单词的公共前缀作为一个字符节点保存。
二：使用范围
既然学Trie树，我们肯定要知道这玩意是用来干嘛的。
第一：词频统计。
可能有人要说了，词频统计简单啊，一个hash或者一个堆就可以打完收工，但问题来了，如果内存有限呢？还能这么
玩吗？所以这里我们就可以用trie树来压缩下空间，因为公共前缀都是用一个节点保存的。
第二: 前缀匹配
就拿上面的图来说吧，如果我想获取所有以"a"开头的字符串，从图中可以很明显的看到是：and,as,at，如果不用trie树，
你该怎么做呢？很显然朴素的做法时间复杂度为O(N2) ，那么用Trie树就不一样了，它可以做到h，h为你检索单词的长度，
可以说这是秒杀的效果。
举个例子：现有一个编号为1的字符串”and“，我们要插入到trie树中，采用动态规划的思想，将编号”1“计入到每个途径的节点中，
那么以后我们要找”a“，”an“，”and"为前缀的字符串的编号将会轻而易举。
三：实际操作
到现在为止，我想大家已经对trie树有了大概的掌握，下面我们看看如何来实现。
1：定义trie树节点
为了方便，我也采用纯英文字母，我们知道字母有26个，那么我们构建的trie树就是一个26叉树，每个节点包含26个子节点。
1 #region Trie树节点
2 /// <summary>
3 /// Trie树节点
4 /// </summary>
5 public class TrieNode
6 {
7 /// <summary>
8 /// 26个字符，也就是26叉树
9 /// </summary>
10 public TrieNode[] childNodes;
11
12 /// <summary>
13 /// 词频统计
14 /// </summary>
15 public int freq;
16
17 /// <summary>
18 /// 记录该节点的字符
19 /// </summary>
20 public char nodeChar;
21
22 /// <summary>
23 /// 插入记录时的编码id
24 /// </summary>
25 public HashSet<int> hashSet = new HashSet<int>();
26
27 /// <summary>
28 /// 初始化
29 /// </summary>
30 public TrieNode()
31 {
32 childNodes = new TrieNode[26];
33 freq = 0;
34 }
35 }
36 #endregion
2: 添加操作
既然是26叉树，那么当前节点的后续子节点是放在当前节点的哪一叉中，也就是放在childNodes中哪一个位置，这里我们采用
int k = word[0] - 'a'来计算位置。
1 /// <summary>
2 /// 插入操作
3 /// </summary>
4 /// <param name="root"></param>
5 /// <param name="s"></param>
6 public void AddTrieNode(ref TrieNode root, string word, int id)
7 {
8 if (word.Length == 0)
9 return;
10
11 //求字符地址，方便将该字符放入到26叉树中的哪一叉中
12 int k = word[0] - 'a';
13
14 //如果该叉树为空，则初始化
15 if (root.childNodes[k] == null)
16 {
17 root.childNodes[k] = new TrieNode();
18
19 //记录下字符
20 root.childNodes[k].nodeChar = word[0];
21 }
22
23 //该id途径的节点
24 root.childNodes[k].hashSet.Add(id);
25
26 var nextWord = word.Substring(1);
27
28 //说明是最后一个字符，统计该词出现的次数
29 if (nextWord.Length == 0)
30 root.childNodes[k].freq++;
31
32 AddTrieNode(ref root.childNodes[k], nextWord, id);
33 }
34 #endregion
3：删除操作
删除操作中，我们不仅要删除该节点的字符串编号，还要对词频减一操作。
/// <summary>
/// 删除操作
/// </summary>
/// <param name="root"></param>
/// <param name="newWord"></param>
/// <param name="oldWord"></param>
/// <param name="id"></param>
public void DeleteTrieNode(ref TrieNode root, string word, int id)
{
if (word.Length == 0)
return;
//求字符地址，方便将该字符放入到26叉树种的哪一颗树中
int k = word[0] - 'a';
//如果该叉树为空,则说明没有找到要删除的点
if (root.childNodes[k] == null)
return;
var nextWord = word.Substring(1);
//如果是最后一个单词，则减去词频
if (word.Length == 0 && root.childNodes[k].freq > 0)
root.childNodes[k].freq--;
//删除途经节点
root.childNodes[k].hashSet.Remove(id);
DeleteTrieNode(ref root.childNodes[k], nextWord, id);
}
4：测试
这里我从网上下载了一套的词汇表，共2279条词汇，现在我们要做的就是检索“go”开头的词汇，并统计go出现的频率。
1 public static void Main()
2 {
3 Trie trie = new Trie();
4
5 var file = File.ReadAllLines(Environment.CurrentDirectory + "//1.txt");
6
7 foreach (var item in file)
8 {
9 var sp = item.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
10
11 trie.AddTrieNode(sp.LastOrDefault().ToLower(), Convert.ToInt32(sp[0]));
12 }
13
14 Stopwatch watch = Stopwatch.StartNew();
15
16 //检索go开头的字符串
17 var hashSet = trie.SearchTrie("go");
18
19 foreach (var item in hashSet)
20 {
21 Console.WriteLine("当前字符串的编号ID为:{0}", item);
22 }
23
24 watch.Stop();
25
26 Console.WriteLine("耗费时间:{0}", watch.ElapsedMilliseconds);
27
28 Console.WriteLine("\n\ngo 出现的次数为:{0}\n\n", trie.WordCount("go"));
29 }
下面我们拿着ID到txt中去找一找，嘿嘿，是不是很有意思。
测试文件：1.txt
完整代码：
View Code
1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Text;
5 using System.Diagnostics;
6 using System.Threading;
7 using System.IO;
8
9 namespace ConsoleApplication2
10 {
11 public class Program
12 {
13 public static void Main()
14 {
15 Trie trie = new Trie();
16
17 var file = File.ReadAllLines(Environment.CurrentDirectory + "//1.txt");
18
19 foreach (var item in file)
20 {
21 var sp = item.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
22
23 trie.AddTrieNode(sp.LastOrDefault().ToLower(), Convert.ToInt32(sp[0]));
24 }
25
26 Stopwatch watch = Stopwatch.StartNew();
27
28 //检索go开头的字符串
29 var hashSet = trie.SearchTrie("go");
30
31 foreach (var item in hashSet)
32 {
33 Console.WriteLine("当前字符串的编号ID为:{0}", item);
34 }
35
36 watch.Stop();
37
38 Console.WriteLine("耗费时间:{0}", watch.ElapsedMilliseconds);
39
40 Console.WriteLine("\n\ngo 出现的次数为:{0}\n\n", trie.WordCount("go"));
41 }
42 }
43
44 public class Trie
45 {
46 public TrieNode trieNode = new TrieNode();
47
48 #region Trie树节点
49 /// <summary>
50 /// Trie树节点
51 /// </summary>
52 public class TrieNode
53 {
54 /// <summary>
55 /// 26个字符，也就是26叉树
56 /// </summary>
57 public TrieNode[] childNodes;
58
59 /// <summary>
60 /// 词频统计
61 /// </summary>
62 public int freq;
63
64 /// <summary>
65 /// 记录该节点的字符
66 /// </summary>
67 public char nodeChar;
68
69 /// <summary>
70 /// 插入记录时的编号id
71 /// </summary>
72 public HashSet<int> hashSet = new HashSet<int>();
73
74 /// <summary>
75 /// 初始化
76 /// </summary>
77 public TrieNode()
78 {
79 childNodes = new TrieNode[26];
80 freq = 0;
81 }
82 }
83 #endregion
84
85 #region 插入操作
86 /// <summary>
87 /// 插入操作
88 /// </summary>
89 /// <param name="word"></param>
90 /// <param name="id"></param>
91 public void AddTrieNode(string word, int id)
92 {
93 AddTrieNode(ref trieNode, word, id);
94 }
95
96 /// <summary>
97 /// 插入操作
98 /// </summary>
99 /// <param name="root"></param>
100 /// <param name="s"></param>
101 public void AddTrieNode(ref TrieNode root, string word, int id)
102 {
103 if (word.Length == 0)
104 return;
105
106 //求字符地址，方便将该字符放入到26叉树中的哪一叉中
107 int k = word[0] - 'a';
108
109 //如果该叉树为空，则初始化
110 if (root.childNodes[k] == null)
111 {
112 root.childNodes[k] = new TrieNode();
113
114 //记录下字符
115 root.childNodes[k].nodeChar = word[0];
116 }
117
118 //该id途径的节点
119 root.childNodes[k].hashSet.Add(id);
120
121 var nextWord = word.Substring(1);
122
123 //说明是最后一个字符，统计该词出现的次数
124 if (nextWord.Length == 0)
125 root.childNodes[k].freq++;
126
127 AddTrieNode(ref root.childNodes[k], nextWord, id);
128 }
129 #endregion
130
131 #region 检索操作
132 /// <summary>
133 /// 检索单词的前缀,返回改前缀的Hash集合
134 /// </summary>
135 /// <param name="s"></param>
136 /// <returns></returns>
137 public HashSet<int> SearchTrie(string s)
138 {
139 HashSet<int> hashSet = new HashSet<int>();
140
141 return SearchTrie(ref trieNode, s, ref hashSet);
142 }
143
144 /// <summary>
145 /// 检索单词的前缀,返回改前缀的Hash集合
146 /// </summary>
147 /// <param name="root"></param>
148 /// <param name="s"></param>
149 /// <returns></returns>
150 public HashSet<int> SearchTrie(ref TrieNode root, string word, ref HashSet<int> hashSet)
151 {
152 if (word.Length == 0)
153 return hashSet;
154
155 int k = word[0] - 'a';
156
157 var nextWord = word.Substring(1);
158
159 if (nextWord.Length == 0)
160 {
161 //采用动态规划的思想，word最后节点记录这途经的id
162 hashSet = root.childNodes[k].hashSet;
163 }
164
165 SearchTrie(ref root.childNodes[k], nextWord, ref hashSet);
166
167 return hashSet;
168 }
169 #endregion
170
171 #region 统计指定单词出现的次数
172
173 /// <summary>
174 /// 统计指定单词出现的次数
175 /// </summary>
176 /// <param name="root"></param>
177 /// <param name="word"></param>
178 /// <returns></returns>
179 public int WordCount(string word)
180 {
181 int count = 0;
182
183 WordCount(ref trieNode, word, ref count);
184
185 return count;
186 }
187
188 /// <summary>
189 /// 统计指定单词出现的次数
190 /// </summary>
191 /// <param name="root"></param>
192 /// <param name="word"></param>
193 /// <param name="hashSet"></param>
194 /// <returns></returns>
195 public void WordCount(ref TrieNode root, string word, ref int count)
196 {
197 if (word.Length == 0)
198 return;
199
200 int k = word[0] - 'a';
201
202 var nextWord = word.Substring(1);
203
204 if (nextWord.Length == 0)
205 {
206 //采用动态规划的思想，word最后节点记录这途经的id
207 count = root.childNodes[k].freq;
208 }
209
210 WordCount(ref root.childNodes[k], nextWord, ref count);
211 }
212
213 #endregion
214
215 #region 修改操作
216 /// <summary>
217 /// 修改操作
218 /// </summary>
219 /// <param name="newWord"></param>
220 /// <param name="oldWord"></param>
221 /// <param name="id"></param>
222 public void UpdateTrieNode(string newWord, string oldWord, int id)
223 {
224 UpdateTrieNode(ref trieNode, newWord, oldWord, id);
225 }
226
227 /// <summary>
228 /// 修改操作
229 /// </summary>
230 /// <param name="root"></param>
231 /// <param name="newWord"></param>
232 /// <param name="oldWord"></param>
233 /// <param name="id"></param>
234 public void UpdateTrieNode(ref TrieNode root, string newWord, string oldWord, int id)
235 {
236 //先删除
237 DeleteTrieNode(oldWord, id);
238
239 //再添加
240 AddTrieNode(newWord, id);
241 }
242 #endregion
243
244 #region 删除操作
245 /// <summary>
246 /// 删除操作
247 /// </summary>
248 /// <param name="root"></param>
249 /// <param name="newWord"></param>
250 /// <param name="oldWord"></param>
251 /// <param name="id"></param>
252 public void DeleteTrieNode(string word, int id)
253 {
254 DeleteTrieNode(ref trieNode, word, id);
255 }
256
257 /// <summary>
258 /// 删除操作
259 /// </summary>
260 /// <param name="root"></param>
261 /// <param name="newWord"></param>
262 /// <param name="oldWord"></param>
263 /// <param name="id"></param>
264 public void DeleteTrieNode(ref TrieNode root, string word, int id)
265 {
266 if (word.Length == 0)
267 return;
268
269 //求字符地址，方便将该字符放入到26叉树种的哪一颗树中
270 int k = word[0] - 'a';
271
272 //如果该叉树为空,则说明没有找到要删除的点
273 if (root.childNodes[k] == null)
274 return;
275
276 var nextWord = word.Substring(1);
277
278 //如果是最后一个单词，则减去词频
279 if (word.Length == 0 && root.childNodes[k].freq > 0)
280 root.childNodes[k].freq--;
281
282 //删除途经节点
283 root.childNodes[k].hashSet.Remove(id);
284
285 DeleteTrieNode(ref root.childNodes[k], nextWord, id);
286 }
287 #endregion
288 }
289 }
时间： 2024-02-25 06:11:07