劍指Offer-Trie樹(字典樹)

劍指Offer——Trie樹(字典樹)Trie樹Trie樹，即字典樹，又稱單詞查找樹或鍵樹，是一種樹形結(jié)構(gòu)，是一種哈希樹的變種。典型應(yīng)用是統(tǒng)計(jì)和排序大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)。它的優(yōu)點(diǎn)是：最大限度地減少無(wú)謂的字符串比較，查詢效率比哈希表高。Trie的核心思想是空間換時(shí)間。利用字符串的公共前綴來(lái)降低查詢時(shí)間的開(kāi)銷以達(dá)到提高效率的目的。Trie樹也有它的缺點(diǎn)，Trie樹的內(nèi)存消耗非常大。當(dāng)然，或許用左兒子右兄弟的方法建樹的話，可能會(huì)好點(diǎn)?？梢?jiàn)，優(yōu)化的點(diǎn)存在于建樹過(guò)程中。和二叉查找樹不同，在trie樹中，每個(gè)結(jié)點(diǎn)上并非存儲(chǔ)一個(gè)元素。trie樹把要查找的關(guān)鍵詞看作一個(gè)字符序列，并根據(jù)構(gòu)成關(guān)鍵詞字符的先后順序構(gòu)造用于檢索的樹結(jié)構(gòu)。在trie樹上進(jìn)行檢索類似于查閱英語(yǔ)詞典。3個(gè)基本性質(zhì)1.根節(jié)點(diǎn)不包含字符，每條邊代表一個(gè)字符。2.從根節(jié)點(diǎn)到某一節(jié)點(diǎn)，路徑上經(jīng)過(guò)的字符連接起來(lái)，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串。3.每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符都不相同。字典樹的構(gòu)建題目：給你100000個(gè)長(zhǎng)度不超過(guò)10的單詞。對(duì)于每一個(gè)單詞，我們要判斷他出沒(méi)出現(xiàn)過(guò)，如果出現(xiàn)了，求第一次出現(xiàn)在第幾個(gè)位置。分析：這題當(dāng)然可以用hash來(lái)解決，但是本文重點(diǎn)介紹的是trie樹，因?yàn)樵谀承┓矫嫠挠猛靖蟆１热缯f(shuō)對(duì)于某一個(gè)單詞，我們要詢問(wèn)它的前綴是否出現(xiàn)過(guò)。這樣hash就不好搞了，而用trie還是很簡(jiǎn)單。假設(shè)我要查詢的單詞是abcd，那么在他前面的單詞中，以b，c，d，f之類開(kāi)頭的我顯然不必考慮。而只要找以a開(kāi)頭的中是否存在abcd就可以了。同樣的，在以a開(kāi)頭中的單詞中，我們只要考慮以b作為第二個(gè)字母的，一次次縮小范圍和提高針對(duì)性，這樣一個(gè)樹的模型就漸漸清晰了。好比假設(shè)有b，abc，abd，bcd，abcd，efg，hii這6個(gè)單詞，我們構(gòu)建的樹就是如下圖這樣的（圖片來(lái)自百度百科）：如上圖所示，對(duì)于每一個(gè)節(jié)點(diǎn)，從根遍歷到他的過(guò)程就是一個(gè)單詞，如果這個(gè)節(jié)點(diǎn)被標(biāo)記為紅色，就表示這個(gè)單詞存在，否則不存在。那么，對(duì)于一個(gè)單詞，我只要順著他從根走到對(duì)應(yīng)的節(jié)點(diǎn)，再看這個(gè)節(jié)點(diǎn)是否被標(biāo)記為紅色就可以知道它是否出現(xiàn)過(guò)了。把這個(gè)節(jié)點(diǎn)標(biāo)記為紅色，就相當(dāng)于插入了這個(gè)單詞。這樣一來(lái)我們查詢和插入可以一起完成（重點(diǎn)體會(huì)這個(gè)查詢和插入是如何一起完成的，稍后，下文具體解釋）。我們可以看到，trie樹每一層的節(jié)點(diǎn)數(shù)是26^i（26個(gè)英文字母）級(jí)別的。所以為了節(jié)省空間，我們用動(dòng)態(tài)鏈表，或者用數(shù)組來(lái)模擬?？臻g的花費(fèi)，不會(huì)超過(guò)單詞數(shù)×單詞長(zhǎng)度。已知n個(gè)由小寫字母構(gòu)成的平均長(zhǎng)度為10的單詞,判斷其中是否存在某個(gè)串為另一個(gè)串的前綴子串。下面對(duì)比3種方法：最容易想到的：1.即從字符串集中從頭往后搜，看每個(gè)字符串是否為字符串集中某個(gè)字符串的前綴，復(fù)雜度為O(n^2)。2.使用hash：我們用hash存下所有字符串的所有前綴子串，建立存有子串hash的復(fù)雜度為O(n*len)，而查詢的復(fù)雜度為O(n)*O(1)=O(n)。3.使用trie：因?yàn)楫?dāng)查詢?nèi)缱址產(chǎn)bc是否為某個(gè)字符串的前綴時(shí)，顯然以b,c,d....等不是以a開(kāi)頭的字符串就不用查找了。所以建立trie的復(fù)雜度為O(n*len)，而建立+查詢?cè)趖rie中是可以同時(shí)執(zhí)行的，建立的過(guò)程也就可以稱為查詢的過(guò)程，hash就不能實(shí)現(xiàn)這個(gè)功能。所以總的復(fù)雜度為O(n*len)，實(shí)際查詢的復(fù)雜度也只是O(len)。（說(shuō)白了，就是Trie樹的平均高度h為len，所以Trie樹的查詢復(fù)雜度為O（h）=O（len）。好比一棵二叉平衡樹的高度為logN，則其查詢，插入的平均時(shí)間復(fù)雜度亦為O（logN））。查詢Trie樹是簡(jiǎn)單但實(shí)用的數(shù)據(jù)結(jié)構(gòu)，通常用于實(shí)現(xiàn)字典查詢。我們做即時(shí)響應(yīng)用戶輸入的AJAX搜索框時(shí)，就是Trie樹。本質(zhì)上，Trie是一棵存儲(chǔ)多個(gè)字符串的樹。相鄰節(jié)點(diǎn)間的邊代表一個(gè)字符，這樣樹的每條分支代表一則子串，而樹的葉節(jié)點(diǎn)則代表完整的字符串。和普通樹不同的地方是，相同的字符串前綴共享同一條分支。下面，再舉一個(gè)例子。給出一組單詞，inn,int,at,age,adv,ant,我們可以得到下面的Trie：可以看出：每條邊對(duì)應(yīng)一個(gè)字母。每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一項(xiàng)前綴。葉節(jié)點(diǎn)對(duì)應(yīng)最長(zhǎng)前綴，即單詞本身。單詞inn與單詞int有共同的前綴“in”,因此他們共享左邊的一條分支，root->i->in。同理，ate,age,adv,和ant共享前綴"a"，所以他們共享從根節(jié)點(diǎn)到節(jié)點(diǎn)"a"的邊。查詢操縱非常簡(jiǎn)單。比如要查找int，順著路徑i->in->int就找到了。搭建Trie的基本算法也很簡(jiǎn)單，無(wú)非是逐一把每個(gè)單詞的每個(gè)字母插入Trie。插入前先看前綴是否存在。如果存在，就共享，否則創(chuàng)建對(duì)應(yīng)的節(jié)點(diǎn)和邊。比如要插入單詞add，就有下面幾步：考察前綴"a"，發(fā)現(xiàn)邊a已經(jīng)存在。于是順著邊a走到節(jié)點(diǎn)a?？疾焓Ｏ碌淖址?dd"的前綴"d"，發(fā)現(xiàn)從節(jié)點(diǎn)a出發(fā)，已經(jīng)有邊d存在。于是順著邊d走到節(jié)點(diǎn)ad考察最后一個(gè)字符"d"，這下從節(jié)點(diǎn)ad出發(fā)沒(méi)有邊d了，于是創(chuàng)建節(jié)點(diǎn)ad的子節(jié)點(diǎn)add，并把邊ad->add標(biāo)記為d。查找分析在trie樹中查找一個(gè)關(guān)鍵字的時(shí)間和樹中包含的結(jié)點(diǎn)數(shù)無(wú)關(guān)，而取決于組成關(guān)鍵字的字符數(shù)。而二叉查找樹的查找時(shí)間和樹中的結(jié)點(diǎn)數(shù)有關(guān)O(log2n)。如果要查找的關(guān)鍵字可以分解成字符序列且不是很長(zhǎng)，利用trie樹查找速度優(yōu)于二叉查找樹。例如：若關(guān)鍵字長(zhǎng)度最大是5，則利用trie樹，利用5次比較可以從26^5＝11881376個(gè)可能的關(guān)鍵字中檢索出指定的關(guān)鍵字。而利用二叉查找樹至少要進(jìn)行次比較。應(yīng)用1.字符串檢索，詞頻統(tǒng)計(jì)，搜索引擎的熱門查詢事先將已知的一些字符串（字典）的有關(guān)信息保存到trie樹里，查找另外一些未知字符串是否出現(xiàn)過(guò)或者出現(xiàn)頻率。舉例：1、有一個(gè)1G大小的一個(gè)文件，里面每一行是一個(gè)詞，詞的大小不超過(guò)16字節(jié)，內(nèi)存限制大小是1M。返回頻數(shù)最高的100個(gè)詞。2、給出N個(gè)單詞組成的熟詞表，以及一篇全用小寫英文書寫的文章，請(qǐng)你按最早出現(xiàn)的順序?qū)懗鏊胁辉谑煸~表中的生詞。3、給出一個(gè)詞典，其中的單詞為不良單詞。單詞均為小寫字母。再給出一段文本，文本的每一行也由小寫字母構(gòu)成。判斷文本中是否含有任何不良單詞。例如，若rob是不良單詞，那么文本problem含有不良單詞。4、1000萬(wàn)字符串，其中有些是重復(fù)的，需要把重復(fù)的全部去掉，保留沒(méi)有重復(fù)的字符串。請(qǐng)?jiān)趺丛O(shè)計(jì)和實(shí)現(xiàn)？5、一個(gè)文本文件，大約有一萬(wàn)行，每行一個(gè)詞，要求統(tǒng)計(jì)出其中最頻繁出現(xiàn)的前10個(gè)詞，請(qǐng)給出思想，給出時(shí)間復(fù)雜度分析。6、尋找熱門查詢：搜索引擎會(huì)通過(guò)日志文件把用戶每次檢索使用的所有檢索串都記錄下來(lái)，每個(gè)查詢串的長(zhǎng)度為1-255字節(jié)。假設(shè)目前有一千萬(wàn)個(gè)記錄，這些查詢串的重復(fù)讀比較高，雖然總數(shù)是1千萬(wàn)，但是如果去除重復(fù)和，不超過(guò)3百萬(wàn)個(gè)。一個(gè)查詢串的重復(fù)度越高，說(shuō)明查詢它的用戶越多，也就越熱門。請(qǐng)你統(tǒng)計(jì)最熱門的10個(gè)查詢串，要求使用的內(nèi)存不能超過(guò)1G(京東筆試題簡(jiǎn)答題與此類似)。(1)請(qǐng)描述你解決這個(gè)問(wèn)題的思路；(2)請(qǐng)給出主要的處理流程，算法，以及算法的復(fù)雜度。2.字符串最長(zhǎng)公共前綴Trie樹利用多個(gè)字符串的公共前綴來(lái)節(jié)省存儲(chǔ)空間，反之，當(dāng)我們把大量字符串存儲(chǔ)到一棵trie樹上時(shí)，我們可以快速得到某些字符串的公共前綴。舉例：1)給出N個(gè)小寫英文字母串，以及Q個(gè)詢問(wèn)，即詢問(wèn)某兩個(gè)串的最長(zhǎng)公共前綴的長(zhǎng)度是多少.解決方案：首先對(duì)所有的串建立其對(duì)應(yīng)的字母樹。此時(shí)發(fā)現(xiàn)，對(duì)于兩個(gè)串的最長(zhǎng)公共前綴的長(zhǎng)度即它們所在結(jié)點(diǎn)的公共祖先個(gè)數(shù)，于是，問(wèn)題就轉(zhuǎn)化為了離線（Offline）的最近公共祖先（LeastCommonAncestor，簡(jiǎn)稱LCA）問(wèn)題。而最近公共祖先問(wèn)題同樣是一個(gè)經(jīng)典問(wèn)題，可以用下面幾種方法：1.利用并查集（DisjointSet），可以采用經(jīng)典的Tarjan算法；2.求出字母樹的歐拉序列（EulerSequence）后，就可以轉(zhuǎn)為經(jīng)典的最小值查詢（RangeMinimumQuery，簡(jiǎn)稱RMQ）問(wèn)題了；3.排序Trie樹是一棵多叉樹，只要先序遍歷整棵樹，輸出相應(yīng)的字符串便是按字典序排序的結(jié)果。舉例：給你N個(gè)互不相同的僅由一個(gè)單詞構(gòu)成的英文名，讓你將它們按字典序從小到大排序輸出。4.作為其他數(shù)據(jù)結(jié)構(gòu)和算法的輔助結(jié)構(gòu)如后綴樹，AC自動(dòng)機(jī)等。舉例下面以字典樹的構(gòu)建與單詞查找為例。TrieTreeNode.java[html]viewplaincopyprint?在CODE上查看代碼片派生到我的代碼片package.ujn.trieTree;publicclassTrieTreeNode{intnCount;//記錄該字符出現(xiàn)次數(shù)charch;//記錄該字符TrieTreeNode[]child;//記錄子節(jié)點(diǎn)finalintMAX_SIZE=26;publicTrieTreeNode(){nCount=1;child=newTrieTreeNode[MAX_SIZE];}}TrieTree.java[html]viewplaincopyprint?在CODE上查看代碼片派生到我的代碼片package.ujn.trieTree;publicclassTrieTree{//字典樹的插入和構(gòu)建publicvoidcreateTrie(TrieTreeNodenode,Stringstr){if(str==null||str.length()==0){return;}char[]letters=str.toCharArray();for(inti=0;i<letters.length;i++){intpos=letters[i]-'a';//用相對(duì)于a字母的值作為下標(biāo)索引，也隱式地記錄了該字母的值if(node.child[pos]==null){node.child[pos]=newTrieTreeNode();}else{node.child[pos].nCount++;}node.ch=letters[i];node=node.child[pos];}}//字典樹的查找publicintfindCount(TrieTreeNodenode,Stringstr){if(str==null||str.length()==0){return-1;}char[]letters=str.toCharArray();for(inti=0;i<letters.length;i++){intpos=letters[i]-'a';if(node.child[pos]==null){return0;}else{node=node.child[pos];}}returnnode.nCount;}}Test.java[html]viewplaincopyprint?在CODE上查看代碼片派生到我的代碼片package.ujn.trieTree;publicclassTest{publicstaticvoidmain(String[]args){/***ProblemDescription老師交給他很多單詞(只有小寫字母組成,不會(huì)有重復(fù)的單詞出現(xiàn)),現(xiàn)在老師要他統(tǒng)計(jì)*出以某個(gè)字符串為前綴的單詞數(shù)量(單詞本身也是自己的前綴).*/String[]strs={"banana","band","bee","absolute","acm"};String[]prefix={"ba","b","band","abc"};TrieTreetree=newTrieTree();TrieTreeNoderoot=newTrieTreeNode();for(Strings:strs){tree.createTrie(root,s);}//tree.printAllWords();for(Stringpre:prefix){intnum=tree.findCount(root,pre);System.out.println(pre+""+num);}}}小結(jié)看過(guò)上面的代碼，是否發(fā)現(xiàn)這個(gè)代碼有什么問(wèn)題呢？盡管這個(gè)實(shí)現(xiàn)方式查找的效率很高，時(shí)間復(fù)雜度是O(m)，m是要查找的單詞中包含的字母的個(gè)數(shù)。但是確浪費(fèi)大量存放空指針的存儲(chǔ)空間。因?yàn)椴豢赡苊總€(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)都包含26個(gè)字母的。所以對(duì)于這個(gè)問(wèn)題，字典樹存在的意義是解決快速搜索的問(wèn)題，所以采取以空間換時(shí)間的作法也毋庸置疑。Trie樹占用內(nèi)存較大，例如：處理最大長(zhǎng)度為20、全部為小寫字母的一組字符串，則可能需要2620個(gè)節(jié)點(diǎn)來(lái)保存數(shù)據(jù)。而這樣的樹實(shí)際上稀疏的十分厲害，可以采用左兒子右兄弟的方式來(lái)改善，也可以采用需要多少子節(jié)點(diǎn)則添加多少子節(jié)點(diǎn)來(lái)解決（不要類似網(wǎng)上的示例，每個(gè)節(jié)點(diǎn)初始化時(shí)就申請(qǐng)一個(gè)長(zhǎng)度為26的數(shù)組）。Wiki上提到了采用三數(shù)組Trie(Tripple-ArrayTrie)和二數(shù)組Trie(Double-ArrayTrie)來(lái)解決該問(wèn)題，此外還有壓縮等方式來(lái)緩解該問(wèn)題。示例優(yōu)化TrieTreeNode.java[html]viewplaincopyprint?在CODE上查看代碼片派生到我的代碼片package.ujn.trieTreeMap;importjava.util.HashMap;importjava.util.Map;publicclassTrieNode{intnCount;//記錄該字符出現(xiàn)次數(shù)Map<Character,TrieNode>childdren;//記錄子節(jié)點(diǎn)publicTrieNode(){nCount=1;childdren=newHashMap<Character,TrieNode>();}}TrieTree.java[html]viewplaincopyprint?在CODE上查看代碼片派生到我的代碼片package.ujn.trieTreeMap;//利用Map動(dòng)態(tài)創(chuàng)建節(jié)點(diǎn)publicclassTrieTree{//字典樹的插入和構(gòu)建publicvoidinsert(TrieNodenode,Stringword){for(inti=0;i<word.length();i++){Characterc=newCharacter(word.charAt(i));if(!ren.containsKey(c)){node.childdren.put(c,newTrieNode());}else{node.childdren.get(c).nCount++;}node=node.childdren.get(c);}}//字典樹的查找publicintsearch(TrieNodenode,Stringword){for(inti=0;i<word.length();i++){Characterc=newCharacter(word.charAt(i));if(!node.childdren.containsKey(c)){return0;}node=node.childdren.get(c);}returnnode.nCount;}}Test.java[html]viewplaincopyprint?在CODE上查看代碼片派生到我的代碼片package.ujn.trieTreeMap;publicclassTest{publicstaticvoidmain(String[]args){/***ProblemDescription老師交給他很多單詞(只有小寫字母組成,不會(huì)有重復(fù)的單詞出現(xiàn)),現(xiàn)在老師要他統(tǒng)計(jì)*出以某個(gè)字符串為前綴的單詞數(shù)量(單詞本身也是自己的前綴).*/String[]strs={"banana","band","bee","absolute","acm"};String[]prefix={"ba","b","band","abc"};TrieTreetree=newTrieTree();TrieNodenode=newTrieNode();for(Strings:strs){tree.insert(node,s);}//tree.printAllWords();for(Stringpre:prefix){intnum=tree.search(node,pre);System.out.println(pre+""+num);}}}計(jì)算結(jié)果如下：經(jīng)過(guò)以上方法的改進(jìn)，可避免冗余節(jié)點(diǎn)的存在。將字典樹的優(yōu)勢(shì)進(jìn)一步放大。當(dāng)然，也可以使用左兒子右兄弟的形式創(chuàng)建字典樹。此方法后續(xù)介紹~文件讀入[html]viewplaincopyprint?在CODE上查看代碼片派生到我的代碼片package.ujn.trieTreeMap;importjava.io.BufferedReader;importjava.io.File;importjava.io.FileInputStream;importjava.io.InputStreamReader;publicclassTest{publicstaticvoidmain(String[]args){/***ProblemDescription老師交給他很多單詞(只有小寫字母組成,不會(huì)有重復(fù)的單詞出現(xiàn)),現(xiàn)在老師要他統(tǒng)計(jì)*出以某個(gè)字符串為前綴的單詞數(shù)量(單詞本身也是