场景：现在有一个错词库，维护的是错词和正确词对应关系。比如：错词“我门”对应的正确词“我们”。然后在用户输入的文字进行错词校验，需要判断输入的文字是否有错词，并找出错词以便提醒用户，并且可以显示出正确词以便用户确认，如果是错词就进行替换。
首先想到的就是取出错词List放在内存中，当用户输入完成后用错词List来foreach每个错词，然后查找输入的字符串中是否包含错词。这是一种有效的方法，并且能够实现。问题是错词的数量比较多，目前有10多万条，将来也会不断更新扩展。所以pass了这种方案，为了让错词查找提高速度就用了字典树来存储错词。
字典树
Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较。
Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
通常字典树的查询时间复杂度是O(logL)，L是字符串的长度。所以效率还是比较高的。而我们上面说的foreach循环则时间复杂度为O(n)，根据时间复杂度来看，字典树效率应该是可行方案。
字典树原理
根节点不包含字符，除根节点外每一个节点都只包含一个字符； 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串； 每个节点的所有子节点包含的字符都不相同。
比如现在有错词：“我门”、“旱睡”、“旱起”。那么字典树如下图
其中红色的点就表示词结束节点，也就是从根节点往下连接成我们的词。
实现字典树：
public class Trie
{
private class Node
{
/// <summary>
/// 是否单词根节点
/// </summary>
public bool isTail = false;
public Dictionary<char, Node> nextNode;
public Node(bool isTail)
{
this.isTail = isTail;
this.nextNode = new Dictionary<char, Node>();
}
public Node() : this(false)
{
}
}
/// <summary>
/// 根节点
/// </summary>
private Node rootNode;
private int size;
private int maxLength;
public Trie()
{
this.rootNode = new Node();
this.size = 0;
this.maxLength = 0;
}
/// <summary>
/// 字典树中存储的单词的最大长度
/// </summary>
/// <returns></returns>
public int MaxLength()
{
return maxLength;
}
/// <summary>
/// 字典树中存储的单词数量
/// </summary>
public int Size()
{
return size;
}
/// <summary>
/// 获取字典树中所有的词
/// </summary>
public List<string> GetWordList()
{
return GetStrList(this.rootNode);
}
private List<string> GetStrList(Node node)
{
List<string> wordList = new List<string>();
foreach (char nextChar in node.nextNode.Keys)
{
string firstWord = Convert.ToString(nextChar);
Node childNode = node.nextNode[nextChar];
if (childNode == null || childNode.nextNode.Count == 0)
{
wordList.Add(firstWord);
}
else
{
if (childNode.isTail)
{
wordList.Add(firstWord);
}
List<string> subWordList = GetStrList(childNode);
foreach (string subWord in subWordList)
{
wordList.Add(firstWord + subWord);
}
}
}
return wordList;
}
/// <summary>
/// 向字典中添加新的单词
/// </summary>
/// <param name="word"></param>
public void Add(string word)
{
//从根节点开始
Node cur = this.rootNode;
//循环遍历单词
foreach (char c in word.ToCharArray())
{
//如果字典树节点中没有这个字母，则添加
if (!cur.nextNode.ContainsKey(c))
{
cur.nextNode.Add(c, new Node());
}
cur = cur.nextNode[c];
}
cur.isTail = true;
if (word.Length > this.maxLength)
{
this.maxLength = word.Length;
}
size++;
}
/// <summary>
/// 查询字典中某单词是否存在
/// </summary>
/// <param name="word"></param>
/// <returns></returns>
public bool Contains(string word)
{
return Match(rootNode, word);
}
/// <summary>
/// 查找匹配
/// </summary>
/// <param name="node"></param>
/// <param name="word"></param>
/// <returns></returns>
private bool Match(Node node, string word)
{
if (word.Length == 0)
{
if (node.isTail)
{
return true;
}
else
{
return false;
}
}
else
{
char firstChar = word.ElementAt(0);
if (!node.nextNode.ContainsKey(firstChar))
{
return false;
}
else
{
Node childNode = node.nextNode[firstChar];
return Match(childNode, word.Substring(1, word.Length - 1));
}
}
}
}
