數據結構與演算法：字典樹（前綴樹）

下面介紹前綴樹

Trie樹，即字典樹，又稱單詞查找樹或鍵樹，是一種樹形結構，是一種哈希樹的變種。典型應用是用於統計和排序大量的字元串（但不僅限於字元串），所以經常被搜索引擎系統用於文本詞頻統計。它的優點是：最大限度地減少無謂的字元串比較。

Trie的核心思想是空間換時間。利用字元串的公共前綴來降低查詢時間的開銷以達到提高效率的目的。

前綴樹的3個基本性質：

1. 根節點不包含字元，除根節點外每一個節點都只包含一個字元。
2. 從根節點到某一節點，路徑上經過的字元連接起來，為該節點對應的字元串。
3. 每個節點的所有子節點包含的字元都不相同。

前綴樹查詢和哈希查詢的比較（示相對情況而定）：

通常字典樹的查詢時間複雜度是O(logL)，L是字元串的長度。所以效率還是比較高的。

網上的一部分文章說的都是字典樹的效率比hash表高。我覺得還是相對來看比較好，各有個的特點吧。

hash表，通過hash函數把所有的單詞分別hash成key值，查詢的時候直接通過hash函數即可，都知道hash表的效率是非常高的為O(1)，直接說字典樹的查詢效率比hash高，難道有比O(1)還快的- -。

hash：

當然對於單詞查詢，如果我們hash函數選取的好，計算量少，且衝突少，那單詞查詢速度肯定是非常快的。那如果hash函數的計算量相對大呢，且衝突律高呢？

這些都是要考慮的因素。且hash表不支持動態查詢，什麼叫動態查詢，當我們要查詢單詞apple時，hash表必須等待用戶把單詞apple輸入完畢才能hash查詢。

當你輸入到appl時肯定不可能hash吧。

字典樹（tries樹）：

對於單詞查詢這種，還是用字典樹比較好，但也是有前提的，空間大小允許，字典樹的空間相比較hash還是比較浪費的，畢竟hash可以用bit數組。

那麼在空間要求不那麼嚴格的情況下，字典樹的效率不一定比hash若，它支持動態查詢，比如apple，當用戶輸入到appl時，字典樹此刻的查詢位置可以就到達l這個位置，那麼我在輸入e時光查詢e就可以了（更何況如果我們直接用字母的ASCII作下標肯定會更快）！字典樹它並不用等待你完全輸入完畢後才查詢。

所以效率來講我認為是相對的。

---------------------------------------------------------------------------------------------------------------------------

接下來通過案例來介紹前綴樹的具體操作。

題目：給你100000個長度不超過10的單詞。對於每一個單詞，我們要判斷他出沒出現過，如果出現了，求第一次出現在第幾個位置。

如果我們使用一般的方法，沒查詢一個單詞都去遍歷一遍，那麼時間複雜度將為O(n^2),這對於100000這麼大的數據是不能夠接受的。假如我們要查找單詞student。那我們通過前綴樹只需要查找s開頭的即可，然後接下來查詢t開頭的即可，對於大量的數據可以省去不小的時間。

樹結構：

其中count表示以當前單詞結尾的單詞數量。

prefix表示以該處節點之前的字元串為前綴的單詞數量。

public class TrieNode { int count; int prefix; TrieNode[] nextNode=new TrieNode[26]; public TrieNode(){ count=0; prefix=0; }}

1.前綴樹的創建

好比假設有b，abc，abd，bcd，abcd，efg，hii 這6個單詞,那我們創建trie樹就得到

//插入一個新單詞 public static void insert(TrieNode root,String str){ if(root==null||str.length()==0){ return; } char[] c=str.toCharArray(); for(int i=0;i<str.length();i++){ //如果該分支不存在，創建一個新節點 if(root.nextNode[c[i]-a]==null){ root.nextNode[c[i]-a]=new TrieNode(); } root=root.nextNode[c[i]-a]; root.prefix++;//注意，應該加在後面 } //以該節點結尾的單詞數+1 root.count++; }

2.查詢以str開頭的單詞數量，查詢單詞str的數量

//查找該單詞是否存在，如果存在返回數量，不存在返回-1 public static int search(TrieNode root,String str){ if(root==null||str.length()==0){ return -1; } char[] c=str.toCharArray(); for(int i=0;i<str.length();i++){ //如果該分支不存在，表名該單詞不存在 if(root.nextNode[c[i]-a]==null){ return -1; } //如果存在，則繼續向下遍歷 root=root.nextNode[c[i]-a]; } //如果count==0,也說明該單詞不存在 if(root.count==0){ return -1; } return root.count; } //查詢以str為前綴的單詞數量 public static int searchPrefix(TrieNode root,String str){ if(root==null||str.length()==0){ return -1; } char[] c=str.toCharArray(); for(int i=0;i<str.length();i++){ //如果該分支不存在，表名該單詞不存在 if(root.nextNode[c[i]-a]==null){ return -1; } //如果存在，則繼續向下遍歷 root=root.nextNode[c[i]-a]; } return root.prefix; }

3.在主函數中測試

public static void main(String[] args){ TrieNode newNode=new TrieNode(); insert(newNode,"hello"); insert(newNode,"hello"); insert(newNode,"hello"); insert(newNode,"helloworld"); System.out.println(search(newNode,"hello")); System.out.println(searchPrefix(newNode,"he")); }/**輸出：3 4**/

推薦閱讀：