Trie樹(shù)簡(jiǎn)介

Trie樹(shù)也稱(chēng)字典樹(shù)，在字符串的查找中優(yōu)勢(shì)比較明顯，適用于在海量數(shù)據(jù)中查找某個(gè)數(shù)據(jù)。因?yàn)門(mén)rie樹(shù)的查找時(shí)間和數(shù)據(jù)總量沒(méi)有關(guān)系，只和要查找的數(shù)據(jù)長(zhǎng)度有關(guān)。比如搜索引擎中熱度詞語(yǔ)的統(tǒng)計(jì)。除此之外也可用于將數(shù)據(jù)按字典序排序。
另外Trie樹(shù)是典型的空間換時(shí)間的數(shù)據(jù)結(jié)構(gòu)，構(gòu)建一顆Trie樹(shù)需要花費(fèi)比較大的內(nèi)存空間。

簡(jiǎn)單的Trie樹(shù)的實(shí)現(xiàn)有兩種方式，每個(gè)節(jié)點(diǎn)存儲(chǔ)一個(gè)子節(jié)點(diǎn)數(shù)組，或者用鏈表將每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)連接起來(lái)。
采用數(shù)組浪費(fèi)了大量的空間，因?yàn)樵赥rie樹(shù)使用的過(guò)程中不可能整個(gè)樹(shù)是滿(mǎn)的，所以數(shù)組中絕大多數(shù)的位置都是空閑的，空間得不到有效利用，但是因?yàn)閿?shù)組支持隨機(jī)訪問(wèn)，所以查找時(shí)效率很高
采用鏈表雖然節(jié)省了不少空間，但是在查找的過(guò)程中難以高效定位。

為了將兩者的優(yōu)點(diǎn)有效地結(jié)合起來(lái)，出現(xiàn)了一種僅用兩個(gè)線性數(shù)組描述的Trie樹(shù)，稱(chēng)為雙數(shù)組Trie樹(shù)（DAT）。兩個(gè)數(shù)組分別是base和check，理解它們的含義是學(xué)習(xí)DAT的關(guān)鍵。

base數(shù)組和check數(shù)組

base和check數(shù)組用于記錄節(jié)點(diǎn)和節(jié)點(diǎn)之間的關(guān)系，而自身的數(shù)據(jù)是通過(guò)在數(shù)組中的索引表示的。上文提到的Trie樹(shù)為每個(gè)節(jié)點(diǎn)都開(kāi)辟一定大小的數(shù)組來(lái)存儲(chǔ)孩子節(jié)點(diǎn)，但是開(kāi)辟的大小是事先規(guī)定好的，只能處理比如說(shuō)英文單詞這種簡(jiǎn)單的數(shù)據(jù)，而對(duì)于中文的處理不是很理想，雙數(shù)組Trie樹(shù)將每個(gè)數(shù)據(jù)都映射成一個(gè)整型數(shù)，既是數(shù)據(jù)的編碼又可用于在base和check數(shù)組中定位索引。

雙數(shù)組Trie樹(shù)中只有樹(shù)結(jié)構(gòu)意義上的節(jié)點(diǎn)，并無(wú)實(shí)際的表述，而節(jié)點(diǎn)與節(jié)點(diǎn)之間的關(guān)系僅是通過(guò)base和check記錄的。

編碼
在理解base和check數(shù)組之前，先了解一下有關(guān)編碼的事情。計(jì)算機(jī)在存儲(chǔ)數(shù)據(jù)時(shí)都是以二進(jìn)制的形式存儲(chǔ)的，
比如想要存儲(chǔ)字符’a’，并不是直接將’a’放入內(nèi)存，而是將其轉(zhuǎn)換成對(duì)應(yīng)的編碼（一個(gè)整型數(shù)97），隨后進(jìn)行進(jìn)制轉(zhuǎn)換存儲(chǔ)在內(nèi)存中。想要存儲(chǔ)中文”一”，也是需要要將其轉(zhuǎn)換成對(duì)應(yīng)的編碼（19968），然后再進(jìn)行存儲(chǔ)。
所以可以理解成，任何數(shù)據(jù)都有唯一的整數(shù)值與其對(duì)應(yīng)，這就是數(shù)據(jù)的編碼。目前比較流行的就是Unicode碼，可以有效處理中文字符。

起始索引begin
有了編碼的知識(shí)，首先想到的是將每個(gè)數(shù)據(jù)轉(zhuǎn)換成對(duì)應(yīng)的Code，然后這個(gè)Code就是這個(gè)數(shù)據(jù)在base和check中的下標(biāo)。但是沒(méi)辦法維護(hù)節(jié)點(diǎn)之間的關(guān)系，不過(guò)也不能說(shuō)這種想法是錯(cuò)的，至少對(duì)了一部分。原因是在base和check中的下標(biāo)不是只由Code組成，還需要一個(gè)起始索引begin，這個(gè)begin是在程序中需要計(jì)算的整數(shù)（目前先假設(shè)begin以求出）。
這個(gè)起始索引begin很像HashTable中的hash地址，在哈希表中，對(duì)于每個(gè)數(shù)據(jù)，都有一個(gè)確定的哈希散列函數(shù)將這個(gè)數(shù)據(jù)轉(zhuǎn)換成一個(gè)整數(shù)，這個(gè)整數(shù)就是數(shù)據(jù)在哈希表中的索引。
而對(duì)于雙數(shù)組而言，begin + Code組成了某個(gè)數(shù)據(jù)在base和check中的下標(biāo)。

base數(shù)組
但是你可能會(huì)問(wèn)，這樣也沒(méi)有父節(jié)點(diǎn)子節(jié)點(diǎn)的關(guān)系？
這就是base要解決的事情，考慮一下，每個(gè)數(shù)據(jù)都有一個(gè)唯一的begin作為它的起始索引，這個(gè)begin就好比于是數(shù)據(jù)的歸屬地。父節(jié)點(diǎn)有，孩子節(jié)點(diǎn)也同樣有，那么就可以利用base數(shù)組來(lái)存儲(chǔ)數(shù)據(jù)的孩子節(jié)點(diǎn)的起始索引child_begin。也就是說(shuō)，base[begin + code] = child_begin，這樣，在知道父節(jié)點(diǎn)的編碼，和父節(jié)點(diǎn)的起始索引begin后，就能找到它的孩子節(jié)點(diǎn)的起始索引child_begin，然后child_begin + child_code就是孩子節(jié)點(diǎn)在base和check數(shù)組中的下標(biāo)。

你可能又會(huì)問(wèn)，父節(jié)點(diǎn)會(huì)有多個(gè)孩子節(jié)點(diǎn)，而base中只存儲(chǔ)了一個(gè)begin？
具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)之間互為兄弟關(guān)系，只需要保證兄弟節(jié)點(diǎn)具有相同的起始索引begin就可以了，對(duì)嗎。

check數(shù)組
而對(duì)于check數(shù)組，它存儲(chǔ)的值是每個(gè)數(shù)據(jù)的起始索引begin，也就是說(shuō)
check[begin + code] = begin。它的作用在于判斷某個(gè)數(shù)據(jù)是否存在，比如說(shuō)現(xiàn)在知道了父節(jié)點(diǎn)的begin和code，想要判斷父節(jié)點(diǎn)有沒(méi)有表示某個(gè)數(shù)據(jù)的孩子節(jié)點(diǎn)，這個(gè)數(shù)據(jù)的編碼為child_code，那么就可以先求出父節(jié)點(diǎn)的孩子們的起始索引child_begin（利用base數(shù)組就可以了，child_begin = base[begin + code]）。求出之后考慮，如果那個(gè)數(shù)據(jù)存在，那么它就是父節(jié)點(diǎn)的孩子，它的起始索引就是child_begin，那么它的check數(shù)組中存儲(chǔ)的就應(yīng)該是child_begin。所以可以根據(jù)
check[child_begin + child_code]是否等于child_begin來(lái)判斷是否存在這個(gè)數(shù)據(jù)。

初始化操作

以下面的數(shù)據(jù)為例，任務(wù)是將這些數(shù)據(jù)放入Trie樹(shù)中。

//如下數(shù)據(jù) 一舉 一舉一動(dòng) 一舉成名 一舉成名天下知 萬(wàn)能 萬(wàn)能膠

每個(gè)字的編碼如下：

膠 名 動(dòng) 知 下 成 舉 一 能 天 萬(wàn) 33014 21517 21160 30693 19979 25104 20030 19968 33021 22825 19975

中文的編碼一般都比較大（小于65536），所以在創(chuàng)建一棵雙數(shù)組Trie樹(shù)時(shí)，需要為base和check開(kāi)辟很大的內(nèi)存。又因?yàn)閎egin的值也有可能很大，所以?xún)H僅開(kāi)辟65536是遠(yuǎn)遠(yuǎn)不夠的。
先考慮上面的問(wèn)題，應(yīng)該采用什么方法將這些數(shù)據(jù)添加到樹(shù)中，換言之就是放入base和check數(shù)組中呢。

根據(jù)base的含義，兄弟節(jié)點(diǎn)之間具有相同的起始索引begin，所以在添加的過(guò)程中，每次添加的節(jié)點(diǎn)們是互為兄弟的關(guān)系。

起始索引begin的選擇
對(duì)于互為兄弟的幾個(gè)數(shù)據(jù)，假設(shè)他們的編碼是a1,a2,a3,…,an。選擇begin的依據(jù)是需要滿(mǎn)足：

check[begin + a1] = 0; check[begin + a2] = 0; check[begin + a3] = 0;... check[begin + an] = 0；

check數(shù)組的賦值
初始化時(shí)check中的元素都為0，表示沒(méi)有位置被占用，check[i]不為0表示i這個(gè)索引位置已經(jīng)被其他的數(shù)據(jù)占用了，需要重新為這些兄弟數(shù)據(jù)找begin。而找到滿(mǎn)足上述條件的begin之后，需要將這些數(shù)據(jù)的check賦值為他們的起始索引begin，表示對(duì)應(yīng)索引位置已經(jīng)被占用。

check[begin + a1] = begin; check[begin + a2] = begin; check[begin + a3] = begin;... check[begin + an] = begin;

base數(shù)組的賦值
而base數(shù)組在什么時(shí)候賦值呢，base數(shù)組存儲(chǔ)的是孩子們的起始索引child_begin，也就是說(shuō)需要在為孩子們找到child_begin之后才能將父節(jié)點(diǎn)的base設(shè)置成child_begin。即

base[begin + code] = child_begin；

又因?yàn)槌跏蓟僮魇菑母?jié)點(diǎn)開(kāi)始的，所以很顯然需要利用遞歸的思想。

舉例
在上面的例子中，互為兄弟的字如下：

"一","萬(wàn)" 父節(jié)點(diǎn)為根節(jié)點(diǎn) "舉" 父節(jié)點(diǎn)為"一" "null", "一", "成" 父節(jié)點(diǎn)為"舉" "動(dòng)" 父節(jié)點(diǎn)為"一" "名" 父節(jié)點(diǎn)為"成" ... "能" 父節(jié)點(diǎn)為"萬(wàn)" ...

注意在計(jì)算兄弟節(jié)點(diǎn)時(shí)會(huì)多計(jì)算一個(gè)”null”，表示葉子節(jié)點(diǎn)，標(biāo)識(shí)從根節(jié)點(diǎn)到它的父節(jié)點(diǎn)為止表示的數(shù)據(jù)是一個(gè)完整的詞，也就是”一舉”是一個(gè)詞。
不同于其他的數(shù)據(jù)節(jié)點(diǎn)，子結(jié)點(diǎn)的編碼為0，在base中的值需要設(shè)為負(fù)數(shù)，在判斷是否存在某個(gè)詞時(shí)，需要利用這個(gè)負(fù)值判斷。
比如說(shuō)，想要判斷”一舉”是否在詞典中，只需要找到”舉”的孩子們的起始索引child_begin后，判斷base[child_begin + 0]是否是負(fù)數(shù)即可。
那在插入數(shù)據(jù)的過(guò)程中怎么判斷哪個(gè)節(jié)點(diǎn)是葉子結(jié)點(diǎn)呢。考慮一下，在插入數(shù)據(jù)的時(shí)候，每次都需要為某個(gè)數(shù)據(jù)生成它的孩子數(shù)據(jù)（像為”舉”找到”null”,”一”,”成”一樣），而葉子結(jié)點(diǎn)沒(méi)有孩子數(shù)據(jù)，所以可以根據(jù)找到的孩子是否為空進(jìn)行判斷。

初始時(shí)，為根節(jié)點(diǎn)的base和check賦值。根節(jié)點(diǎn)的下標(biāo)為0，base[0]表示孩子們的起始索引，初始化時(shí)設(shè)置為1.

base[0] = 1; check[1] = 0;

初始化操作流程：

先選取第一批互為兄弟的節(jié)點(diǎn)，”一”和”萬(wàn)”。

為它們尋找一個(gè)滿(mǎn)足條件的起始索引begin1，并改變二者的check.

找到”一”的孩子”舉”。

為”舉”尋找滿(mǎn)足條件的起始索引begin2，并改變check。

找”舉”的孩子們”null”,”一”,”成”。

為孩子們找到滿(mǎn)足條件的起始索引begin3。

找”null”的孩子，沒(méi)有找到，將”null”的base賦值為負(fù)數(shù)

找”一”的孩子”動(dòng)”。

….

當(dāng)找到最后的，遞歸到最后一層時(shí)，向上返回每次尋找的begin。

….

將”舉”的base設(shè)置為begin3，將”一”的base設(shè)置為begin2，將”0”的base設(shè)置為begin1。

然后再為”萬(wàn)”字進(jìn)行同樣的操作。

…

查詢(xún)操作

整個(gè)流程下來(lái)，所有的數(shù)據(jù)都在base和check中存儲(chǔ)。對(duì)于查詢(xún)操作，比如說(shuō)給定一個(gè)詞語(yǔ)，需要判斷這個(gè)詞語(yǔ)是否在Trie樹(shù)表示的詞典中，步驟如下：
1. 計(jì)算begin1（base[0])
2. 計(jì)算第一個(gè)字的編碼code1
3. 判斷第一個(gè)字是否存在，check[begin1 + code1] == begin1表示存在
4. 若存在，將begin賦值為第二個(gè)字的起始索引，begin2 = base[begin1 + code1]
5. 計(jì)算第二個(gè)字的編碼code2
6. 判斷第二個(gè)字是否存在，check[begin2 + code2] == begin2表示存在
7. 若存在，將begin賦值為第三個(gè)字的起始索引，begin3 = base[begin2 + code2]
8. …
9. 當(dāng)全部遍歷后，beginN表示最后一個(gè)字的孩子們的起始索引。判斷base[beginN + 0] <
0是否成立，成立就表示存在，否則表示不存在。

注：只要有一處check[begin + code] != begin就表示不存在，返回fasle

流程示例

下面以

一舉 一舉一動(dòng) 一舉成名 一舉成名天下知 萬(wàn)能 萬(wàn)能膠

為例，進(jìn)行初始化操作的說(shuō)明。

每個(gè)字的編碼如下：膠 名 動(dòng) 知 下 成 舉 一 能 天 萬(wàn) 33014 21517 21160 30693 19979 25104 20030 19968 33021 22825 19975

在處理完以”一”字開(kāi)頭的詞語(yǔ)后，繼續(xù)處理以”萬(wàn)”字開(kāi)頭的詞語(yǔ)。如果詞典中詞語(yǔ)有很多，則依次處理。
需要考慮的函數(shù)有

找到以某個(gè)字作為前綴字的字，比如說(shuō)處理完”舉”字，需要尋找”舉”的孩子”null”，”一”，”成”。

為互為兄弟關(guān)系的幾個(gè)字尋找滿(mǎn)足條件的起始索引begin。然后遞歸地進(jìn)行步驟1。當(dāng)遇到葉子節(jié)點(diǎn)時(shí)，將葉子節(jié)點(diǎn)的base設(shè)置成負(fù)數(shù)。每層遞歸返回本層的begin作為父節(jié)點(diǎn)的base值。

參考的博客
http://www.hankcs.com/program/java/%E5%8F%8C%E6%95%B0%E7%BB%84trie%E6%A0%91doublearraytriejava%E5%AE%9E%E7%8E%B0.html

總結(jié)

以上是生活随笔為你收集整理的数据结构-----基于双数组的Trie树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。