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 TrieNode6 {7 /// <summary>8 /// 26个字符，也就是26叉树9 /// </summary>10 public TrieNode[] childNodes;1112 /// <summary>13 /// 词频统计14 /// </summary>15 public int freq;1617 /// <summary>18 /// 记录该节点的字符19 /// </summary>20 public char nodeChar;2122 /// <summary>23 /// 插入记录时的编码id24 /// </summary>25 public HashSet<int> hashSet = new HashSet<int>();2627 /// <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;1011 //求字符地址，方便将该字符放入到26叉树中的哪一叉中12 int k = word[0] - 'a';1314 //如果该叉树为空，则初始化15 if (root.childNodes[k] == null)16 {17 root.childNodes[k] = new TrieNode();1819 //记录下字符20 root.childNodes[k].nodeChar = word[0];21 }2223 //该id途径的节点24 root.childNodes[k].hashSet.Add(id);2526 var nextWord = word.Substring(1);2728 //说明是最后一个字符，统计该词出现的次数29 if (nextWord.Length == 0)30 root.childNodes[k].freq++;3132 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();45 var file = File.ReadAllLines(Environment.CurrentDirectory + "//1.txt");67 foreach (var item in file)8 {9 var sp = item.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);1011 trie.AddTrieNode(sp.LastOrDefault().ToLower(), Convert.ToInt32(sp[0]));12 }1314 Stopwatch watch = Stopwatch.StartNew();1516 //检索go开头的字符串17 var hashSet = trie.SearchTrie("go");1819 foreach (var item in hashSet)20 {21 Console.WriteLine("当前字符串的编号ID为:{0}", item);22 }2324 watch.Stop();2526 Console.WriteLine("耗费时间:{0}", watch.ElapsedMilliseconds);2728 Console.WriteLine("\n\ngo 出现的次数为:{0}\n\n", trie.WordCount("go"));29 }
下面我们拿着ID到txt中去找一找，嘿嘿，是不是很有意思。
测试文件：1.txt
完整代码：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Threading;
using System.IO;
namespace ConsoleApplication2
{
public class Program
{
public static void Main()
{
Trie trie = new Trie();
var file = File.ReadAllLines(Environment.CurrentDirectory + “//1.txt”);
foreach (var item in file)
{
var sp = item.Split(new char[] { ‘ ‘ }, StringSplitOptions.RemoveEmptyEntries);
trie.AddTrieNode(sp.LastOrDefault().ToLower(), Convert.ToInt32(sp[0]));
}
Stopwatch watch = Stopwatch.StartNew();
//检索go开头的字符串
var hashSet = trie.SearchTrie(“go”);
foreach (var item in hashSet)
{
Console.WriteLine(“当前字符串的编号ID为:{0}“, item);
}
watch.Stop();
Console.WriteLine(“耗费时间:{0}“, watch.ElapsedMilliseconds);
Console.WriteLine(“\n\ngo 出现的次数为:{0}\n\n”, trie.WordCount(“go”));
}
}
public class Trie
{
public TrieNode trieNode = new TrieNode();
#region Trie树节点
///
/// Trie树节点
///
public class TrieNode
{
///
/// 26个字符，也就是26叉树
///
public TrieNode[] childNodes;
///
/// 词频统计
///
public int freq;
///
/// 记录该节点的字符
///
public char nodeChar;
///
/// 插入记录时的编号id
///
public HashSet
///
/// 初始化
///
public TrieNode()
{
childNodes = new TrieNode[26];
freq = 0;
}
}
#endregion
#region 插入操作
///
/// 插入操作
///
///
///
public void AddTrieNode(string word, int id)
{
AddTrieNode(ref trieNode, word, id);
}
///
/// 插入操作
///
///
///
public void AddTrieNode(ref TrieNode root, string word, int id)
{
if (word.Length == 0)
return;
//求字符地址，方便将该字符放入到26叉树中的哪一叉中
int k = word[0] - ‘a’;
//如果该叉树为空，则初始化
if (root.childNodes[k] == null)
{
root.childNodes[k] = new TrieNode();
//记录下字符
root.childNodes[k].nodeChar = word[0];
}
//该id途径的节点
root.childNodes[k].hashSet.Add(id);
var nextWord = word.Substring(1);
//说明是最后一个字符，统计该词出现的次数
if (nextWord.Length == 0)
root.childNodes[k].freq++;
AddTrieNode(ref root.childNodes[k], nextWord, id);
}
#endregion
#region 检索操作
///
/// 检索单词的前缀,返回改前缀的Hash集合
///
///
///
public HashSet
{
HashSet
return SearchTrie(ref trieNode, s, ref hashSet);
}
///
/// 检索单词的前缀,返回改前缀的Hash集合
///
///
///
///
public HashSet
{
if (word.Length == 0)
return hashSet;
int k = word[0] - ‘a’;
var nextWord = word.Substring(1);
if (nextWord.Length == 0)
{
//采用动态规划的思想，word最后节点记录这途经的id
hashSet = root.childNodes[k].hashSet;
}
SearchTrie(ref root.childNodes[k], nextWord, ref hashSet);
return hashSet;
}
#endregion
#region 统计指定单词出现的次数
///
/// 统计指定单词出现的次数
///
///
///
///
public int WordCount(string word)
{
int count = 0;
WordCount(ref trieNode, word, ref count);
return count;
}
///
/// 统计指定单词出现的次数
///
///
///
///
///
public void WordCount(ref TrieNode root, string word, ref int count)
{
if (word.Length == 0)
return;
int k = word[0] - ‘a’;
var nextWord = word.Substring(1);
if (nextWord.Length == 0)
{
//采用动态规划的思想，word最后节点记录这途经的id
count = root.childNodes[k].freq;
}
WordCount(ref root.childNodes[k], nextWord, ref count);
}
#endregion
#region 修改操作
///
/// 修改操作
///
///
///
///
public void UpdateTrieNode(string newWord, string oldWord, int id)
{
UpdateTrieNode(ref trieNode, newWord, oldWord, id);
}
///
/// 修改操作
///
///
///
///
///
public void UpdateTrieNode(ref TrieNode root, string newWord, string oldWord, int id)
{
//先删除
DeleteTrieNode(oldWord, id);
//再添加
AddTrieNode(newWord, id);
}
#endregion
#region 删除操作
///
/// 删除操作
///
///
///
///
///
public void DeleteTrieNode(string word, int id)
{
DeleteTrieNode(ref trieNode, word, id);
}
///
/// 删除操作
///
///
///
///
///
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);
}
#endregion
}
}
àì夳堔傛蜴生んèń
╰半夏微凉°
灰太狼
还没有评论，来说两句吧...