場景：現在有一個錯詞庫，維護的是錯詞和正确詞對應關系。比如：錯詞“我門”對應的正确詞“我們”。然後在使用者輸入的文字進行錯詞校驗，需要判斷輸入的文字是否有錯詞，并找出錯詞以便提醒使用者，并且可以顯示出正确詞以便使用者确認，如果是錯詞就進行替換。
首先想到的就是取出錯詞List放在記憶體中，當使用者輸入完成後用錯詞List來foreach每個錯詞，然後查找輸入的字元串中是否包含錯詞。這是一種有效的方法，并且能夠實作。問題是錯詞的數量比較多，目前有10多萬條，将來也會不斷更新擴充。是以pass了這種方案，為了讓錯詞查找提高速度就用了字典樹來存儲錯詞。
字典樹
Trie樹，即字典樹，又稱單詞查找樹或鍵樹，是一種樹形結構，是一種哈希樹的變種。典型應用是用于統計和排序大量的字元串（但不僅限于字元串），是以經常被搜尋引擎系統用于文本詞頻統計。它的優點是：最大限度地減少無謂的字元串比較。
Trie的核心思想是空間換時間。利用字元串的公共字首來降低查詢時間的開銷以達到提高效率的目的。
通常字典樹的查詢時間複雜度是O(logL)，L是字元串的長度。是以效率還是比較高的。而我們上面說的foreach循環則時間複雜度為O(n)，根據時間複雜度來看，字典樹效率應該是可行方案。
字典樹原理
根節點不包含字元，除根節點外每一個節點都隻包含一個字元； 從根節點到某一節點，路徑上經過的字元連接配接起來，為該節點對應的字元串； 每個節點的所有子節點包含的字元都不相同。
比如現在有錯詞：“我門”、“旱睡”、“旱起”。那麼字典樹如下圖
其中紅色的點就表示詞結束節點，也就是從根節點往下連接配接成我們的詞。
實作字典樹：
1 public class Trie
2 {
3 private class Node
4 {
5 /// <summary>
6 /// 是否單詞根節點
7 /// </summary>
8 public bool isTail = false;
9
10 public Dictionary<char, Node> nextNode;
11
12 public Node(bool isTail)
13 {
14 this.isTail = isTail;
15 this.nextNode = new Dictionary<char, Node>();
16 }
17 public Node() : this(false)
18 {
19 }
20 }
21
22 /// <summary>
23 /// 根節點
24 /// </summary>
25 private Node rootNode;
26 private int size;
27 private int maxLength;
28
29 public Trie()
30 {
31 this.rootNode = new Node();
32 this.size = 0;
33 this.maxLength = 0;
34 }
35
36 /// <summary>
37 /// 字典樹中存儲的單詞的最大長度
38 /// </summary>
39 /// <returns></returns>
40 public int MaxLength()
41 {
42 return maxLength;
43 }
44
45 /// <summary>
46 /// 字典樹中存儲的單詞數量
47 /// </summary>
48 public int Size()
49 {
50 return size;
51 }
52
53 /// <summary>
54 /// 擷取字典樹中所有的詞
55 /// </summary>
56 public List<string> GetWordList()
57 {
58 return GetStrList(this.rootNode);
59 }
60
61 private List<string> GetStrList(Node node)
62 {
63 List<string> wordList = new List<string>();
64
65 foreach (char nextChar in node.nextNode.Keys)
66 {
67 string firstWord = Convert.ToString(nextChar);
68 Node childNode = node.nextNode[nextChar];
69
70 if (childNode == null || childNode.nextNode.Count == 0)
71 {
72 wordList.Add(firstWord);
73 }
74 else
75 {
76
77 if (childNode.isTail)
78 {
79 wordList.Add(firstWord);
80 }
81
82 List<string> subWordList = GetStrList(childNode);
83 foreach (string subWord in subWordList)
84 {
85 wordList.Add(firstWord + subWord);
86 }
87 }
88 }
89
90 return wordList;
91 }
92
93 /// <summary>
94 /// 向字典中添加新的單詞
95 /// </summary>
96 /// <param name="word"></param>
97 public void Add(string word)
98 {
99 //從根節點開始
100 Node cur = this.rootNode;
101 //循環周遊單詞
102 foreach (char c in word.ToCharArray())
103 {
104 //如果字典樹節點中沒有這個字母，則添加
105 if (!cur.nextNode.ContainsKey(c))
106 {
107 cur.nextNode.Add(c, new Node());
108 }
109 cur = cur.nextNode[c];
110 }
111 cur.isTail = true;
112
113 if (word.Length > this.maxLength)
114 {
115 this.maxLength = word.Length;
116 }
117 size++;
118 }
119
120 /// <summary>
121 /// 查詢字典中某單詞是否存在
122 /// </summary>
123 /// <param name="word"></param>
124 /// <returns></returns>
125 public bool Contains(string word)
126 {
127 return Match(rootNode, word);
128 }
129
130 /// <summary>
131 /// 查找比對
132 /// </summary>
133 /// <param name="node"></param>
134 /// <param name="word"></param>
135 /// <returns></returns>
136 private bool Match(Node node, string word)
137 {
138 if (word.Length == 0)
139 {
140 if (node.isTail)
141 {
142 return true;
143 }
144 else
145 {
146 return false;
147 }
148 }
149 else
150 {
151 char firstChar = word.ElementAt(0);
152 if (!node.nextNode.ContainsKey(firstChar))
153 {
154 return false;
155 }
156 else
157 {
158 Node childNode = node.nextNode[firstChar];
159 return Match(childNode, word.Substring(1, word.Length - 1));
160 }
161 }
162 }
163 } 複制
測試下：
現在我們有了字典樹，然後就不能以字典樹來foreach，字典樹用于檢索。我們就以使用者輸入的字元串為資料源，去字典樹種查找是否存在錯詞。是以需要對輸入字元串進行取詞檢索。也就是分詞，分詞我們采用前向最大比對。
前向最大比對
我們分詞的目的是将輸入字元串分成若幹個詞語，前向最大比對就是從前向後尋找在詞典中存在的詞。
例子：我們假設maxLength= 3,即假設單詞的最大長度為3。實際上我們應該以字典樹中的最大單詞長度，作為最大長度來分詞（上面我們的字典最大長度應該是2）。這樣效率更高，為了示範比對過程就假設maxLength為3，這樣示範的更清楚。
用前向最大比對來劃分“我們應該早睡早起” 這句話。因為我是錯詞比對，是以這句話我改成“我門應該旱睡旱起”。
第一次：取子串 “我門應”，正向取詞，如果比對失敗，每次去掉比對字段最後面的一個字。
“我門應”，掃描詞典中單詞，沒有比對，子串長度減 1 變為“我門”。
“我門”，掃描詞典中的單詞，比對成功，得到“我門”錯詞，輸入變為“應該旱”。
第二次：取子串“應該旱”
“應該旱”，掃描詞典中單詞，沒有比對，子串長度減 1 變為“應該”。
“應該”，掃描詞典中的單詞，沒有比對，輸入變為“應”。
“應”，掃描詞典中的單詞，沒有比對，輸入變為“該旱睡”。
第三次：取子串“該旱睡”
“該旱睡”，掃描詞典中單詞，沒有比對，子串長度減 1 變為“該旱”。
“該旱”，掃描詞典中的單詞，沒有比對，輸入變為“該”。
“該”，掃描詞典中的單詞，沒有比對，輸入變為“旱睡旱”。
第四次：取子串“旱睡旱”
“旱睡旱”，掃描詞典中單詞，沒有比對，子串長度減 1 變為“旱睡”。
“旱睡”，掃描詞典中的單詞，比對成功，得到“旱睡”錯詞，輸入變為“早起”。
以此類推，我們得到錯詞 我們/旱睡/旱起。
因為我是結合字典樹比對錯詞是以一個字也可能是錯字，則比對到單個字，如果隻是分詞則上面的到一個字的時候就應該停止分詞了，直接字元串長度減1。
這種比對方式還有後向最大比對以及雙向比對，這個大家可以去了解下。
實作前向最大比對，這裡後向最大比對也可以一起實作。
1 public class ErrorWordMatch
2 {
3 private static ErrorWordMatch singleton = new ErrorWordMatch();
4 private static Trie trie = new Trie();
5 private ErrorWordMatch()
6 {
7
8 }
9
10 public static ErrorWordMatch Singleton()
11 {
12 return singleton;
13 }
14
15 public void LoadTrieData(List<string> errorWords)
16 {
17 foreach (var errorWord in errorWords)
18 {
19 trie.Add(errorWord);
20 }
21 }
22
23 /// <summary>
24 /// 最大 正向/逆向 比對錯詞
25 /// </summary>
26 /// <param name="inputStr">需要比對錯詞的字元串</param>
27 /// <param name="leftToRight">true為從左到右分詞，false為從右到左分詞</param>
28 /// <returns>比對到的錯詞</returns>
29 public List<string> MatchErrorWord(string inputStr, bool leftToRight)
30 {
31 if (string.IsNullOrWhiteSpace(inputStr))
32 return null;
33 if (trie.Size() == 0)
34 {
35 throw new ArgumentException("字典樹沒有資料,請先調用 LoadTrieData 方法裝載字典樹");
36 }
37 //取詞的最大長度
38 int maxLength = trie.MaxLength();
39 //取詞的目前長度
40 int wordLength = maxLength;
41 //分詞操作中，處于字元串中的目前位置
42 int position = 0;
43 //分詞操作中，已經處理的字元串總長度
44 int segLength = 0;
45 //用于嘗試分詞的取詞字元串
46 string word = "";
47
48 //用于儲存正向分詞的字元串數組
49 List<string> segWords = new List<string>();
50 //用于儲存逆向分詞的字元串數組
51 List<string> segWordsReverse = new List<string>();
52
53 //開始分詞，循環以下操作，直到全部完成
54 while (segLength < inputStr.Length)
55 {
56 //如果剩餘沒分詞的字元串長度<取詞的最大長度，則取詞長度等于剩餘未分詞長度
57 if ((inputStr.Length - segLength) < maxLength)
58 wordLength = inputStr.Length - segLength;
59 //否則，按最大長度處理
60 else
61 wordLength = maxLength;
62
63 //從左到右 和 從右到左截取時，起始位置不同
64 //剛開始，截取位置是字元串兩頭，随着不斷循環分詞，截取位置會不斷推進
65 if (leftToRight)
66 position = segLength;
67 else
68 position = inputStr.Length - segLength - wordLength;
69
70 //按照指定長度，從字元串截取一個詞
71 word = inputStr.Substring(position, wordLength);
72
73
74 //在字典中查找，是否存在這樣一個詞
75 //如果不包含，就減少一個字元，再次在字典中查找
76 //如此循環，直到隻剩下一個字為止
77 while (!trie.Contains(word))
78 {
79 //如果最後一個字都沒有比對，則把word設定為空，用來表示沒有比對項(如果是分詞直接break)
80 if (word.Length == 1)
81 {
82 word = null;
83 break;
84 }
85
86 //把截取的字元串，最邊上的一個字去掉
87 //從左到右 和 從右到左時，截掉的字元的位置不同
88 if (leftToRight)
89 word = word.Substring(0, word.Length - 1);
90 else
91 word = word.Substring(1);
92 }
93
94 //将分出比對上的詞，加入到分詞字元串數組中，正向和逆向不同
95 if (word != null)
96 {
97 if (leftToRight)
98 segWords.Add(word);
99 else
100 segWordsReverse.Add(word);
101 //已經完成分詞的字元串長度，要相應增加
102 segLength += word.Length;
103 }
104 else
105 {
106 //沒比對上的則+1，丢掉一個字（如果是分詞 則不用判斷word是否為空，單個字也傳回）
107 segLength += 1;
108 }
109 }
110
111 //如果是逆向分詞，對分詞結果反轉排序
112 if (!leftToRight)
113 {
114 for (int i = segWordsReverse.Count - 1; i >= 0; i--)
115 {
116 //将反轉的結果，儲存在正向分詞數組中 以便最後return 同一個變量segWords
117 segWords.Add(segWordsReverse[i]);
118 }
119 }
120
121 return segWords;
122 }
123 } 複制
這裡使用了單例模式用來在項目中共用，在第一次裝入了字典樹後就可以在其他地方比對錯詞使用了。
這個是結合我具體使用，簡化了些代碼，如果隻是分詞的話就是分詞那個實作方法就行了。最後分享就到這裡吧，如有不對之處，請加以指正。