引言

咱們先來看一道面試題：一個文本文件，大約有一萬行，每行一個詞，要求統計出其中最頻繁出現的前10個詞，請給出思想，給出時間復雜度分析。

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

本文第一部分，咱們就來了解了解這個Trie樹，然后自然而然過渡到第二部分、后綴樹，在此對這兩種樹權作此番闡述，以備不時之需，在需要的時候能手到擒來即可。ok，有任何問題，歡迎不吝指正或賜教。謝謝。

第一部分、Trie樹

什么是Trie樹

Trie樹，又稱單詞查找樹或鍵樹，是一種樹形結構，是一種哈希樹的變種。典型應用是用于統計和排序大量的字符串（但不僅限于字符串），所以經常被搜索引擎系統用于文本詞頻統計。它的優點是：最大限度地減少無謂的字符串比較，查詢效率比哈希表高。

Trie的核心思想是空間換時間。利用字符串的公共前綴來降低查詢時間的開銷以達到提高效率的目的。

它有3個基本性質：

  1. 根節點不包含字符，除根節點外每一個節點都只包含一個字符。
  2. 從根節點到某一節點，路徑上經過的字符連接起來，為該節點對應的字符串。
  3. 每個節點的所有子節點包含的字符都不相同。

舉例

舉個在網上流傳頗廣的例子，如下：

題目：給你100000個長度不超過10的單詞。對于每一個單詞，我們要判斷他出沒出現過，如果出現了，求第一次出現在第幾個位置。
分析：這題當然可以用hash來解決，但是本文重點介紹的是trie樹，因為在某些方面它的用途更大。比如說對于某一個單詞，我們要詢問它的前綴是否出現過。這樣hash就不好搞了，而用trie還是很簡單。
現在回到例子中，如果我們用最傻的方法，對于每一個單詞，我們都要去查找它前面的單詞中是否有它。那么這個算法的復雜度就是O(n^2)。顯然對于 100000的范圍難以接受。現在我們換個思路想。假設我要查詢的單詞是abcd，那么在他前面的單詞中，以b，c，d，f之類開頭的我顯然不必考慮。而 只要找以a開頭的中是否存在abcd就可以了。同樣的，在以a開頭中的單詞中，我們只要考慮以b作為第二個字母的，一次次縮小范圍和提高針對性，這樣一個 樹的模型就漸漸清晰了。
好比假設有b，abc，abd，bcd，abcd，efg，hii 這6個單詞，我們構建的樹就是如下圖這樣的：

（圖義：當時第一次看到這幅圖的時候，便立馬感到此樹之不凡構造了。單單從上幅圖便可窺知一二，好比大海搜人，立馬就能確定東南西北中的到底哪個方位，如此迅速縮小查找的范圍和提高查找的針對性，不失為一創舉）
對于每一個節點，從根遍歷到他的過程就是一個單詞，如果這個節點被標記為紅色，就表示這個單詞存在，否則不存在。
那么，對于一個單詞，我只要順著他從跟走到對應的節點，再看這個節點是否被標記為紅色就可以知道它是否出現過了。把這個節點標記為紅色，就相當于插入了這個單詞。
這樣一來我們查詢和插入可以一起完成（重點體會這個查詢和插入是如何一起完成的，稍后，下文具體解釋），所用時間僅僅為單詞長度，在這一個樣例，便是10。
我們可以看到，trie樹每一層的節點數是26^i級別的。所以為了節省空間。我們用動態鏈表，或者用數組來模擬動態。空間的花費，不會超過單詞數×單詞長度。

小結

ok，下面，咱們再總結一下上述問題：

已知n個由小寫字母構成的平均長度為10的單詞,判斷其中是否存在某個串為另一個串的前綴子串。下面對比3種方法：

  1. 最容易想到的：即從字符串集中從頭往后搜，看每個字符串是否為字符串集中某個字符串的前綴，復雜度為O(n^2)。
  2. 使用hash：我們用hash存下所有字符串的所有的前綴子串，建立存有子串hash的復雜度為O(n*len)，而查詢的復雜度為O(n)* O(1)= O(n)。
  3. 使用trie：因為當查詢如字符串abc是否為某個字符串的前綴時，顯然以b,c,d....等不是以a開頭的字符串就不用查找了。所以建立trie的復雜度為O(n*len)，而建立+查詢在trie中是可以同時執行的，建立的過程也就可以成為查詢的過程，hash就不能實現這個功能。所以總的復雜度為O(n*len)，實際查詢的復雜度也只是O(len)。

解釋下上述方法3中所說的為什么hash不能將建立與查詢同時執行，而Trie樹卻可以：

  • 在hash中，例如有串：911，911456輸入，如果要同時執行建立與查詢，過程就是查詢911，沒有，然后存入9、91、911； 查詢911456，沒有然后存入9114、91145、911456，而程序沒有記憶功能，并不知道911在輸入數據中出現過。所以用hash必須先存入 所有子串，然后for循環查詢。
  • 而trie樹中，存入911后，已經記錄911為出現的字符串，在存入911456的過程中就能發現而輸出答案；倒過來亦可以，先存入911456，在存入911時，當指針指向最后一個1時，程序會發現這個1已經存在，說明911必定是某個字符串的前綴。

至于，有關Trie樹的查找，插入等操作的實現代碼，網上遍地開花且千篇一律，諸君盡可參考，想必不用我再做多余費神。

查詢

Trie樹是簡單但實用的數據結構，通常用于實現字典查詢。我們做即時響應用戶輸入的AJAX搜索框時，就是Trie開始。本質上，Trie是一顆 存儲多個字符串的樹。相鄰節點間的邊代表一個字符，這樣樹的每條分支代表一則子串，而樹的葉節點則代表完整的字符串。和普通樹不同的地方是，相同的字符串 前綴共享同一條分支。下面，再舉一個例子。給出一組單詞，inn, int, at, age, adv, ant, 我們可以得到下面的Trie：

可以看出：

  • 每條邊對應一個字母。
  • 每個節點對應一項前綴。葉節點對應最長前綴，即單詞本身。
  • 單詞inn與單詞int有共同的前綴“in”, 因此他們共享左邊的一條分支，root->i->in。同理，ate, age, adv, 和ant共享前綴"a"，所以他們共享從根節點到節點"a"的邊。

查詢操縱非常簡單。比如要查找int，順著路徑i -> in -> int就找到了。

搭建Trie的基本算法也很簡單，無非是逐一把每則單詞的每個字母插入Trie。插入前先看前綴是否存在。如果存在，就共享，否則創建對應的節點和邊。比如要插入單詞add，就有下面幾步：

  1. 考察前綴"a"，發現邊a已經存在。于是順著邊a走到節點a。
  2. 考察剩下的字符串"dd"的前綴"d"，發現從節點a出發，已經有邊d存在。于是順著邊d走到節點ad
  3. 考察最后一個字符"d"，這下從節點ad出發沒有邊d了，于是創建節點ad的子節點add，并把邊ad->add標記為d。

應用

除了本文引言處所述的問題能應用Trie樹解決之外，Trie樹還能解決下述問題（節選自此文：海量數據處理面試題集錦與Bit-map詳解）：

  • 3、有一個1G大小的一個文件，里面每一行是一個詞，詞的大小不超過16字節，內存限制大小是1M。返回頻數最高的100個詞。
  • 9、1000萬字符串，其中有些是重復的，需要把重復的全部去掉，保留沒有重復的字符串。請怎么設計和實現？
  • 10、 一個文本文件，大約有一萬行，每行一個詞，要求統計出其中最頻繁出現的前10個詞，請給出思想，給出時間復雜度分析。
  • 13、尋找熱門查詢：搜索引擎會通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來，每個查詢串的長度為1-255字節。假設目前有 一千萬個記錄，這些查詢串的重復讀比較高，雖然總數是1千萬，但是如果去除重復和，不超過3百萬個。一個查詢串的重復度越高，說明查詢它的用戶越多，也就 越熱門。請你統計最熱門的10個查詢串，要求使用的內存不能超過1G。
    (1) 請描述你解決這個問題的思路；
    (2) 請給出主要的處理流程，算法，以及算法的復雜度。

有了Trie，后綴樹就容易理解了。本文接下來的第二部分，介紹后綴樹。

第二部分、后綴樹

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

以字符串S=XMADAMYX為例，它的長度為8，所以S[1..8], S[2..8], ... , S[8..8]都算S的后綴，我們一般還把空字串也算成后綴。這樣，我們一共有如下后綴。對于后綴S[i..n]，我們說這項后綴起始于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
空字串。記為$。

而后綴樹，就是包含一則字符串所有后綴的壓縮Trie。把上面的后綴加入Trie后，我們得到下面的結構：

仔細觀察上圖，我們可以看到不少值得壓縮的地方。比如藍框標注的分支都是獨苗，沒有必要用單獨的節點同邊表示。如果我們允許任意一條邊里包含多個字 母，就可以把這種沒有分叉的路徑壓縮到一條邊。另外每條邊已經包含了足夠的后綴信息，我們就不用再給節點標注字符串信息了。我們只需要在葉節點上標注上每 項后綴的起始位置。于是我們得到下圖：

這樣的結構丟失了某些后綴。比如后綴X在上圖中消失了，因為它正好是字符串XMADAMYX的前綴。為了避免這種情況，我們也規定每項后綴不能是其 它后綴的前綴。要解決這個問題其實挺簡單，在待處理的子串后加一坨空字串就行了。例如我們處理XMADAMYX前，先把XMADAMYX變為 XMADAMYX$，于是就得到suffix tree樂。

那后綴樹同最長回文有什么關系呢？我們得先知道兩坨坨簡單概念：

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

廣 義后綴樹(Generalized Suffix Tree)。傳統的后綴樹處理一坨單詞的所有后綴。廣義后綴樹存儲任意多個單詞的所有后綴。例如下圖是單詞XMADAMYX與XYMADAMX的廣義后綴 樹。注意我們需要區分不同單詞的后綴，所以葉節點用不同的特殊符號與后綴位置配對。


轉自：http://www.kuqin.com/algorithm/20111023/313292.html