本篇文章為大家展示了使用javascript怎么實(shí)現(xiàn)一個(gè)trie前綴樹，內(nèi)容簡(jiǎn)明扼要并且容易理解，絕對(duì)能使你眼前一亮，通過這篇文章的詳細(xì)介紹希望你能有所收獲。
Trie樹（來自單詞retrieval），又稱前綴字，單詞查找樹，字典樹，是一種樹形結(jié)構(gòu)，是一種哈希樹的變種，是一種用于快速檢索的多叉樹結(jié)構(gòu)。
它的優(yōu)點(diǎn)是：大限度地減少無謂的字符串比較，查詢效率比哈希表高。
Trie的核心思想是空間換時(shí)間。利用字符串的公共前綴來降低查詢時(shí)間的開銷以達(dá)到提高效率的目的。
Trie樹也有它的缺點(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ì)
根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)外的每一個(gè)子節(jié)點(diǎn)都包含一個(gè)字符
從根節(jié)點(diǎn)到某一節(jié)點(diǎn)。路徑上經(jīng)過的字符連接起來，就是該節(jié)點(diǎn)對(duì)應(yīng)的字符串
每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符都不相同
程序?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)過它
} 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);
}
// 在字典樹中查找是否存在某字符串為前綴開頭的字符串(包括前綴字符串本身)
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) {
// 在字典樹中查找是否存在某字符串(不為前綴)
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)過這節(jié)點(diǎn)
this.numEnd = 0; //有多少個(gè)單詞就此結(jié)束
this.son = [];
this.value = ""; //value為單個(gè)字符
this.isEnd = false;
}
}我們重點(diǎn)看一下TrieNode與Trie的insert方法。 由于字典樹是主要用在詞頻統(tǒng)計(jì)，因此它的節(jié)點(diǎn)屬性比較多, 包含了numPass, numEnd但非常重要的屬性。
insert方法是用于插入重詞，在開始之前，我們必須判定單詞是否合法，不能出現(xiàn) 特殊字符與空白。在插入時(shí)是打散了一個(gè)個(gè)字符放入每個(gè)節(jié)點(diǎn)中。每經(jīng)過一個(gè)節(jié)點(diǎn)都要修改numPass。
優(yōu)化
現(xiàn)在我們每個(gè)方法中，都有一個(gè)c=-48的操作，其實(shí)數(shù)字與大寫字母與小寫字母間其實(shí)還有其他字符的，這樣會(huì)造成無謂的空間的浪費(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ù)據(jù)結(jié)構(gòu)的比較
Trie樹與二叉搜索樹
二叉搜索樹應(yīng)該是我們最早接觸的樹結(jié)構(gòu)了，我們知道，數(shù)據(jù)規(guī)模為n時(shí)，二叉搜索樹插入、查找、刪除操作的時(shí)間復(fù)雜度通常只有O(log n)，最壞情況下整棵樹所有的節(jié)點(diǎn)都只有一個(gè)子節(jié)點(diǎn)，退變成一個(gè)線性表，此時(shí)插入、查找、刪除操作的時(shí)間復(fù)雜度是O(n)。
通常情況下，Trie樹的高度n要遠(yuǎn)大于搜索字符串的長度m，故查找操作的時(shí)間復(fù)雜度通常為O(m)，最壞情況下的時(shí)間復(fù)雜度才為O(n)。很容易看出，Trie樹最壞情況下的查找也快過二叉搜索樹。
文中Trie樹都是拿字符串舉例的，其實(shí)它本身對(duì)key的適宜性是有嚴(yán)格要求的，如果key是浮點(diǎn)數(shù)的話，就可能導(dǎo)致整個(gè)Trie樹巨長無比，節(jié)點(diǎn)可讀性也非常差，這種情況下是不適宜用Trie樹來保存數(shù)據(jù)的；而二叉搜索樹就不存在這個(gè)問題。
Trie樹與Hash表
考慮一下Hash沖突的問題。Hash表通常我們說它的復(fù)雜度是O(1)，其實(shí)嚴(yán)格說起來這是接近完美的Hash表的復(fù)雜度，另外還需要考慮到hash函數(shù)本身需要遍歷搜索字符串，復(fù)雜度是O(m)。在不同鍵被映射到“同一個(gè)位置”（考慮closed hashing，這“同一個(gè)位置”可以由一個(gè)普通鏈表來取代）的時(shí)候，需要進(jìn)行查找的復(fù)雜度取決于這“同一個(gè)位置”下節(jié)點(diǎn)的數(shù)目，因此，在最壞情況下，Hash表也是可以成為一張單向鏈表的。
Trie樹可以比較方便地按照key的字母序來排序（整棵樹先序遍歷一次就好了），這跟絕大多數(shù)Hash表是不同的（Hash表一般對(duì)于不同的key來說是無序的）。
在較理想的情況下，Hash表可以以O(shè)(1)的速度迅速命中目標(biāo)，如果這張表非常大，需要放到磁盤上的話，Hash表的查找訪問在理想情況下只需要一次即可；但是Trie樹訪問磁盤的數(shù)目需要等于節(jié)點(diǎn)深度。
很多時(shí)候Trie樹比Hash表需要更多的空間，我們考慮這種一個(gè)節(jié)點(diǎn)存放一個(gè)字符的情況的話，在保存一個(gè)字符串的時(shí)候，沒有辦法把它保存成一個(gè)單獨(dú)的塊。Trie樹的節(jié)點(diǎn)壓縮可以明顯緩解這個(gè)問題，后面會(huì)講到。
Trie樹的改進(jìn)
按位Trie樹（Bitwise Trie）
原理上和普通Trie樹差不多，只不過普通Trie樹存儲(chǔ)的最小單位是字符，但是Bitwise Trie存放的是位而已。位數(shù)據(jù)的存取由CPU指令一次直接實(shí)現(xiàn)，對(duì)于二進(jìn)制數(shù)據(jù)，它理論上要比普通Trie樹快。
節(jié)點(diǎn)壓縮。
分支壓縮：對(duì)于穩(wěn)定的Trie樹，基本上都是查找和讀取操作，完全可以把一些分支進(jìn)行壓縮。例如，前圖中最右側(cè)分支的inn可以直接壓縮成一個(gè)節(jié)點(diǎn)“inn”，而不需要作為一棵常規(guī)的子樹存在。Radix樹就是根據(jù)這個(gè)原理來解決Trie樹過深問題的。
節(jié)點(diǎn)映射表：這種方式也是在Trie樹的節(jié)點(diǎn)可能已經(jīng)幾乎完全確定的情況下采用的，針對(duì)Trie樹中節(jié)點(diǎn)的每一個(gè)狀態(tài)，如果狀態(tài)總數(shù)重復(fù)很多的話，通過一個(gè)元素為數(shù)字的多維數(shù)組（比如Triple Array Trie）來表示，這樣存儲(chǔ)Trie樹本身的空間開銷會(huì)小一些，雖說引入了一張額外的映射表。
前綴樹的應(yīng)用
前綴樹還是很好理解，它的應(yīng)用也是非常廣的。
（1）字符串的快速檢索
字典樹的查詢時(shí)間復(fù)雜度是O(logL)，L是字符串的長度。所以效率還是比較高的。字典樹的效率比hash表高。
（2）字符串排序
從上圖我們很容易看出單詞是排序的，先遍歷字母序在前面。減少了沒必要的公共子串。
（3）最長公共前綴
inn和int的最長公共前綴是in，遍歷字典樹到字母n時(shí)，此時(shí)這些單詞的公共前綴是in。
（4）自動(dòng)匹配前綴顯示后綴
上述內(nèi)容就是使用javascript怎么實(shí)現(xiàn)一個(gè)trie前綴樹，你們學(xué)到知識(shí)或技能了嗎？如果還想學(xué)到更多技能或者豐富自己的知識(shí)儲(chǔ)備，歡迎關(guān)注創(chuàng)新互聯(lián)成都網(wǎng)站設(shè)計(jì)公司行業(yè)資訊頻道。
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。
