引言

咱們先來(lái)看一道面試題：一個(gè)文本文件，大約有一萬(wàn)行，每行一個(gè)詞，要求統(tǒng)計(jì)出其中最頻繁出現(xiàn)的前10個(gè)詞，請(qǐng)給出思想，給出時(shí)間復(fù)雜度分析。

之前在此文：海量數(shù)據(jù)處理面試題集錦與Bit-map詳解中給出的參考答案：用trie樹(shù)統(tǒng)計(jì)每個(gè)詞出現(xiàn)的次數(shù)，時(shí)間復(fù)雜度是O(n*le)（le表示單詞的平均長(zhǎng)度），然后是找出出現(xiàn)最頻繁的前10個(gè)詞。也可以用堆來(lái)實(shí)現(xiàn)（具體的操作可參考第三章、尋找最小的k個(gè)數(shù)），時(shí)間復(fù)雜度是O(n*lg10)。所以總的時(shí)間復(fù)雜度，是O(n*le)與O(n*lg10)中較大的哪一個(gè)。

本文第一部分，咱們就來(lái)了解了解這個(gè)Trie樹(shù)，然后自然而然過(guò)渡到第二部分、后綴樹(shù)，在此對(duì)這兩種樹(shù)權(quán)作此番闡述，以備不時(shí)之需，在需要的時(shí)候能手到擒來(lái)即可。ok，有任何問(wèn)題，歡迎不吝指正或賜教。謝謝。

第一部分、Trie樹(shù)

什么是Trie樹(shù)

Trie樹(shù)，又稱(chēng)單詞查找樹(shù)或鍵樹(shù)，是一種樹(shù)形結(jié)構(gòu)，是一種哈希樹(shù)的變種。典型應(yīng)用是用于統(tǒng)計(jì)和排序大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)。它的優(yōu)點(diǎn)是：最大限度地減少無(wú)謂的字符串比較，查詢(xún)效率比哈希表高。

Trie的核心思想是空間換時(shí)間。利用字符串的公共前綴來(lái)降低查詢(xún)時(shí)間的開(kāi)銷(xiāo)以達(dá)到提高效率的目的。

它有3個(gè)基本性質(zhì)：

  1. 根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)外每一個(gè)節(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è)在網(wǎng)上流傳頗廣的例子，如下：

題目：給你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樹(shù)，因?yàn)樵谀承┓矫嫠挠猛靖蟆１热缯f(shuō)對(duì)于某一個(gè)單詞，我們要詢(xún)問(wèn)它的前綴是否出現(xiàn)過(guò)。這樣hash就不好搞了，而用trie還是很簡(jiǎn)單。
現(xiàn)在回到例子中，如果我們用最傻的方法，對(duì)于每一個(gè)單詞，我們都要去查找它前面的單詞中是否有它。那么這個(gè)算法的復(fù)雜度就是O(n^2)。顯然對(duì)于 100000的范圍難以接受。現(xiàn)在我們換個(gè)思路想。假設(shè)我要查詢(xún)的單詞是abcd，那么在他前面的單詞中，以b，c，d，f之類(lèi)開(kāi)頭的我顯然不必考慮。而 只要找以a開(kāi)頭的中是否存在abcd就可以了。同樣的，在以a開(kāi)頭中的單詞中，我們只要考慮以b作為第二個(gè)字母的，一次次縮小范圍和提高針對(duì)性，這樣一個(gè) 樹(shù)的模型就漸漸清晰了。
好比假設(shè)有b，abc，abd，bcd，abcd，efg，hii 這6個(gè)單詞，我們構(gòu)建的樹(shù)就是如下圖這樣的：

（圖義：當(dāng)時(shí)第一次看到這幅圖的時(shí)候，便立馬感到此樹(shù)之不凡構(gòu)造了。單單從上幅圖便可窺知一二，好比大海搜人，立馬就能確定東南西北中的到底哪個(gè)方位，如此迅速縮小查找的范圍和提高查找的針對(duì)性，不失為一創(chuàng)舉）
對(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)我們查詢(xún)和插入可以一起完成（重點(diǎn)體會(huì)這個(gè)查詢(xún)和插入是如何一起完成的，稍后，下文具體解釋?zhuān)脮r(shí)間僅僅為單詞長(zhǎng)度，在這一個(gè)樣例，便是10。
我們可以看到，trie樹(shù)每一層的節(jié)點(diǎn)數(shù)是26^i級(jí)別的。所以為了節(jié)省空間。我們用動(dòng)態(tài)鏈表，或者用數(shù)組來(lái)模擬動(dòng)態(tài)。空間的花費(fèi)，不會(huì)超過(guò)單詞數(shù)×單詞長(zhǎng)度。

小結(jié)

ok，下面，咱們?cè)倏偨Y(jié)一下上述問(wèn)題：

已知n個(gè)由小寫(xiě)字母構(gòu)成的平均長(zhǎng)度為10的單詞,判斷其中是否存在某個(gè)串為另一個(gè)串的前綴子串。下面對(duì)比3種方法：

  1. 最容易想到的：即從字符串集中從頭往后搜，看每個(gè)字符串是否為字符串集中某個(gè)字符串的前綴，復(fù)雜度為O(n^2)。
  2. 使用hash：我們用hash存下所有字符串的所有的前綴子串，建立存有子串hash的復(fù)雜度為O(n*len)，而查詢(xún)的復(fù)雜度為O(n)* O(1)= O(n)。
  3. 使用trie：因?yàn)楫?dāng)查詢(xún)?nèi)缱址產(chǎn)bc是否為某個(gè)字符串的前綴時(shí)，顯然以b,c,d....等不是以a開(kāi)頭的字符串就不用查找了。所以建立trie的復(fù)雜度為O(n*len)，而建立+查詢(xún)?cè)趖rie中是可以同時(shí)執(zhí)行的，建立的過(guò)程也就可以成為查詢(xún)的過(guò)程，hash就不能實(shí)現(xiàn)這個(gè)功能。所以總的復(fù)雜度為O(n*len)，實(shí)際查詢(xún)的復(fù)雜度也只是O(len)。

解釋下上述方法3中所說(shuō)的為什么hash不能將建立與查詢(xún)同時(shí)執(zhí)行，而Trie樹(shù)卻可以：

  • 在hash中，例如有串：911，911456輸入，如果要同時(shí)執(zhí)行建立與查詢(xún)，過(guò)程就是查詢(xún)911，沒(méi)有，然后存入9、91、911； 查詢(xún)911456，沒(méi)有然后存入9114、91145、911456，而程序沒(méi)有記憶功能，并不知道911在輸入數(shù)據(jù)中出現(xiàn)過(guò)。所以用hash必須先存入 所有子串，然后for循環(huán)查詢(xún)。
  • 而trie樹(shù)中，存入911后，已經(jīng)記錄911為出現(xiàn)的字符串，在存入911456的過(guò)程中就能發(fā)現(xiàn)而輸出答案；倒過(guò)來(lái)亦可以，先存入911456，在存入911時(shí)，當(dāng)指針指向最后一個(gè)1時(shí)，程序會(huì)發(fā)現(xiàn)這個(gè)1已經(jīng)存在，說(shuō)明911必定是某個(gè)字符串的前綴。

至于，有關(guān)Trie樹(shù)的查找，插入等操作的實(shí)現(xiàn)代碼，網(wǎng)上遍地開(kāi)花且千篇一律，諸君盡可參考，想必不用我再做多余費(fèi)神。

查詢(xún)

Trie樹(shù)是簡(jiǎn)單但實(shí)用的數(shù)據(jù)結(jié)構(gòu)，通常用于實(shí)現(xiàn)字典查詢(xún)。我們做即時(shí)響應(yīng)用戶(hù)輸入的AJAX搜索框時(shí)，就是Trie開(kāi)始。本質(zhì)上，Trie是一顆 存儲(chǔ)多個(gè)字符串的樹(shù)。相鄰節(jié)點(diǎn)間的邊代表一個(gè)字符，這樣樹(shù)的每條分支代表一則子串，而樹(shù)的葉節(jié)點(diǎn)則代表完整的字符串。和普通樹(shù)不同的地方是，相同的字符串 前綴共享同一條分支。下面，再舉一個(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"的邊。

查詢(xún)操縱非常簡(jiǎn)單。比如要查找int，順著路徑i -> in -> int就找到了。

搭建Trie的基本算法也很簡(jiǎn)單，無(wú)非是逐一把每則單詞的每個(gè)字母插入Trie。插入前先看前綴是否存在。如果存在，就共享，否則創(chuàng)建對(duì)應(yīng)的節(jié)點(diǎn)和邊。比如要插入單詞add，就有下面幾步：

  1. 考察前綴"a"，發(fā)現(xiàn)邊a已經(jīng)存在。于是順著邊a走到節(jié)點(diǎn)a。
  2. 考察剩下的字符串"dd"的前綴"d"，發(fā)現(xiàn)從節(jié)點(diǎn)a出發(fā)，已經(jīng)有邊d存在。于是順著邊d走到節(jié)點(diǎn)ad
  3. 考察最后一個(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。

應(yīng)用

除了本文引言處所述的問(wèn)題能應(yīng)用Trie樹(shù)解決之外，Trie樹(shù)還能解決下述問(wèn)題（節(jié)選自此文：海量數(shù)據(jù)處理面試題集錦與Bit-map詳解）：

  • 3、有一個(gè)1G大小的一個(gè)文件，里面每一行是一個(gè)詞，詞的大小不超過(guò)16字節(jié)，內(nèi)存限制大小是1M。返回頻數(shù)最高的100個(gè)詞。
  • 9、1000萬(wàn)字符串，其中有些是重復(fù)的，需要把重復(fù)的全部去掉，保留沒(méi)有重復(fù)的字符串。請(qǐng)?jiān)趺丛O(shè)計(jì)和實(shí)現(xiàn)？
  • 10、 一個(gè)文本文件，大約有一萬(wàn)行，每行一個(gè)詞，要求統(tǒng)計(jì)出其中最頻繁出現(xiàn)的前10個(gè)詞，請(qǐng)給出思想，給出時(shí)間復(fù)雜度分析。
  • 13、尋找熱門(mén)查詢(xún)：搜索引擎會(huì)通過(guò)日志文件把用戶(hù)每次檢索使用的所有檢索串都記錄下來(lái)，每個(gè)查詢(xún)串的長(zhǎng)度為1-255字節(jié)。假設(shè)目前有 一千萬(wàn)個(gè)記錄，這些查詢(xún)串的重復(fù)讀比較高，雖然總數(shù)是1千萬(wàn)，但是如果去除重復(fù)和，不超過(guò)3百萬(wàn)個(gè)。一個(gè)查詢(xún)串的重復(fù)度越高，說(shuō)明查詢(xún)它的用戶(hù)越多，也就 越熱門(mén)。請(qǐng)你統(tǒng)計(jì)最熱門(mén)的10個(gè)查詢(xún)串，要求使用的內(nèi)存不能超過(guò)1G。
    (1) 請(qǐng)描述你解決這個(gè)問(wèn)題的思路；
    (2) 請(qǐng)給出主要的處理流程，算法，以及算法的復(fù)雜度。

有了Trie，后綴樹(shù)就容易理解了。本文接下來(lái)的第二部分，介紹后綴樹(shù)。

第二部分、后綴樹(shù)

先說(shuō)說(shuō)后綴的定義，顧名思義，通俗點(diǎn)來(lái)說(shuō)，就是所謂后綴就是后面尾巴的意思。比如說(shuō)給定一長(zhǎng)度為n的字符串S=S1S2..Si..Sn，和整數(shù)i，1 <= i <= n，子串SiSi+1...Sn便都是字符串S的后綴。

以字符串S=XMADAMYX為例，它的長(zhǎng)度為8，所以S[1..8], S[2..8], ... , S[8..8]都算S的后綴，我們一般還把空字串也算成后綴。這樣，我們一共有如下后綴。對(duì)于后綴S[i..n]，我們說(shuō)這項(xiàng)后綴起始于i。

S[1..8], XMADAMYX， 也就是字符串本身，起始位置為1
S[2..8], MADAMYX，起始位置為2
S[3..8], ADAMYX，起始位置為3
S[4..8], DAMYX，起始位置為4
S[5..8], AMYX，起始位置為5
S[6..8], MYX，起始位置為6
S[7..8], YX，起始位置為7
S[8..8], X，起始位置為8
空字串。記為$。

而后綴樹(shù)，就是包含一則字符串所有后綴的壓縮Trie。把上面的后綴加入Trie后，我們得到下面的結(jié)構(gòu)：

仔細(xì)觀察上圖，我們可以看到不少值得壓縮的地方。比如藍(lán)框標(biāo)注的分支都是獨(dú)苗，沒(méi)有必要用單獨(dú)的節(jié)點(diǎn)同邊表示。如果我們?cè)试S任意一條邊里包含多個(gè)字 母，就可以把這種沒(méi)有分叉的路徑壓縮到一條邊。另外每條邊已經(jīng)包含了足夠的后綴信息，我們就不用再給節(jié)點(diǎn)標(biāo)注字符串信息了。我們只需要在葉節(jié)點(diǎn)上標(biāo)注上每 項(xiàng)后綴的起始位置。于是我們得到下圖：

這樣的結(jié)構(gòu)丟失了某些后綴。比如后綴X在上圖中消失了，因?yàn)樗檬亲址甔MADAMYX的前綴。為了避免這種情況，我們也規(guī)定每項(xiàng)后綴不能是其 它后綴的前綴。要解決這個(gè)問(wèn)題其實(shí)挺簡(jiǎn)單，在待處理的子串后加一坨空字串就行了。例如我們處理XMADAMYX前，先把XMADAMYX變?yōu)? XMADAMYX$，于是就得到suffix tree樂(lè)。

那后綴樹(shù)同最長(zhǎng)回文有什么關(guān)系呢？我們得先知道兩坨坨簡(jiǎn)單概念：

最低共有祖先，LCA（Lowest Common Ancestor)，也就是任意兩節(jié)點(diǎn)（多個(gè)也行）最長(zhǎng)的共有前綴。比如下圖中，節(jié)點(diǎn)7同節(jié)點(diǎn)10的共同祖先是節(jié)點(diǎn)1與借點(diǎn)，但最低共同祖先是5。 查找LCA的算法是O(1)的復(fù)雜度，這年頭少見(jiàn)。代價(jià)是需要對(duì)后綴樹(shù)做復(fù)雜度為O(n)的預(yù)處理。

廣 義后綴樹(shù)(Generalized Suffix Tree)。傳統(tǒng)的后綴樹(shù)處理一坨單詞的所有后綴。廣義后綴樹(shù)存儲(chǔ)任意多個(gè)單詞的所有后綴。例如下圖是單詞XMADAMYX與XYMADAMX的廣義后綴 樹(shù)。注意我們需要區(qū)分不同單詞的后綴，所以葉節(jié)點(diǎn)用不同的特殊符號(hào)與后綴位置配對(duì)。


轉(zhuǎn)自：http://www.kuqin.com/algorithm/20111023/313292.html