教你如何迅速秒殺99%的海量數(shù)據(jù)處理面試題密匙四、Trie樹(shù)/數(shù)據(jù)庫(kù)/倒排索

Trie樹(shù)

　　適用范圍：數(shù)據(jù)量大，重復(fù)多，但是數(shù)據(jù)種類小可以放入內(nèi)存
　　基本原理及要點(diǎn)：實(shí)現(xiàn)方式，節(jié)點(diǎn)孩子的表示方式
　　擴(kuò)展：壓縮實(shí)現(xiàn)。
　　問(wèn)題實(shí)例：

1. 有10個(gè)文件，每個(gè)文件1G，每個(gè)文件的每一行都存放的是用戶的query，每個(gè)文件的query都可能重復(fù)。要你按照query的頻度排序。
2. 1000萬(wàn)字符串，其中有些是相同的(重復(fù)),需要把重復(fù)的全部去掉，保留沒(méi)有重復(fù)的字符串。請(qǐng)問(wèn)怎么設(shè)計(jì)和實(shí)現(xiàn)？
3. 尋找熱門(mén)查詢：查詢串的重復(fù)度比較高，雖然總數(shù)是1千萬(wàn)，但如果除去重復(fù)后，不超過(guò)3百萬(wàn)個(gè)，每個(gè)不超過(guò)255字節(jié)。
4. 上面的第8題：一個(gè)文本文件，大約有一萬(wàn)行，每行一個(gè)詞，要求統(tǒng)計(jì)出其中最頻繁出現(xiàn)的前10個(gè)詞。其解決方法是：用trie樹(shù)統(tǒng)計(jì)每個(gè)詞出現(xiàn)的次數(shù)，時(shí)間復(fù)雜度是O(n*le)（le表示單詞的平準(zhǔn)長(zhǎng)度），然后是找出出現(xiàn)最頻繁的前10個(gè)詞。

    更多有關(guān)Trie樹(shù)的介紹，請(qǐng)參見(jiàn)此文：從Trie樹(shù)（字典樹(shù)）談到后綴樹(shù)。

數(shù)據(jù)庫(kù)索引
　　適用范圍：大數(shù)據(jù)量的增刪改查
　　基本原理及要點(diǎn)：利用數(shù)據(jù)的設(shè)計(jì)實(shí)現(xiàn)方法，對(duì)海量數(shù)據(jù)的增刪改查進(jìn)行處理。

    關(guān)于數(shù)據(jù)庫(kù)索引及其優(yōu)化，更多可參見(jiàn)此文：http://www.cnblogs.com/pkuoliver/archive/2011/08/17/mass-data-topic-7-index-and-optimize.html。同時(shí)，關(guān)于MySQL索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理，這里還有一篇很好的文章：http://www.codinglabs.org/html/theory-of-mysql-index.html。
倒排索引(Inverted index)
　　適用范圍：搜索引擎，關(guān)鍵字查詢
　　基本原理及要點(diǎn)：為何叫倒排索引？一種索引方法，被用來(lái)存儲(chǔ)在全文搜索下某個(gè)單詞在一個(gè)文檔或者一組文檔中的存儲(chǔ)位置的映射。
　以英文為例，下面是要被索引的文本：
    T0 = "it is what it is"
    T1 = "what is it"
    T2 = "it is a banana"
我們就能得到下面的反向文件索引：
    "a":      {2}
    "banana": {2}
    "is":     {0, 1, 2}
    "it":     {0, 1, 2}
    "what":   {0, 1}
　檢索的條件"what","is"和"it"將對(duì)應(yīng)集合的交集。
　　正向索引開(kāi)發(fā)出來(lái)用來(lái)存儲(chǔ)每個(gè)文檔的單詞的列表。正向索引的查詢往往滿足每個(gè)文檔有序頻繁的全文查詢和每個(gè)單詞在校驗(yàn)文檔中的驗(yàn)證這樣的查詢。在正向索引中，文檔占據(jù)了中心的位置，每個(gè)文檔指向了一個(gè)它所包含的索引項(xiàng)的序列。也就是說(shuō)文檔指向了它包含的那些單詞，而反向索引則是單詞指向了包含它的文檔，很容易看到這個(gè)反向的關(guān)系。
　　擴(kuò)展：
　　問(wèn)題實(shí)例：文檔檢索系統(tǒng)，查詢那些文件包含了某單詞，比如常見(jiàn)的學(xué)術(shù)論文的關(guān)鍵字搜索。

    關(guān)于倒排索引的應(yīng)用，更多請(qǐng)參見(jiàn)：第二十三、四章：楊氏矩陣查找，倒排索引關(guān)鍵詞Hash不重復(fù)編碼實(shí)踐，及第二十六章：基于給定的文檔生成倒排索引的編碼與實(shí)踐。