Trie，又稱字典樹、單詞查找樹或鍵樹，是一種樹形結(jié)構(gòu)，是一種哈希樹的變種。典型應(yīng)用是用于統(tǒng)計，排序和保存大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計。它的優(yōu)點是：利用字符串的公共前綴來減少查詢時間，最大限度地減少無謂的字符串比較，查詢效率比哈希樹高。
什么是前綴樹
在計算機科學(xué)中，trie，又稱前綴樹或字典樹，是一種有序樹，用于保存關(guān)聯(lián)數(shù)組，其中的鍵通常是字符串。與二叉查找樹不同，鍵不是直接保存在節(jié)點中，而是由節(jié)點在樹中的位置決定。一個節(jié)點的所有子孫都有相同的前綴，也就是這個節(jié)點對應(yīng)的字符串，而根節(jié)點對應(yīng)空字符串。一般情況下，不是所有的節(jié)點都有對應(yīng)的值，只有葉子節(jié)點和部分內(nèi)部節(jié)點所對應(yīng)的鍵才有相關(guān)的值。
Trie 這個術(shù)語來自于 retrieval。根據(jù)詞源學(xué)，trie 的發(fā)明者 Edward Fredkin 把它讀作/?tri?/ “tree”。但是，其他作者把它讀作/?tra?/ “try”。trie 中的鍵通常是字符串，但也可以是其它的結(jié)構(gòu)。trie 的算法可以很容易地修改為處理其它結(jié)構(gòu)的有序序列，比如一串?dāng)?shù)字或者形狀的排列。比如，bitwise trie 中的鍵是一串位元，可以用于表示整數(shù)或者內(nèi)存地址。trie 樹常用于搜索提示。如當(dāng)輸入一個網(wǎng)址，可以自動搜索出可能的選擇。當(dāng)沒有完全匹配的搜索結(jié)果，可以返回前綴最相似的可能。
上圖是一棵Trie樹，表示了關(guān)鍵字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。從上圖可以歸納出Trie樹的基本性質(zhì)：
根節(jié)點不包含字符，除根節(jié)點外的每一個子節(jié)點都包含一個字符。
從根節(jié)點到某一個節(jié)點，路徑上經(jīng)過的字符連接起來，為該節(jié)點對應(yīng)的字符串。
每個節(jié)點的所有子節(jié)點包含的字符互不相同。
從第一字符開始有連續(xù)重復(fù)的字符只占用一個節(jié)點，比如上面的to，和ten，中重復(fù)的單詞t只占用了一個節(jié)點。
前綴樹的實現(xiàn)
重點在于節(jié)點數(shù)據(jù)結(jié)構(gòu)，重要的插入和查找方法，以及遞歸和非遞歸兩種形式。
節(jié)點數(shù)據(jù)結(jié)構(gòu)定義
Node節(jié)點中使用map較為高效，用于映射到下一個節(jié)點：
public class Trie {
private class Node{
public boolean isWord; // 是否是某個單詞的結(jié)束
public TreeMap<Character, Node> next; //到下一個節(jié)點的映射
public Node(boolean isWord){
this.isWord = isWord;
//初始化字典樹
next = new TreeMap<>();
}
public Node(){
this(false);
}
}
//根節(jié)點
private Node root;
//Trie單詞個數(shù)
private int size;
public Trie(){
root = new Node();
size = 0;
}
// 獲得Trie中存儲的單詞數(shù)量
public int getSize(){
return size;
}
}插入方法
非遞歸方式
向Trie中添加一個新的單詞word: 將單詞拆分成一個個字符c，然后從根節(jié)點開始往下添加
public void add(String word){
Node cur = root;
//循環(huán)判斷新的cur節(jié)點是否包含下一個字符到下一個節(jié)點的映射
for(int i = 0 ; i < word.length() ; i ++){
//將c當(dāng)成一個節(jié)點插入Trie中
char c = word.charAt(i);
//判斷cur.next是不是已經(jīng)指向我們要找的c字符相應(yīng)的節(jié)點
if(cur.next.get(c) == null){
//新建節(jié)點
cur.next.put(c, new Node());
}
//否則，就直接走到該節(jié)點位置即可
cur = cur.next.get(c);
}
//判斷該單詞并不表示任何一個單詞的結(jié)尾
if(!cur.isWord){
//確定cur是新的單詞
cur.isWord = true;
size ++;
}
}遞歸方式
/**
* 向Trie中添加一個新的單詞word(遞歸寫法接口)
*
* @param word
*/
public void recursionAdd(String word) {
Node cur = root;
add(root, word, 0);
}
/**
* 遞歸寫法調(diào)用方法實現(xiàn)遞歸添加
*
* @param node 傳入要進行添加的節(jié)點
* @param word 傳入要進行添加的單詞
*/
public void add(Node node, String word, int index) {
// 確定終止條件,這個終止條件在沒加index這個參數(shù)時,很難確定
// 此時一個單詞已經(jīng)遍歷完成了,如果這個結(jié)束節(jié)點沒有標(biāo)記為單詞,就標(biāo)記為單詞
if (!node.isWord && index == word.length()) {
node.isWord = true;
size++;
}
if (word.length() > index) {
char addLetter = word.charAt(index);
// 判斷trie的下個節(jié)點組中是否有查詢的字符,如果沒有,就添加
if (node.next.get(addLetter) == null) {
node.next.put(addLetter, new Node());
}
// 基于已經(jīng)存在的字符進行下個字符的遞歸查詢
add(node.next.get(addLetter), word, index + 1);
}
}查詢單詞方法
非遞歸方式
/**
* 查詢單詞word是否在Trie中(非遞歸寫法)
*
* @param word
* @return
*/
public boolean contains(String word) {
Node cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (cur.next.get(c) == null) {
return false;
} else {
cur = cur.next.get(c);
}
}
return cur.isWord;
}遞歸方式
/**
* 查詢單詞word中是否在Trie中接口(遞歸寫法)
*
* @param word
* @return
*/
public boolean recursionContains(String word) {
Node cur = root;
return contains(root, word, 0);
}
/**
* 查詢word中是否在Trie中遞歸寫法
*
* @param node
* @param word
* @param index
* @return
*/
private boolean contains(Node node, String word, int index) {
if (index == word.length()) {
return node.isWord;
}
char c = word.charAt(index);
if (node.next.get(c) == null) {
return false;
} else {
return contains(node.next.get(c), word, index + 1);
}
}查詢前綴方法
非遞歸方式
/**
* 查詢是否在Trie中有單詞一prefix為前綴
*
* @param prefix
* @return
*/
public boolean isPrefix(String prefix) {
Node cur = root;
for (int i = 0; i < prefix.length(); i++) {
char c = prefix.charAt(i);
if (cur.next.get(c) == null) {
return false;
}
cur = cur.next.get(c);
}
return true;
}遞歸方式
/**
* 查詢是否在Trie中有單詞一prefix為前綴(遞歸調(diào)用)
*
* @param prefix
* @return
*/
public boolean recursionIsPrefix(String prefix) {
Node node = root;
return recursionIsPrefix(root, prefix, 0);
}
/**
* 查詢是否在Trie中有單詞一prefix為前綴(遞歸實現(xiàn))
*
* @return
*/
public boolean recursionIsPrefix(Node root, String prefix, int index) {
if (prefix.length() == index) {
return true;
}
char c = prefix.charAt(index);
if (root.next.get(c) == null) {
return false;
} else {
return recursionIsPrefix(root.next.get(c), prefix, ++index);
}
}前綴樹的拓展
再深入理解下前綴樹。
前綴樹的復(fù)雜度
設(shè)平均查詢的query詞長n， 白名單m條記錄，平均長度k,
簡單單詞查詢：一個query，需要遍歷每一個白名單，調(diào)用query是否contains方法，contains方法遍歷前詞，找到頭元素一致，再遍歷判斷尾序列，contains的復(fù)雜度是O(n)，整體復(fù)雜度是O(mn)
前綴樹查詢: 一個query，將這個query從頭到尾遍歷，每個元素在前綴樹中判斷，操作都是取下一個節(jié)點和判斷是否是end，時間復(fù)雜度是O(1)，整體時間復(fù)雜度是O(n)
前綴樹有哪些應(yīng)用
這個比較簡單，就簡單列下：
前綴匹配
字符串檢索， 比如 敏感詞過濾，黑白名單等
詞頻統(tǒng)計
字符串排序
前綴樹的壓縮：基數(shù)樹
在計算機科學(xué)中，基數(shù)樹，或稱壓縮前綴樹，是一種更節(jié)省空間的 Trie（前綴樹）。對于基數(shù)樹的每個節(jié)點，如果該節(jié)點是確定的子樹的話，就和父節(jié)點合并?；鶖?shù)樹可用來構(gòu)建關(guān)聯(lián)數(shù)組。 用于 IP 路由。 信息檢索中用于文本文檔的倒排索引。
基數(shù)樹可看做是以二進制位串為關(guān)鍵字的 trie 樹，是一種多叉樹形結(jié)構(gòu)，同時又類似多層索引表，每個中間節(jié)點包含指向多個子節(jié)點的指針數(shù)組，葉子節(jié)點包含指向?qū)嶋H的對象的指針(由于對象不具備樹節(jié)點結(jié)構(gòu)，因此將其父節(jié)點看做葉節(jié)點)?；鶖?shù)樹也被設(shè)計成多道樹，以提高磁盤交互性能。同時，基數(shù)樹也是按照字典序來組織葉節(jié)點的，這種特點使之適合持久化改造，加上它的多道特點，靈活性較強，適合作為區(qū)塊鏈的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，構(gòu)建持久性區(qū)塊時較好地映射各類數(shù)據(jù)集合上?；鶖?shù)樹支持插入、刪除、查找操作。查找包括完全匹配、前綴匹配、前驅(qū)查找、后繼查找。所有這些操作都是 O(k)復(fù)雜度，其中 k 是所有字符串中最大的長度。
雙數(shù)組Trie樹(DoubleArrayTrie)
雙數(shù)組Trie樹(DoubleArrayTrie)是一種空間復(fù)雜度低的Trie樹，應(yīng)用于字符區(qū)間大的語言（如中文、日文等）分詞領(lǐng)域。
雙數(shù)組Trie (Double-Array Trie)結(jié)構(gòu)由日本人JUN-ICHI AOE于1989年提出的，是Trie結(jié)構(gòu)的壓縮形式，僅用兩個線性數(shù)組來表示Trie樹，該結(jié)構(gòu)有效結(jié)合了數(shù)字搜索樹(Digital Search Tree)檢索時間高效的特點和鏈?zhǔn)奖硎镜腡rie空間結(jié)構(gòu)緊湊的特點。雙數(shù)組Trie的本質(zhì)是一個確定有限狀態(tài)自動機（DFA），每個節(jié)點代表自動機的一個狀態(tài)，根據(jù)變量不同，進行狀態(tài)轉(zhuǎn)移，當(dāng)?shù)竭_結(jié)束狀態(tài)或無法轉(zhuǎn)移時，完成一次查詢操作。在雙數(shù)組所有鍵中包含的字符之間的聯(lián)系都是通過簡單的數(shù)學(xué)加法運算表示，不僅提高了檢索速度，而且省去了鏈?zhǔn)浇Y(jié)構(gòu)中使用的大量指針，節(jié)省了存儲空間。——《基于雙數(shù)組Ｔｒｉｅ樹算法的字典改進和實現(xiàn)》
具體可以看這篇文章
參考文章
https://blog.csdn.net/v_july_v/article/details/6897097
https://www.cnblogs.com/bonelee/p/8830825.html
https://blog.csdn.net/forever_dreams/article/details/81009580
https://www.jianshu.com/p/b9b8bf82fcd5
https://bestqiang.blog.csdn.net/article/details/89103524文章來源：http://www.zghlxwxcb.cn/news/detail-732984.html
https://java-sword.blog.csdn.net/article/details/89373156文章來源地址http://www.zghlxwxcb.cn/news/detail-732984.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)】樹 - 前綴樹(Trie Tree)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
