引子
Trie樹(shù)（來(lái)自單詞retrieval），又稱前綴字，單詞查找樹(shù)，字典樹(shù)，是一種樹(shù)形結(jié)構(gòu)，是一種哈希樹(shù)的變種，是一種用于快速檢索的多叉樹(shù)結(jié)構(gòu)。
它的優(yōu)點(diǎn)是：最大限度地減少無(wú)謂的字符串比較，查詢效率比哈希表高。
Trie的核心思想是空間換時(shí)間。利用字符串的公共前綴來(lái)降低查詢時(shí)間的開(kāi)銷以達(dá)到提高效率的目的。
Trie樹(shù)也有它的缺點(diǎn), 假定我們只對(duì)字母與數(shù)字進(jìn)行處理，那么每個(gè)節(jié)點(diǎn)至少有52＋10個(gè)子節(jié)點(diǎn)。為了節(jié)省內(nèi)存，我們可以用鏈表或數(shù)組。在JS中我們直接用數(shù)組，因?yàn)镴S的數(shù)組是動(dòng)態(tài)的，自帶優(yōu)化。
基本性質(zhì)
程序?qū)崿F(xiàn)
// by 司徒正美class Trie { constructor() { this.root = new TrieNode(); } isValid(str) { return /^[a-z1-9]+$/i.test(str); } insert(word) { // addWord if (this.isValid(word)) { var cur = this.root; for (var i = 0; i < word.length; i++) { var c = word.charCodeAt(i); c -= 48; //減少”0“的charCode var node = cur.son[c]; if (node == null) { var node = (cur.son[c] = new TrieNode()); node.value = word.charAt(i); node.numPass = 1; //有N個(gè)字符串經(jīng)過(guò)它 } else { node.numPass++; } cur = node; } cur.isEnd = true; //檣記有字符串到此節(jié)點(diǎn)已經(jīng)結(jié)束 cur.numEnd++; //這個(gè)字符串重復(fù)次數(shù) return true; } else { return false; } } remove(word){ if (this.isValid(word)) { var cur = this.root; var array = [], n = word.length for (var i = 0; i < n; i++) { var c = word.charCodeAt(i); c = this.getIndex(c) var node = cur.son[c]; if(node){ array.push(node) cur = node }else{ return false } } if(array.length === n){ array.forEach(function(){ el.numPass-- }) cur.numEnd -- if( cur.numEnd == 0){ cur.isEnd = false } } }else{ return false } } preTraversal(cb){//先序遍歷 function preTraversalImpl(root, str, cb){ cb(root, str); for(let i = 0,n = root.son.length; i < n; i ++){ let node = root.son[i]; if(node){ preTraversalImpl(node, str + node.value, cb); } } } preTraversalImpl(this.root, "", cb); } // 在字典樹(shù)中查找是否存在某字符串為前綴開(kāi)頭的字符串(包括前綴字符串本身) isContainPrefix(word) { if (this.isValid(word)) { var cur = this.root; for (var i = 0; i < word.length; i++) { var c = word.charCodeAt(i); c -= 48; //減少”0“的charCode if (cur.son[c]) { cur = cur.son[c]; } else { return false; } } return true; } else { return false; } } isContainWord(str) { // 在字典樹(shù)中查找是否存在某字符串(不為前綴) if (this.isValid(word)) { var cur = this.root; for (var i = 0; i < word.length; i++) { var c = word.charCodeAt(i); c -= 48; //減少”0“的charCode if (cur.son[c]) { cur = cur.son[c]; } else { return false; } } return cur.isEnd; } else { return false; } } countPrefix(word) { // 統(tǒng)計(jì)以指定字符串為前綴的字符串?dāng)?shù)量 if (this.isValid(word)) { var cur = this.root; for (var i = 0; i < word.length; i++) { var c = word.charCodeAt(i); c -= 48; //減少”0“的charCode if (cur.son[c]) { cur = cur.son[c]; } else { return 0; } } return cur.numPass; } else { return 0; } } countWord(word) { // 統(tǒng)計(jì)某字符串出現(xiàn)的次數(shù)方法 if (this.isValid(word)) { var cur = this.root; for (var i = 0; i < word.length; i++) { var c = word.charCodeAt(i); c -= 48; //減少”0“的charCode if (cur.son[c]) { cur = cur.son[c]; } else { return 0; } } return cur.numEnd; } else { return 0; } }}class TrieNode { constructor() { this.numPass = 0;//有多少個(gè)單詞經(jīng)過(guò)這節(jié)點(diǎn) this.numEnd = 0; //有多少個(gè)單詞就此結(jié)束 this.son = []; this.value = ""; //value為單個(gè)字符 this.isEnd = false; }}我們重點(diǎn)看一下TrieNode與Trie的insert方法。 由于字典樹(shù)是主要用在詞頻統(tǒng)計(jì)，因此它的節(jié)點(diǎn)屬性比較多, 包含了numPass, numEnd但非常重要的屬性。
insert方法是用于插入重詞，在開(kāi)始之前，我們必須判定單詞是否合法，不能出現(xiàn) 特殊字符與空白。在插入時(shí)是打散了一個(gè)個(gè)字符放入每個(gè)節(jié)點(diǎn)中。每經(jīng)過(guò)一個(gè)節(jié)點(diǎn)都要修改numPass。
優(yōu)化
現(xiàn)在我們每個(gè)方法中，都有一個(gè)c=-48的操作，其實(shí)數(shù)字與大寫(xiě)字母與小寫(xiě)字母間其實(shí)還有其他字符的，這樣會(huì)造成無(wú)謂的空間的浪費(fèi)
// by 司徒正美getIndex(c){ if(c < 58){//48-57 return c - 48 }else if(c < 91){//65-90 return c - 65 + 11 }else {//> 97 return c - 97 + 26+ 11 } }然后相關(guān)方法將c-= 48改成c = this.getIndex(c)即可
測(cè)試
var trie = new Trie(); trie.insert("I"); trie.insert("Love"); trie.insert("China"); trie.insert("China"); trie.insert("China"); trie.insert("China"); trie.insert("China"); trie.insert("xiaoliang"); trie.insert("xiaoliang"); trie.insert("man"); trie.insert("handsome"); trie.insert("love"); trie.insert("Chinaha"); trie.insert("her"); trie.insert("know"); var map = {} trie.preTraversal(function(node, str){ if(node.isEnd){ map[str] = node.numEnd } }) for(var i in map){ console.log(i+" 出現(xiàn)了"+ map[i]+" 次") } console.log("包含Chin（包括本身）前綴的單詞及出現(xiàn)次數(shù)："); //console.log("China") var map = {} trie.preTraversal(function(node, str){ if(str.indexOf("Chin") === 0 && node.isEnd){ map[str] = node.numEnd } }) for(var i in map){ console.log(i+" 出現(xiàn)了"+ map[i]+" 次") }
Trie樹(shù)和其它數(shù)據(jù)結(jié)構(gòu)的比較
Trie樹(shù)與二叉搜索樹(shù)
二叉搜索樹(shù)應(yīng)該是我們最早接觸的樹(shù)結(jié)構(gòu)了，我們知道，數(shù)據(jù)規(guī)模為n時(shí)，二叉搜索樹(shù)插入、查找、刪除操作的時(shí)間復(fù)雜度通常只有O(log n)，最壞情況下整棵樹(shù)所有的節(jié)點(diǎn)都只有一個(gè)子節(jié)點(diǎn)，退變成一個(gè)線性表，此時(shí)插入、查找、刪除操作的時(shí)間復(fù)雜度是O(n)。
通常情況下，Trie樹(shù)的高度n要遠(yuǎn)大于搜索字符串的長(zhǎng)度m，故查找操作的時(shí)間復(fù)雜度通常為O(m)，最壞情況下的時(shí)間復(fù)雜度才為O(n)。很容易看出，Trie樹(shù)最壞情況下的查找也快過(guò)二叉搜索樹(shù)。
文中Trie樹(shù)都是拿字符串舉例的，其實(shí)它本身對(duì)key的適宜性是有嚴(yán)格要求的，如果key是浮點(diǎn)數(shù)的話，就可能導(dǎo)致整個(gè)Trie樹(shù)巨長(zhǎng)無(wú)比，節(jié)點(diǎn)可讀性也非常差，這種情況下是不適宜用Trie樹(shù)來(lái)保存數(shù)據(jù)的；而二叉搜索樹(shù)就不存在這個(gè)問(wèn)題。
Trie樹(shù)與Hash表
考慮一下Hash沖突的問(wèn)題。Hash表通常我們說(shuō)它的復(fù)雜度是O(1)，其實(shí)嚴(yán)格說(shuō)起來(lái)這是接近完美的Hash表的復(fù)雜度，另外還需要考慮到hash函數(shù)本身需要遍歷搜索字符串，復(fù)雜度是O(m)。在不同鍵被映射到“同一個(gè)位置”（考慮closed hashing，這“同一個(gè)位置”可以由一個(gè)普通鏈表來(lái)取代）的時(shí)候，需要進(jìn)行查找的復(fù)雜度取決于這“同一個(gè)位置”下節(jié)點(diǎn)的數(shù)目，因此，在最壞情況下，Hash表也是可以成為一張單向鏈表的。
Trie樹(shù)可以比較方便地按照key的字母序來(lái)排序（整棵樹(shù)先序遍歷一次就好了），這跟絕大多數(shù)Hash表是不同的（Hash表一般對(duì)于不同的key來(lái)說(shuō)是無(wú)序的）。
在較理想的情況下，Hash表可以以O(shè)(1)的速度迅速命中目標(biāo)，如果這張表非常大，需要放到磁盤(pán)上的話，Hash表的查找訪問(wèn)在理想情況下只需要一次即可；但是Trie樹(shù)訪問(wèn)磁盤(pán)的數(shù)目需要等于節(jié)點(diǎn)深度。
很多時(shí)候Trie樹(shù)比Hash表需要更多的空間，我們考慮這種一個(gè)節(jié)點(diǎn)存放一個(gè)字符的情況的話，在保存一個(gè)字符串的時(shí)候，沒(méi)有辦法把它保存成一個(gè)單獨(dú)的塊。Trie樹(shù)的節(jié)點(diǎn)壓縮可以明顯緩解這個(gè)問(wèn)題，后面會(huì)講到。
Trie樹(shù)的改進(jìn)
按位Trie樹(shù)（Bitwise Trie）
原理上和普通Trie樹(shù)差不多，只不過(guò)普通Trie樹(shù)存儲(chǔ)的最小單位是字符，但是Bitwise Trie存放的是位而已。位數(shù)據(jù)的存取由CPU指令一次直接實(shí)現(xiàn)，對(duì)于二進(jìn)制數(shù)據(jù)，它理論上要比普通Trie樹(shù)快。
節(jié)點(diǎn)壓縮。
分支壓縮：對(duì)于穩(wěn)定的Trie樹(shù)，基本上都是查找和讀取操作，完全可以把一些分支進(jìn)行壓縮。例如，前圖中最右側(cè)分支的inn可以直接壓縮成一個(gè)節(jié)點(diǎn)“inn”，而不需要作為一棵常規(guī)的子樹(shù)存在。Radix樹(shù)就是根據(jù)這個(gè)原理來(lái)解決Trie樹(shù)過(guò)深問(wèn)題的。
節(jié)點(diǎn)映射表：這種方式也是在Trie樹(shù)的節(jié)點(diǎn)可能已經(jīng)幾乎完全確定的情況下采用的，針對(duì)Trie樹(shù)中節(jié)點(diǎn)的每一個(gè)狀態(tài)，如果狀態(tài)總數(shù)重復(fù)很多的話，通過(guò)一個(gè)元素為數(shù)字的多維數(shù)組（比如Triple Array Trie）來(lái)表示，這樣存儲(chǔ)Trie樹(shù)本身的空間開(kāi)銷會(huì)小一些，雖說(shuō)引入了一張額外的映射表。
前綴樹(shù)的應(yīng)用
前綴樹(shù)還是很好理解，它的應(yīng)用也是非常廣的。
（1）字符串的快速檢索
字典樹(shù)的查詢時(shí)間復(fù)雜度是O(logL)，L是字符串的長(zhǎng)度。所以效率還是比較高的。字典樹(shù)的效率比hash表高。
（2）字符串排序
從上圖我們很容易看出單詞是排序的，先遍歷字母序在前面。減少了沒(méi)必要的公共子串。
（3）最長(zhǎng)公共前綴
inn和int的最長(zhǎng)公共前綴是in，遍歷字典樹(shù)到字母n時(shí)，此時(shí)這些單詞的公共前綴是in。
（4）自動(dòng)匹配前綴顯示后綴
我們使用辭典或者是搜索引擎的時(shí)候，輸入appl，后面會(huì)自動(dòng)顯示一堆前綴是appl的東東吧。那么有可能是通過(guò)字典樹(shù)實(shí)現(xiàn)的，前面也說(shuō)了字典樹(shù)可以找到公共前綴，我們只需要把剩余的后綴遍歷顯示出來(lái)即可。
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持武林網(wǎng)。
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
