Trie樹和Ternary Search樹的學習總結
1.1.1 摘要 Trie樹，又稱字典樹，單詞查找樹或者前綴樹，是一種用于快速檢索的多叉樹結構，如英文字母的字典樹是一個26叉樹，數字的字典樹是一個10叉樹。三叉搜索樹是一種特殊的Trie樹的數據結構，它是數字搜索樹和二叉搜索樹的混合體。它既有數字搜索樹效率優點，又有二叉搜索樹空間優點.....
1.1.1 摘要
Trie樹，又稱字典樹，單詞查找樹或者前綴樹，是一種用于快速檢索的多叉樹結構，如英文字母的字典樹是一個26叉樹，數字的字典樹是一個10叉樹。
三叉搜索樹是一種特殊的Trie樹的數據結構，它是數字搜索樹和二叉搜索樹的混合體。它既有數字搜索樹效率優點，又有二叉搜索樹空間優點。
在接下來的博文中，我們將介紹Trie樹和三叉搜索樹的定義，實現和優缺點。
本文目錄
1.1.2 正文
Trie樹的定義
Trie樹與二叉搜索樹不同，鍵不是直接保存在節點中，而是由節點在樹中的位置決定。一個節點的所有子孫都有相同的前綴（prefix），也就是這個節點對應的字符串，而根節點對應空字符串。一般情況下，不是所有的節點都有對應的值，只有葉子節點和部分內部節點所對應的鍵才有相關的值。
Trie樹可以利用字符串的公共前綴來節約存儲空間，如下圖所示，該Trie樹用11個節點保存了8個字符串tea，ted，ten，to，A，i，in，inn。
圖1Trie樹（圖片源于wiki）
我們注意到Trie樹中，字符串tea，ted和ten的相同的前綴（prefix）為“te”，如果我們要存儲的字符串大部分都具有相同的前綴（prefix），那么該Trie樹結構可以節省大量內存空間，因為Trie樹中每個單詞都是通過character by character方法進行存儲，所以具有相同前綴單詞是共享前綴節點的。
當然，如果Trie樹中存在大量字符串，并且這些字符串基本上沒有公共前綴，那么相應的Trie樹將非常消耗內存空間，Trie的缺點是空指針耗費內存空間。
Trie樹的基本性質可以歸納為：
（1）根節點不包含字符，除根節點外的每個節點只包含一個字符。
（2）從根節點到某一個節點，路徑上經過的字符連接起來，為該節點對應的字符串。
（3）每個節點的所有子節點包含的字符串不相同。
Trie樹的實現
Trie樹是一種形似樹的數據結構，它的每個節點都包含一個指針數組，假設，我們要構建一個26個字母的Trie樹，那么每一個指針對應著字母表里的一個字母。從根節點開始，我們只要依次找到目標單詞里下一個字母對應的指針，就可以一步步查找目標了。假設，我們要把字符串AB，ABBA，ABCD和BCD插入到Trie樹中，由于Trie樹的根節點不保存任何字母，我們從根節點的直接后繼開始保存字母。如下圖所示，我們在Trie樹的第二層中保存了字母A和B，第三層中保存了B和C，其中B被標記為深藍色表示單詞AB已經插入完成。
圖2 Trie樹的實現
我們發現由于Trie的每個節點都有一個長度為26指針數組，但我們知道并不是每個指針數組都保存記錄，空的指針數組導致內存空間的浪費。
假設，我們要設計一個翻譯軟件，翻譯軟件少不了查詞功能，而且當用戶輸入要查詢的詞匯時，軟件會提示相似單詞，讓用戶選擇要查詢的詞匯，這樣用戶就無需輸入完整詞匯就能進行查詢，而且用戶體驗更好。
我們將使用Trie樹結構存儲和檢索單詞，從而實現詞匯的智能提示功能，這里我們只考慮26英文字母匹配的實現，所以我們將構建一棵26叉樹。
由于每個節點下一層都包含26個節點，那么我們在節點類中添加節點屬性，節點類的具體實現如下：
/// <summary> /// The node type. /// Indicates the word completed or not. /// </summary> public enum NodeType { COMPLETED, UNCOMPLETED }; /// <summary> /// The tree node. /// </summary> public class Node { const int ALPHABET_SIZE = 26; internal char Word { get; set; } internal NodeType Type { get; set; } internal Node[] Child; /// <summary> /// Initializes a new instance of the <see cref="Node"/> class. /// </summary> /// <param name="word">The word.</param> /// <param name="nodeType">Type of the node.</param> public Node(char word, NodeType nodeType) { this.Word = word; this.Type = nodeType; this.Child = new Node[ALPHABET_SIZE]; } }
上面我們定義一個枚舉類型NodeType，它用來標記詞匯是否插入完成；接著，我們定義了一個節點類型Node，它包含兩個屬性Word和Type，Word用來保存當前節點的字母，Type用來標記當前節點是否插入完成。
接下來，我們要定義Trie樹類型，并且添加Insert()，Find()和FindSimilar()方法。
/// <summary> /// The trie tree entity. /// </summary> public class Trie { const int ALPHABET_SIZE = 26; private Node _root; private HashSet<string> _hashSet; public Trie() { _root = CreateNode(' '); } public Node CreateNode(char word) { var node = new Node(word, NodeType.UNCOMPLETED); return node; } /// <summary> /// Inserts the specified node. /// </summary> /// <param name="node">The node.</param> /// <param name="word">The word need to insert.</param> private void Insert(ref Node node, string word) { Node temp = node; foreach (char t in word) { if (null == temp.Child[this.CharToIndex(t)]) { temp.Child[this.CharToIndex(t)] = this.CreateNode(t); } temp = temp.Child[this.CharToIndex(t)]; } temp.Type = NodeType.COMPLETED; } /// <summary> /// Inserts the specified word. /// </summary> /// <param name="word">Retrieval word.</param> public void Insert(string word) { if (string.IsNullOrEmpty(word)) { throw new ArgumentException("word"); } Insert(ref _root, word); } /// <summary> /// Finds the specified word. /// </summary> /// <param name="word">Retrieval word.</param> /// <returns>The tree node.</returns> public Node Find(string word) { if (string.IsNullOrEmpty(word)) { throw new ArgumentException("word"); } int i = 0; Node temp = _root; var words = new HashSet<string>(); while (i < word.Length) { if (null == temp.Child[this.CharToIndex(word[i])]) { return null; } temp = temp.Child[this.CharToIndex(word[i++])]; } if (temp != null && NodeType.COMPLETED == temp.Type) { _hashSet = new HashSet<string> { word }; return temp; } return null; } /// <summary> /// Finds the simlar word. /// </summary> /// <param name="word">The words have same prefix.</param> /// <returns>The collection of similar words.</returns> public HashSet<string> FindSimilar(string word) { Node node = Find(word); DFS(word, node); return _hashSet; } /// <summary> /// DFSs the specified prefix. /// </summary> /// <param name="prefix">Retrieval prefix.</param> /// <param name="node">The node.</param> private void DFS(string prefix, Node node) { for (int i = 0; i < ALPHABET_SIZE; i++) { if (node.Child[i] != null) { DFS(prefix + node.Child[i].Word, node.Child[i]); if (NodeType.COMPLETED == node.Child[i].Type) { _hashSet.Add(prefix + node.Child[i].Word); } } } } /// <summary> /// Converts char to index. /// </summary> /// <param name="ch">The char need to convert.</param> /// <returns>The index.</returns> private int CharToIndex(char ch) { return ch - 'a'; } }
上面我們，定義了Trie樹類，它包含兩個字段分別是：_root和_hashSet，_root用來保存Trie樹的根節點，我們使用_hashSet保存前綴匹配的所有單詞。
接著，我們在Trie樹類中定義了CreateNode()，Insert()，Find()，FindSimilar()和DFS()等方法。
CreateNode()方法用來創建樹的節點，Insert()方法把節點插入樹中，Find()和FindSimilar()方法用來查找指定單詞，DFS()方法是查找單詞的具體實現，它通過深度搜索的方法遍歷節點查找匹配的單詞，最后把匹配的單詞保存到_hashSet中。
接下來，我們創建一棵Trie樹，然后把兩千個英語單詞插入到Trie樹中，最后我們查找前綴為“the”的所有單詞包括前綴本身。
public class Program { public static void Main() { // Creates a file object. var file = File.ReadAllLines(Environment.CurrentDirectory + "http://1.txt"); // Creates a trie tree object. var trie = new Trie(); foreach (var item in file) { var sp = item.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries); // Inserts word into to the tree. trie.Insert(sp.LastOrDefault().ToLower()); ////ternaryTree.Insert(sp.LastOrDefault().ToLower()); } var similarWords = trie.FindSimilar("jk"); foreach (var similarWord in similarWords) { Console.WriteLine("Similar word: {0}", similarWord); } } }
圖3 匹配詞結果
我們在1.txt文本文件中通過正則表達式（^:z the+）查找前綴為the的所有單詞，恰好就是上面8個單詞。
Ternary Tree的定義
前面，我們介紹了Trie樹結構，它的實現簡單但空間效率低。如果要支持26個英文字母，每個節點就要保存26個指針，假若我們還要支持國際字符、標點符號、區分大小寫，內存用量就會急劇上升，以至于不可行。
由于節點數組中保存的空指針占用了太多內存，我們遇到的困難與此有關，因此可以考慮改用其他數據結構去代替，比如用hash map。然而，管理成千上萬個hash map肯定也不是什么好主意，而且它使數據的相對順序信息丟失，所以我們還是去看看另一種更好解法吧——Ternary Tree。
接下來，我們將介紹三叉搜索樹，它結合字典樹的時間效率和二叉搜索樹的空間效率優點。
Ternary Tree的實現
三叉搜索樹使用了一種聰明的手段去解決Trie的內存問題（空的指針數組）。為了避免多余的指針占用內存，每個Trie節點不再用數組來表示，而是表示成“樹中有樹”。Trie節點里每個非空指針都會在三叉搜索樹里得到屬于它自己的節點。
接下來，我們將實現三叉搜索樹的節點類，具體實現如下：
/// <summary> /// The node type. /// Indicates the word completed or not. /// </summary> public enum NodeType { COMPLETED, UNCOMPLETED }; /// <summary> /// The tree node. /// </summary> public class Node { internal char Word { get; set; } internal Node LeftChild, CenterChild, RightChild; internal NodeType Type { get; set; } public Node(char ch, NodeType type) { Word = ch; Type = type; } }
由于三叉搜索樹包含三種類型的箭頭。第一種箭頭和Trie里的箭頭是一樣的，也就是圖2里畫成虛線的向下的箭頭。沿著向下箭頭行進，就意味著“匹配上”了箭頭起始端的字符。如果當前字符少于節點中的字符，會沿著節點向左查找，反之向右查找。
接下來，我們將定義Ternary Tree類型，并且添加Insert()，Find()和FindSimilar()方法。
/// <summary> /// The ternary tree. /// </summary> public class TernaryTree { private Node _root; ////private string _prefix; private HashSet<string> _hashSet; /// <summary> /// Inserts the word into the tree. /// </summary> /// <param name="s">The word need to insert.</param> /// <param name="index">The index of the word.</param> /// <param name="node">The tree node.</param> private void Insert(string s, int index, ref Node node) { if (null == node) { node = new Node(s[index], NodeType.UNCOMPLETED); } if (s[index] < node.Word) { Node leftChild = node.LeftChild; this.Insert(s, index, ref node.LeftChild); } else if (s[index] > node.Word) { Node rightChild = node.RightChild; this.Insert(s, index, ref node.RightChild); } else { if (index + 1 == s.Length) { node.Type = NodeType.COMPLETED; } else { Node centerChild = node.CenterChild; this.Insert(s, index + 1, ref node.CenterChild); } } } /// <summary> /// Inserts the word into the tree. /// </summary> /// <param name="s">The word need to insert.</param> public void Insert(string s) { if (string.IsNullOrEmpty(s)) { throw new ArgumentException("s"); } Insert(s, 0, ref _root); } /// <summary> /// Finds the specified world. /// </summary> /// <param name="s">The specified world</param> /// <returns>The corresponding tree node.</returns> public Node Find(string s) { if (string.IsNullOrEmpty(s)) { throw new ArgumentException("s"); } int pos = 0; Node node = _root; _hashSet = new HashSet<string>(); while (node != null) { if (s[pos] < node.Word) { node = node.LeftChild; } else if (s[pos] > node.Word) { node = node.RightChild; } else { if (++pos == s.Length) { _hashSet.Add(s); return node.CenterChild; } node = node.CenterChild; } } return null; } /// <summary> /// Get the world by dfs. /// </summary> /// <param name="prefix">The prefix of world.</param> /// <param name="node">The tree node.</param> private void DFS(string prefix, Node node) { if (node != null) { if (NodeType.COMPLETED == node.Type) { _hashSet.Add(prefix + node.Word); } DFS(prefix, node.LeftChild); DFS(prefix + node.Word, node.CenterChild); DFS(prefix, node.RightChild); } } /// <summary> /// Finds the similar world. /// </summary> /// <param name="s">The prefix of the world.</param> /// <returns>The world has the same prefix.</returns> public HashSet<string> FindSimilar(string s) { Node node = this.Find(s); this.DFS(s, node); return _hashSet; } }
和Trie類似，我們在TernaryTree 類中，定義了Insert()，Find()和FindSimilar()方法，它包含兩個字段分別是：_root和_hashSet，_root用來保存Trie樹的根節點，我們使用_hashSet保存前綴匹配的所有單詞。
由于三叉搜索樹每個節點只有三個叉，所以我們在進行節點插入操作時，只需判斷插入的字符與當前節點的關系（少于，等于或大于）插入到相應的節點就OK了。
我們使用之前的例子，把字符串AB，ABBA，ABCD和BCD插入到三叉搜索樹中，首先往樹中插入了字符串AB，接著我們插入字符串ABCD，由于ABCD與AB有相同的前綴AB，所以C節點都是存儲到B的CenterChild中，D存儲到C的CenterChild中；當插入ABBA時，由于ABBA與AB有相同的前綴AB，而B字符少于字符C，所以B存儲到C的LeftChild中；當插入BCD時，由于字符B大于字符A，所以B存儲到C的RightChild中。
圖4三叉搜索樹
我們注意到插入字符串的順序會影響三叉搜索樹的結構，為了取得最佳性能，字符串應該以隨機的順序插入到三叉樹搜索樹中，尤其不應該按字母順序插入，否則對應于單個Trie
節點的子樹會退化成鏈表，極大地增加查找成本。當然我們還可以采用一些方法來實現自平衡的三叉樹。
由于樹是否平衡取決于單詞的讀入順序，如果按排序后的順序插入，則該方式生成的樹是最不平衡的。單詞的讀入順序對于創建平衡的三叉搜索樹很重要，所以我們通過選擇一個排序后數據集合的中間值，并把它作為開始節點，通過不斷折半插入中間值，我們就可以創建一棵平衡的三叉樹。我們將通過方法BalancedData()實現數據折半插入，具體實現如下：
/// <summary> /// Balances the ternary tree input data. /// </summary> /// <param name="file">The file saves balanced data.</param> /// <param name="orderList">The order data list.</param> /// <param name="offSet">The offset.</param> /// <param name="len">The length of data list.</param> public void BalancedData(StreamWriter file, IList<KeyValuePair<int, string>> orderList, int offSet, int len) { if (len < 1) { return; } int midLen = len >> 1; // Write balanced data into file. file.WriteLine(orderList[midLen + offSet].Key + " " + orderList[midLen + offSet].Value); BalancedData(file, orderList, offSet, midLen); BalancedData(file, orderList, offSet + midLen + 1, len - midLen - 1); }
上面，我們定義了方法BalancedData()，它包含四個參數分別是：file，orderList，offSet和len。File寫入平衡排序后的數據到文本文件。orderList按順序排序后的數據。offSet偏移量。Len插入的數據量。
同樣我們創建一棵三叉搜索樹，然后把兩千個英語單詞插入到三叉搜索樹中，最后我們查找前綴為“ab”的所有單詞包括前綴本身。
public class Program { public static void Main() { // Creates a file object. var file = File.ReadAllLines(Environment.CurrentDirectory + "http://1.txt"); // Creates a trie tree object. var ternaryTree = new TernaryTree(); var dictionary = new Dictionary<int, string>(); foreach (var item in file) { var sp = item.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries); ternaryTree.Insert(sp.LastOrDefault().ToLower()); } Stopwatch watch = Stopwatch.StartNew(); // Gets words have the same prefix. var similarWords = ternaryTree.FindSimilar("ab"); foreach (var similarWord in similarWords) { Console.WriteLine("Similar word: {0}", similarWord); } watch.Stop(); Console.WriteLine("Time consumes: {0} ms", watch.ElapsedMilliseconds); Console.WriteLine("Similar word: {0}", similarWords.Count); Console.Read(); } }
圖5匹配結果
我們在1.txt文本文件中通過正則表達式（^:z ab+）查找前綴為ab的所有單詞，剛好就是上面9個單詞。
Ternary Tree的應用
我們使用搜索引擎進行搜索時，它會提供自動完成（Auto-complete）功能，讓用戶更加容易查找到相關的信息；假如：我們在Google中輸入ternar，它會提示與ternar的相關搜索信息。
圖6 Auto-complete功能
Google根據我們的輸入ternar，提示了ternary，ternary search tree等等搜索信息，自動完成（Auto-complete）功能的實現的核心思想三叉搜索樹。
對于Web應用程序來說，自動完成（Auto-complete）的繁重處理工作絕大部分要交給服務器去完成。很多時候，自動完成（Auto-complete）的備選項數目巨大，不適宜一下子全都下載到客戶端。相反，三叉樹搜索是保存在服務器上的，客戶端把用戶已經輸入的單詞前綴送到服務器上作查詢，然后服務器根據三叉搜索樹算法獲取相應數據列表，最后把候選的數據列表返回給客戶端。
圖7 Auto-complete功能
1.1.3 總結
Trie樹是一種非常重要的數據結構，它在信息檢索，字符串匹配等領域有廣泛的應用，同時，它也是很多算法和復雜數據結構的基礎，如后綴樹，AC自動機等；三叉搜索樹是結合了數字搜索樹的時間效率和二叉搜索樹的空間效率優點，而且它有效的避免了Trie空指針數據的空間浪費問題。
樹是否平衡取決于單詞的讀入順序。如果字符串經過排序后的順序插入，則該樹是最不平衡的，由于對應于單個Trie節點的子樹會退化成鏈表，極大地增加查找成本。
最后，祝大家新年快樂，身體健康，工作愉快和Code With Pleasant,By Jackson Huang。
參考
|
關于作者:[作者]：
JK_Rush從事.NET開發和熱衷于開源高性能系統設計，通過博文交流和分享經驗，歡迎轉載，請保留原文地址，謝謝。 |
浙公網安備 33010602011771號