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 }
浙公網安備 33010602011771號