首页 > 代码库 > 6天通吃树结构—— 第五天 Trie树
6天通吃树结构—— 第五天 Trie树
原文:6天通吃树结构—— 第五天 Trie树
View Code
很有段时间没写此系列了，今天我们来说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 /// 插入记录时的编码id24 /// </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 #endregion130 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最后节点记录这途经的id162 hashSet = root.childNodes[k].hashSet;163 }164 165 SearchTrie(ref root.childNodes[k], nextWord, ref hashSet);166 167 return hashSet;168 }169 #endregion170 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最后节点记录这途经的id207 count = root.childNodes[k].freq;208 }209 210 WordCount(ref root.childNodes[k], nextWord, ref count);211 }212 213 #endregion214 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 #endregion243 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 #endregion288 }289 }
6天通吃树结构—— 第五天 Trie树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。