Trie 樹， 又稱字典樹，單詞查找樹。它來源于retrieval(檢索)中取中間四個字符構成(讀音同try)。用于存儲大量的字符串以便支持快速模式匹配。主要應用在信息檢索領域。
?
Trie 有三種結構： 標準trie (standard trie)、壓縮trie、 后綴trie(suffix trie) 。 最后一種將在《字符串處理4：后綴樹》中詳細講，這里只將前兩種。
?
?
1. 標準Trie (standard trie)
?
標準 Trie樹的結構 ： 所有含有公共前綴的字符串將掛在樹中同一個結點下。實際上trie簡明的存儲了存在于串集合中的所有公共前綴。 假如有這樣一個字符串集合X{bear,bell,bid,bull,buy,sell,stock,stop}。它的標準Trie樹如下圖：
?
?
? ? ? 上圖（藍色圓形結點為內部結點，紅色方形結點為外部結點），我們可以很清楚的看到字符串集合X構造的Trie樹結構。其中從根結點到紅色方框葉子節點所經歷的所有字符組成的串就是字符串集合X中的一個串。
?
????? 注意這里有一個問題 ： 如果X集合中有一個串是另一個串的前綴呢？ 比如，X集合中加入串bi。那么上圖的Trie樹在綠色箭頭所指的內部結點i 就應該也標記成紅色方形結點。這樣話，一棵樹的枝干上將出現兩個連續的葉子結點(這是不合常理的)。
?
????? 也就是說 字符串集合X中不存在一個串是另外一個串的前綴 。如何滿足這個要求呢？我們可以在X中的每個串后面加入一個特殊字符$(這個字符將不會出現在字母表中)。這樣，集合X{bear$、bell$、.... bi$、bid$}一定會滿足這個要求。
?
????? 總結：一個存儲長度為n，來自大小為d的字母表中s個串的集合X的標準trie具有性質如下：
????? (1) 樹中每個內部結點至多有d個子結點。
????? (2) 樹有s個外部結點。
????? (3) 樹的高度等于X中最長串的長度。
????? (4) 樹中的結點數為O(n)。
?
?
標準 Trie樹的查找
?????? 對于英文單詞的查找，我們完全可以在內部結點中建立26個元素組成的指針數組。如果要查找a，只需要在內部節點的指針數組中找第0個指針即可(b=第1個指針，隨機定位)。時間復雜度為O(1)。
?
????? 查找過程：假如我們要在上面那棵Trie中查找字符串bull (b-u-l-l)。
????? (1) 在root結點中查找第('b'-'a'=1)號孩子指針，發現該指針不為空，則定位到第1號孩子結點處——b結點。
????? (2) 在b結點中查找第('u'-'a'=20)號孩子指針，發現該指針不為空，則定位到第20號孩子結點處——u結點。
????? (3) ... 一直查找到葉子結點出現特殊字符'$'位置，表示找到了bull字符串
?
????? 如果在查找過程中終止于內部結點，則表示沒有找到待查找字符串。
?
????? 效率：對于有n個英文字母的串來說，在內部結點中定位指針所需要花費O(d)時間，d為字母表的大小，英文為26。由于在上面的算法中內部結點指針定位使用了數組隨機存儲方式，因此時間復雜度降為了O(1)。但是如果是中文字，下面在實際應用中會提到。因此我們在這里還是用O(d)。 查找成功的時候恰好走了一條從根結點到葉子結點的路徑。因此時間復雜度為O(d*n)。
???? ? 但是，當查找集合X中所有字符串兩兩都不共享前綴時，trie中出現最壞情況。除根之外，所有內部結點都自由一個子結點。此時的查找時間復雜度蛻化為O(d*(n^2))
???????
?
標準 Trie樹的Java代碼實現：
?
package net.hr.algorithm.stroper;
import java.util.ArrayList;
enum NodeKind{LN,BN};
/**
* Trie結點
*/
class TrieNode{
char key;
TrieNode[] points=null;
NodeKind kind=null;
}
/**
* Trie葉子結點
*/
class LeafNode extends TrieNode{
LeafNode(char k){
super.key=k;
super.kind=NodeKind.LN;
}
}
/**
* Trie內部結點
*/
class BranchNode extends TrieNode{
BranchNode(char k){
super.key=k;
super.kind=NodeKind.BN;
super.points=new TrieNode[27];
}
}
/**
* Trie樹
* @author heartraid
*/
public class StandardTrie {
private TrieNode root=new BranchNode(' ');
/**
* 想Tire中插入字符串
*/
public void insert(String word){
//System.out.println("插入字符串："+word);
//從根結點出發
TrieNode curNode=root;
//為了滿足字符串集合X中不存在一個串是另外一個串的前綴
word=word+"$";
//獲取每個字符
char[] chars=word.toCharArray();
//插入
for(int i=0;i<chars.length;i++){
//System.out.println(" 插入"+chars[i]);
if(chars[i]=='$'){
curNode.points[26]=new LeafNode('$');
// System.out.println(" 插入完畢,使當前結點"+curNode.key+"的第26孩子指針指向字符：$");
}
else{
int pSize=chars[i]-'a';
if(curNode.points[pSize]==null){
curNode.points[pSize]=new BranchNode(chars[i]);
// System.out.println(" 使當前結點"+curNode.key+"的第"+pSize+"孩子指針指向字符: "+chars[i]);
curNode=curNode.points[pSize];
}
else{
// System.out.println(" 不插入，找到當前結點"+curNode.key+"的第"+pSize+"孩子指針已經指向字符: "+chars[i]);
curNode=curNode.points[pSize];
}
}
}
}
/**
* Trie的字符串全字匹配
*/
public boolean fullMatch(String word){
//System.out.print("查找字符串："+word+"\n查找路徑：");
//從根結點出發
TrieNode curNode=root;
//獲取每個字符
char[] chars=word.toCharArray();
for(int i=0;i<chars.length;i++){
if(curNode.key=='$'){
System.out.println('&');
// System.out.println(" 【成功】");
return true;
}else{
System.out.print(chars[i]+" -> ");
int pSize=chars[i]-'a';
if(curNode.points[pSize]==null){
// System.out.println(" 【失敗】");
return false;
}else{
curNode=curNode.points[pSize];
}
}
}
// System.out.println(" 【失敗】");
return false;
}
/**
* 先根遍歷Tire樹
*/
private void preRootTraverse(TrieNode curNode){
if(curNode!=null){
System.out.print(curNode.key+" ");
if(curNode.kind==NodeKind.BN)
for(TrieNode childNode:curNode.points)
preRootTraverse(childNode);
}
}
/**
* 得到Trie根結點
*/
public TrieNode getRoot(){
return this.root;
}
/**
* 測試
*/
public static void main(String[] args) {
StandardTrie trie=new StandardTrie();
trie.insert("bear");
trie.insert("bell");
trie.insert("bid");
trie.insert("bull");
trie.insert("buy");
trie.insert("sell");
trie.insert("stock");
trie.insert("stop");
trie.preRootTraverse(trie.getRoot());
trie.fullMatch("stoops");
}
}
?
中文詞語的 標準 Trie樹
????? 由于中文的字遠比英文的26個字母多的多。因此對于trie樹的內部結點，不可能用一個26的數組來存儲指針。如果每個結點都開辟幾萬個中國字的指針空間。估計內存要爆了，就連磁盤也消耗很大。
?
????? 一般我們采取這樣種措施：
???? (1) 以詞語中相同的第一個字為根組成一棵樹。這樣的話，一個中文詞匯的集合就可以構成一片Trie森林。這篇森林都存儲在磁盤上。森林的root中的字和root所在磁盤的位置都記錄在一張以Unicode碼值排序的有序字表中。字表可以存放在內存里。
??? (2) 內部結點的指針用可變長數組存儲。
?
???? 特點：由于中文詞語很少操作4個字的，因此Trie樹的高度不長。查找的時間主要耗費在內部結點指針的查找。因此將這項指向字的指針按照字的Unicode碼值排序，然后加載進內存以后通過二分查找能夠提高效率。
?
?
標準Trie樹的應用和優缺點
???? (1) 全字匹配：確定待查字串是否與集合的一個單詞完全匹配。如上代碼fullMatch()。
???? (2) 前綴匹配：查找集合中與以s為前綴的所有串。
?
???? 注意：Trie樹的結構并不適合用來查找子串。這一點和前面提到的PAT Tree以及后面專門要提到的Suffix Tree的作用有很大不同。
?
????? 優點： 查找效率比與集合中的每一個字符串做匹配的效率要高很多。在o(m)時間內搜索一個長度為m的字符串s是否在字典里。
????? 缺點：標準Trie的空間利用率不高，可能存在大量結點中只有一個子結點，這樣的結點絕對是一種浪費。正是這個原因，才迅速推動了下面所講的壓縮trie的開發。
?
?
?
2. 壓縮Trie (compressed trie)
?
????? 壓縮Trie類似于標準Trie，但它能保證trie中的每個內部結點至少有兩個子節點(根結點除外)。通過把單子結點鏈壓縮進葉子節點來執行這個規則。
?
壓縮Trie的定義
?
????? 冗余結點(redundant node)：如果T的一個非根內部結點v只有一個子結點，那么我們稱v是冗余的。
????? 冗余鏈(redundant link)：如上標準Trie圖中，內部結點e只有一個內部子結點l，而l也只有一個葉子結點。那么e-l-l就構成了一條冗余鏈。
????? 壓縮(compressed)：對于冗余鏈 v1- v2- v3- ... -vn，我們可以用單邊v1-vn來替代。
?
????? 對上面標準Trie的圖壓縮之后，形成了Compressed Trie的字符表示圖如下：
壓縮Trie的性質和優勢：
?
???? 與標準Trie比較，壓縮Trie的結點數與串的個數成正比了，而不是與串的總長度成正比。一棵存儲來自大小為d的字母表中的s個串的結合T的壓縮trie具有如下性質：
?
???? (1) T中的每個內部結點至少有兩個子結點，至多有d個子結點。
???? (2) T有s個外部結點。
???? (3) T中的結點數為O(s)
???? 存儲空間從標準Trie的O(n)降低到壓縮后的O(s)，其中n為集合T中總字符串長度，s為T中的字符串個數。
?
壓縮Trie的壓縮表示
?
???? 上面的圖是壓縮Trie的字符串表示。相比標準Trie而言，確實少了不少結點。但是細心的讀者會發現，葉子結點中的字符數量增加了，比如結點ell，那么這種壓縮空間的效率當然會打折扣了。那么有什么好辦法呢，這里我們介紹一種壓縮表示方法。即把所有結點中的字符串用三元組的形式表示如下圖：
?
???
? ??? 其中三元組(i，j，k)表示S[i]的從第j個位置到第k個位置間的子串。比如(5,1,3,)表示S[5][1...3]="ell"。
?
? ??? 這種壓縮表示的一個巨大的優點就是：無論結點需要存儲多長的字串，全部都可以用一個三元組表示，而且三元組所占的空間是固定有限的。但是為了做到這一點，必須有一張輔助索引結構（如上圖右側s0—s7所示）。 ??
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
