轉：6.1海量數據處理

本文轉自看云，原文地址請移步：https://www.kancloud.cn/kancloud/the-art-of-programming/41608

偶然閑游，偶遇某一站點，發現這里寫的關于海量數據處理相關的思路還挺不錯，所以在這里采摘收藏,如有侵權之處還請評論區或者站內消息告知。

---

本文導讀：

所謂海量數據處理，是指基于海量數據的存儲、處理、和操作。正因為數據量太大，所以導致要么無法在較短時間內迅速解決，要么無法一次性裝入內存。

事實上，針對時間問題，可以采用巧妙的算法搭配合適的數據結構（如布隆過濾器、哈希、位圖、堆、數據庫、倒排索引、Trie樹）來解決；而對于空間問題，可以采取分而治之（哈希映射）的方法，也就是說，把規模大的數據轉化為規模小的，從而各個擊破。

此外，針對常說的單機及集群問題，通俗來講，單機就是指處理裝載數據的機器有限（只要考慮CPU、內存、和硬盤之間的數據交互），而集群的意思是指機器有多臺，適合分布式處理或并行計算，更多考慮節點與節點之間的數據交互。

一般說來，處理海量數據問題，有以下十種典型方法：

• 1.哈希分治；
• 2.simhash算法；
• 3.外排序；
• 4.MapReduce；
• 5.多層劃分；
• 6.位圖；
• 7.布隆過濾器；
• 8.Trie樹；
• 9.數據庫；
• 10.倒排索引。

受理論之限，本章將摒棄絕大部分的細節，只談方法和模式論，注重用最通俗、最直白的語言闡述相關問題。最后，有一點必須強調的是，全章行文是基于面試題的分析基礎之上的，具體實踐過程中，還得視具體情況具體分析，且各個場景下需要考慮的細節也遠比本章所描述的任何一種解決方案復雜得多。

---

?6.1 關聯式容器

一般來說，STL容器分為：

• 序列式容器(vector/list/deque/stack/queue/heap)，和關聯式容器。
  • 其中，關聯式容器又分為set(集合)和map(映射表)兩大類，以及這兩大類的衍生體multiset(多鍵集合)和multimap(多鍵映射表)，這些容器均以RB-tree（red-black tree, 紅黑樹）完成。
  • 此外，還有第3類關聯式容器，如hashtable(散列表)，以及以hashtable為底層機制完成的hash_set(散列集合)/hash_map(散列映射表)/hash_multiset(散列多鍵集合)/hash_multimap(散列多鍵映射表)。也就是說，set/map/multiset/multimap都內含一個RB-tree，而hash_set/hash_map/hash_multiset/hash_multimap都內含一個hashtable。

所謂關聯式容器，類似關聯式數據庫，每筆數據或每個元素都有一個鍵值(key)和一個實值(value)，即所謂的Key-Value(鍵-值對)。當元素被插入到關聯式容器中時，容器內部結構(RB-tree/hashtable)便依照其鍵值大小，以某種特定規則將這個元素放置于適當位置。

包括在非關聯式數據庫中，比如，在MongoDB內，文檔(document)是最基本的數據組織形式，每個文檔也是以Key-Value（鍵-值對）的方式組織起來。一個文檔可以有多個Key-Value組合，每個Value可以是不同的類型，比如String、Integer、List等等。

{ "name" : "July",  
"sex" : "male",  
"age" : 23 } 

set/map/multiset/multimap

set，同map一樣，所有元素都會根據元素的鍵值自動被排序，因為set/map兩者的所有各種操作，都只是轉而調用RB-tree的操作行為，不過，值得注意的是，兩者都不允許兩個元素有相同的鍵值。

不同的是：set的元素不像map那樣可以同時擁有實值(value)和鍵值(key)，set元素的鍵值就是實值，實值就是鍵值，而map的所有元素都是pair，同時擁有實值(value)和鍵值(key)，pair的第一個元素被視為鍵值，第二個元素被視為實值。

至于multiset/multimap，他們的特性及用法和set/map完全相同，唯一的差別就在于它們允許鍵值重復，即所有的插入操作基于RB-tree的insert_equal()而非insert_unique()。

hash_set/hash_map/hash_multiset/hash_multimap

hash_set/hash_map，兩者的一切操作都是基于hashtable之上。不同的是，hash_set同set一樣，同時擁有實值和鍵值，且實質就是鍵值，鍵值就是實值，而hash_map同map一樣，每一個元素同時擁有一個實值(value)和一個鍵值(key)，所以其使用方式，和上面的map基本相同。但由于hash_set/hash_map都是基于hashtable之上，所以不具備自動排序功能。為什么？因為hashtable沒有自動排序功能。

至于hash_multiset/hash_multimap的特性與上面的multiset/multimap完全相同，唯一的差別就是它們hash_multiset/hash_multimap的底層實現機制是hashtable（而multiset/multimap，上面說了，底層實現機制是RB-tree），所以它們的元素都不會被自動排序，不過也都允許鍵值重復。

所以，綜上，說白了，什么樣的結構決定其什么樣的性質，因為set/map/multiset/multimap都是基于RB-tree之上，所以有自動排序功能，而hash_set/hash_map/hash_multiset/hash_multimap都是基于hashtable之上，所以不含有自動排序功能，至于加個前綴multi_無非就是允許鍵值重復而已。

---

?

?6.2 分而治之

方法介紹

對于海量數據而言，由于無法一次性裝進內存處理，導致我們不得不把海量的數據通過hash映射分割成相應的小塊數據，然后再針對各個小塊數據通過hash_map進行統計或其它操作。

那什么是hash映射呢？簡單來說，就是為了便于計算機在有限的內存中處理big數據，我們通過一種映射散列的方式讓數據均勻分布在對應的內存位置(如大數據通過取余的方式映射成小數存放在內存中，或大文件映射成多個小文件)，而這個映射散列方式便是我們通常所說的hash函數，設計的好的hash函數能讓數據均勻分布而減少沖突。

問題實例

1、海量日志數據，提取出某日訪問百度次數最多的那個IP

分析：百度作為國內第一大搜索引擎，每天訪問它的IP數量巨大，如果想一次性把所有IP數據裝進內存處理，則內存容量明顯不夠，故針對數據太大，內存受限的情況，可以把大文件轉化成（取模映射）小文件，從而大而化小，逐個處理。

換言之，先映射，而后統計，最后排序。

解法：具體分為以下3個步驟

• 1.分而治之/hash映射
  • 首先把這一天訪問百度日志的所有IP提取出來，然后逐個寫入到一個大文件中，接著采用映射的方法，比如%1000，把整個大文件映射為1000個小文件。
• 2.hash_map統計
  • 當大文件轉化成了小文件，那么我們便可以采用hash_map(ip, value)來分別對1000個小文件中的IP進行頻率統計，再找出每個小文件中出現頻率最大的IP。
• 3.堆/快速排序
  • 統計出1000個頻率最大的IP后，依據各自頻率的大小進行排序(可采取堆排序)，找出那個頻率最大的IP，即為所求。

注：Hash取模是一種等價映射，不會存在同一個元素分散到不同小文件中去的情況，即這里采用的是%1000算法，那么同一個IP在hash后，只可能落在同一個文件中，不可能被分散的。

2、尋找熱門查詢，300萬個查詢字符串中統計最熱門的10個查詢

原題：搜索引擎會通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來，每個查詢串的長度為1-255字節。假設目前有一千萬個記錄，請你統計最熱門的10個查詢串，要求使用的內存不能超過1G。

分析：這些查詢串的重復度比較高，雖然總數是1千萬，但如果除去重復后，不超過3百萬個。一個查詢串的重復度越高，說明查詢它的用戶越多，也就是越熱門。

由上面第1題，我們知道，數據大則劃為小的，例如一億個ip求Top 10，可先%1000將ip分到1000個小文件中去，并保證一種ip只出現在一個文件中，再對每個小文件中的ip進行hash_map統計并按數量排序，最后歸并或者最小堆依次處理每個小文件的top10以得到最后的結果。

但對于本題，數據規模比較小，能一次性裝入內存。因為根據題目描述，雖然有一千萬個Query，但是由于重復度比較高，故去除重復后，事實上只有300萬的Query，每個Query255Byte，因此我們可以考慮把他們都放進內存中去（300萬個字符串假設沒有重復，都是最大長度，那么最多占用內存3M*1K/4=0.75G。所以可以將所有字符串都存放在內存中進行處理）。

所以我們放棄分而治之/hash映射的步驟，直接上hash_map統計，然后排序。So，針對此類典型的TOP K問題，采取的對策往往是：hash_map + 堆。

解法：

• 1.hash_map統計
  • 先對這批海量數據預處理。具體方法是：維護一個Key為Query字串，Value為該Query出現次數的hash_map，即hash_map(Query, Value)，每次讀取一個Query，如果該字串不在Table中，那么加入該字串，并將Value值設為1；如果該字串在Table中，那么將該字串的計數加1 即可。最終我們在O(N)的時間復雜度內用hash_map完成了統計；
• 2.堆排序
  • 借助堆這個數據結構，找出Top K，時間復雜度為N‘logK。即借助堆結構，我們可以在log量級的時間內查找和調整/移動。因此，維護一個K(該題目中是10)大小的小根堆，然后遍歷300萬的Query，分別和根元素進行對比。所以，我們最終的時間復雜度是：O(n) + N' * O(logk），其中，N為1000萬，N’為300萬。

關于第2步堆排序，可以維護k個元素的最小堆，即用容量為k的最小堆存儲最先遍歷到的k個數，并假設它們即是最大的k個數，建堆費時O（k），并調整堆(費時O(logk))后，有k1>k2>...kmin（kmin設為小頂堆中最小元素）。繼續遍歷數列，每次遍歷一個元素x，與堆頂元素比較，若x>kmin，則更新堆（x入堆，用時logk），否則不更新堆。這樣下來，總費時O（k_logk+（n-k）_logk）=O（n*logk）。此方法得益于在堆中，查找等各項操作時間復雜度均為logk。

當然，你也可以采用trie樹，關鍵字域存該查詢串出現的次數，沒有出現為0。最后用10個元素的最小推來對出現頻率進行排序。

3、有一個1G大小的一個文件，里面每一行是一個詞，詞的大小不超過16字節，內存限制大小是1M。返回頻數最高的100個詞

解法：

• 1.分而治之/hash映射
  • 順序讀取文件，對于每個詞x，取hash(x)%5000，然后把該值存到5000個小文件（記為x0,x1,...x4999）中。這樣每個文件大概是200k左右。當然，如果其中有的小文件超過了1M大小，還可以按照類似的方法繼續往下分，直到分解得到的小文件的大小都不超過1M。
• 2.hash_map統計
  • 對每個小文件，采用trie樹/hash_map等統計每個文件中出現的詞以及相應的頻率。
• 3.堆/歸并排序
  • 取出出現頻率最大的100個詞（可以用含100個結點的最小堆）后，再把100個詞及相應的頻率存入文件，這樣又得到了5000個文件。最后就是把這5000個文件進行歸并（類似于歸并排序）的過程了。

4、海量數據分布在100臺電腦中，想個辦法高效統計出這批數據的TOP10

解法一：

如果同一個數據元素只出現在某一臺機器中，那么可以采取以下步驟統計出現次數TOP10的數據元素：

• 1.堆排序
  • 在每臺電腦上求出TOP 10，可以采用包含10個元素的堆完成（TOP 10小，用最大堆，TOP 10大，用最小堆，比如求TOP10大，我們首先取前10個元素調整成最小堆，如果發現，然后掃描后面的數據，并與堆頂元素比較，如果比堆頂元素大，那么用該元素替換堆頂，然后再調整為最小堆。最后堆中的元素就是TOP 10大）。
• 2.組合歸并
  • 求出每臺電腦上的TOP 10后，然后把這100臺電腦上的TOP 10組合起來，共1000個數據，再利用上面類似的方法求出TOP 10就可以了。

解法二：

但如果同一個元素重復出現在不同的電腦中呢，比如拿兩臺機器求top 2的情況來說：

• 第一臺的數據分布及各自出現頻率為：a(50)，b(50)，c(49)，d(49) ，e(0)，f(0)
  • 其中，括號里的數字代表某個數據出現的頻率，如a(50)表示a出現了50次。
• 第二臺的數據分布及各自出現頻率為：a(0)，b(0)，c(49)，d(49)，e(50)，f(50)

這個時候，你可以有兩種方法：

• 遍歷一遍所有數據，重新hash取摸，如此使得同一個元素只出現在單獨的一臺電腦中，然后采用上面所說的方法，統計每臺電腦中各個元素的出現次數找出TOP 10，繼而組合100臺電腦上的TOP 10，找出最終的TOP 10。
• 或者，暴力求解：直接統計統計每臺電腦中各個元素的出現次數，然后把同一個元素在不同機器中的出現次數相加，最終從所有數據中找出TOP 10。

5、有10個文件，每個文件1G，每個文件的每一行存放的都是用戶的query，每個文件的query都可能重復。要求你按照query的頻度排序

解法一：

• 1.hash映射
  • 順序讀取10個文件，按照hash(query)%10的結果將query寫入到另外10個文件（記為a0,a1,..a9）中。這樣新生成的文件每個的大小大約也1G（假設hash函數是隨機的）。
• 2.hash_map統計
  • 找一臺內存在2G左右的機器，依次對用hash_map(query, query_count)來統計每個query出現的次數。注：hash_map(query, query_count)是用來統計每個query的出現次數，不是存儲他們的值，出現一次，則count+1。
• 3.堆/快速/歸并排序
  • 利用快速/堆/歸并排序按照出現次數進行排序，將排序好的query和對應的query_cout輸出到文件中，這樣得到了10個排好序的文件（記為）。最后，對這10個文件進行歸并排序（內排序與外排序相結合）。

解法二：

一般query的總量是有限的，只是重復的次數比較多而已，可能對于所有的query，一次性就可以加入到內存了。這樣，我們就可以采用trie樹/hash_map等直接來統計每個query出現的次數，然后按出現次數做快速/堆/歸并排序就可以了。

解法三：

與解法1類似，但在做完hash，分成多個文件后，可以交給多個文件來處理，采用分布式的架構來處理（比如MapReduce），最后再進行合并。

6、給定a、b兩個文件，各存放50億個url，每個url各占64字節，內存限制是4G，讓你找出a、b文件共同的url？

解法：

可以估計每個文件安的大小為5G×64=320G，遠遠大于內存限制的4G。所以不可能將其完全加載到內存中處理。考慮采取分而治之的方法。

• 1.分而治之/hash映射
  • 遍歷文件a，對每個url求取，然后根據所取得的值將url分別存儲到1000個小文件（記為，這里漏寫個了a1）中。這樣每個小文件的大約為300M。遍歷文件b，采取和a相同的方式將url分別存儲到1000小文件中（記為）。這樣處理后，所有可能相同的url都在對應的小文件（）中，不對應的小文件不可能有相同的url。然后我們只要求出1000對小文件中相同的url即可。
• 2.hash_set統計
  • 求每對小文件中相同的url時，可以把其中一個小文件的url存儲到hash_set中。然后遍歷另一個小文件的每個url，看其是否在剛才構建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。

7、100萬個數中找出最大的100個數

解法一：采用局部淘汰法。選取前100個元素，并排序，記為序列L。然后一次掃描剩余的元素x，與排好序的100個元素中最小的元素比，如果比這個最小的要大，那么把這個最小的元素刪除，并把x利用插入排序的思想，插入到序列L中。依次循環，知道掃描了所有的元素。復雜度為O(100萬*100)。

解法二：采用快速排序的思想，每次分割之后只考慮比軸大的一部分，知道比軸大的一部分在比100多的時候，采用傳統排序算法排序，取前100個。復雜度為O(100萬*100)。

解法三：在前面的題中，我們已經提到了，用一個含100個元素的最小堆完成。復雜度為O(100萬*lg100)。

舉一反三

1、怎么在海量數據中找出重復次數最多的一個？

提示：先做hash，然后求模映射為小文件，求出每個小文件中重復次數最多的一個，并記錄重復次數。然后找出上一步求出的數據中重復次數最多的一個就是所求（具體參考前面的題）。

2、上千萬或上億數據（有重復），統計其中出現次數最多的前N個數據。

提示：上千萬或上億的數據，現在的機器的內存應該能存下。所以考慮采用hash_map/搜索二叉樹/紅黑樹等來進行統計次數。然后就是取出前N個出現次數最多的數據了，可以用第2題提到的堆機制完成。

3、一個文本文件，大約有一萬行，每行一個詞，要求統計出其中最頻繁出現的前10個詞，請給出思想，給出時間復雜度分析。

提示：這題是考慮時間效率。用trie樹統計每個詞出現的次數，時間復雜度是O(nle)（le表示單詞的平準長度）。然后是找出出現最頻繁的前10個詞，可以用堆來實現，前面的題中已經講到了，時間復雜度是O(nlg10)。所以總的時間復雜度，是O(nle)與O(nlg10)中較大的哪一個。

4、1000萬字符串，其中有些是重復的，需要把重復的全部去掉，保留沒有重復的字符串。請怎么設計和實現？

提示：這題用trie樹比較合適，hash_map也行。當然，也可以先hash成小文件分開處理再綜合。

5、一個文本文件，找出前10個經常出現的詞，但這次文件比較長，說是上億行或十億行，總之無法一次讀入內存，問最優解。

提示：首先根據用hash并求模，將文件分解為多個小文件，對于單個文件利用上題的方法求出每個文件件中10個最常出現的詞。然后再進行歸并處理，找出最終的10個最常出現的詞。

---

6.3 simhash算法

方法介紹

背景

如果某一天，面試官問你如何設計一個比較兩篇文章相似度的算法？可能你會回答幾個比較傳統點的思路：

• 一種方案是先將兩篇文章分別進行分詞，得到一系列特征向量，然后計算特征向量之間的距離（可以計算它們之間的歐氏距離、海明距離或者夾角余弦等等），從而通過距離的大小來判斷兩篇文章的相似度。
• 另外一種方案是傳統hash，我們考慮為每一個web文檔通過hash的方式生成一個指紋（finger print）。

下面，我們來分析下這兩種方法。

• 采取第一種方法，若是只比較兩篇文章的相似性還好，但如果是海量數據呢，有著數以百萬甚至億萬的網頁，要求你計算這些網頁的相似度。你還會去計算任意兩個網頁之間的距離或夾角余弦么？想必你不會了。
• 而第二種方案中所說的傳統加密方式md5，其設計的目的是為了讓整個分布盡可能地均勻，但如果輸入內容一旦出現哪怕輕微的變化，hash值就會發生很大的變化。

舉個例子，我們假設有以下三段文本：

• the cat sat on the mat
• the cat sat on a mat
• we all scream for ice cream

使用傳統hash可能會得到如下的結果：

• irb(main):006:0> p1 = 'the cat sat on the mat'
  • irb(main):007:0> p1.hash => 415542861
• irb(main):005:0> p2 = 'the cat sat on a mat'
  • irb(main):007:0> p2.hash => 668720516
• irb(main):007:0> p3 = 'we all scream for ice cream'
  • irb(main):007:0> p3.hash => 767429688 "

可理想當中的hash函數，需要對幾乎相同的輸入內容，產生相同或者相近的hash值，換言之，hash值的相似程度要能直接反映輸入內容的相似程度，故md5等傳統hash方法也無法滿足我們的需求。

出世

車到山前必有路，來自于GoogleMoses Charikar發表的一篇論文“detecting near-duplicates for web crawling”中提出了simhash算法，專門用來解決億萬級別的網頁的去重任務。

simhash作為locality sensitive hash（局部敏感哈希）的一種：

• 其主要思想是降維，將高維的特征向量映射成低維的特征向量，通過兩個向量的Hamming Distance來確定文章是否重復或者高度近似。
  • 其中，Hamming Distance，又稱漢明距離，在信息論中，兩個等長字符串之間的漢明距離是兩個字符串對應位置的不同字符的個數。也就是說，它就是將一個字符串變換成另外一個字符串所需要替換的字符個數。例如：1011101 與 1001001 之間的漢明距離是 2。至于我們常說的字符串編輯距離則是一般形式的漢明距離。

如此，通過比較多個文檔的simHash值的海明距離，可以獲取它們的相似度。

流程

simhash算法分為5個步驟：分詞、hash、加權、合并、降維，具體過程如下所述：

• 分詞
  • 給定一段語句，進行分詞，得到有效的特征向量，然后為每一個特征向量設置1-5等5個級別的權重（如果是給定一個文本，那么特征向量可以是文本中的詞，其權重可以是這個詞出現的次數）。例如給定一段語句：“CSDN博客結構之法算法之道的作者July”，分詞后為：“CSDN 博客 結構 之 法 算法 之 道 的 作者 July”，然后為每個特征向量賦予權值：CSDN(4) 博客(5) 結構(3) 之(1) 法(2) 算法(3) 之(1) 道(2) 的(1) 作者(5) July(5)，其中括號里的數字代表這個單詞在整條語句中的重要程度，數字越大代表越重要。
• hash
  • 通過hash函數計算各個特征向量的hash值，hash值為二進制數01組成的n-bit簽名。比如“CSDN”的hash值Hash(CSDN)為100101，“博客”的hash值Hash(博客)為“101011”。就這樣，字符串就變成了一系列數字。
• 加權
  • 在hash值的基礎上，給所有特征向量進行加權，即W = Hash * weight，且遇到1則hash值和權值正相乘，遇到0則hash值和權值負相乘。例如給“CSDN”的hash值“100101”加權得到：W(CSDN) = 100101_4 = 4 -4 -4 4 -4 4，給“博客”的hash值“101011”加權得到：W(博客)=101011_5 = 5 -5 5 -5 5 5，其余特征向量類似此般操作。
• 合并
  • 將上述各個特征向量的加權結果累加，變成只有一個序列串。拿前兩個特征向量舉例，例如“CSDN”的“4 -4 -4 4 -4 4”和“博客”的“5 -5 5 -5 5 5”進行累加，得到“4+5 -4+-5 -4+5 4+-5 -4+5 4+5”，得到“9 -9 1 -1 1”。
• 降維
  • 對于n-bit簽名的累加結果，如果大于0則置1，否則置0，從而得到該語句的simhash值，最后我們便可以根據不同語句simhash的海明距離來判斷它們的相似度。例如把上面計算出來的“9 -9 1 -1 1 9”降維（某位大于0記為1，小于0記為0），得到的01串為：“1 0 1 0 1 1”，從而形成它們的simhash簽名。

其流程如下圖所示：?

應用

• 每篇文檔得到SimHash簽名值后，接著計算兩個簽名的海明距離即可。根據經驗值，對64位的 SimHash值，海明距離在3以內的可認為相似度比較高。
  • 海明距離的求法：異或時，只有在兩個比較的位不同時其結果是1 ，否則結果為0，兩個二進制“異或”后得到1的個數即為海明距離的大小。

舉個例子，上面我們計算到的“CSDN博客”的simhash簽名值為“1 0 1 0 1 1”，假定我們計算出另外一個短語的簽名值為“1 0 1 0 0 0”，那么根據異或規則，我們可以計算出這兩個簽名的海明距離為2，從而判定這兩個短語的相似度是比較高的。

換言之，現在問題轉換為：對于64位的SimHash值，我們只要找到海明距離在3以內的所有簽名，即可找出所有相似的短語。

但關鍵是，如何將其擴展到海量數據呢？譬如如何在海量的樣本庫中查詢與其海明距離在3以內的記錄呢？

• 一種方案是查找待查詢文本的64位simhash code的所有3位以內變化的組合
  • 大約需要四萬多次的查詢。
• 另一種方案是預生成庫中所有樣本simhash code的3位變化以內的組合
  • 大約需要占據4萬多倍的原始空間。

這兩種方案，要么時間復雜度高，要么空間復雜度復雜，能否有一種方案可以達到時空復雜度的絕佳平衡呢？答案是肯定的：

• 我們可以把 64 位的二進制simhash簽名均分成4塊，每塊16位。根據鴿巢原理（也稱抽屜原理），如果兩個簽名的海明距離在 3 以內，它們必有一塊完全相同。如下圖所示：?
• 然后把分成的4 塊中的每一個塊分別作為前16位來進行查找，建倒排索引。

具體如下圖所示：

如此，如果樣本庫中存有2^34（差不多10億）的simhash簽名，則每個table返回2^(34-16)=262144個候選結果，大大減少了海明距離的計算成本。

• 假設數據是均勻分布，16位的數據，產生的像限為2^16個，則平均每個像限分布的文檔數則為2^34/2^16 = 2^(34-16)) ，四個塊返回的總結果數為 4* 262144 （大概 100 萬）。
  • 這樣，原本需要比較10億次，經過索引后，大概只需要處理100萬次。

（部分內容及圖片參考自：http://grunt1223.iteye.com/blog/964564?，后續圖片會全部重畫）

問題實例

待續。

@復旦李斌：simhash不是google發明的，是princeton的人早在stoc02上發表的。google在www07上的那篇論文只是在網頁查重上應用了下。事實上www07中的算法是stoc02中隨機超平面的一個極其巧妙的實現，bit差異的期望正好等于原姶向量的余弦。

---

6.4 外排序

方法介紹

所謂外排序，顧名思義，即是在內存外面的排序，因為當要處理的數據量很大，而不能一次裝入內存時，此時只能放在讀寫較慢的外存儲器（通常是硬盤）上。

外排序通常采用的是一種“排序-歸并”的策略。

• 在排序階段，先讀入能放在內存中的數據量，將其排序輸出到一個臨時文件，依此進行，將待排序數據組織為多個有序的臨時文件；
• 爾后在歸并階段將這些臨時文件組合為一個大的有序文件，也即排序結果。

假定現在有20個數據的文件A：{5 11 0 18 4 14 9 7 6 8 12 17 16 13 19 10 2 1 3 15}，但一次只能使用僅裝4個數據的內容，所以，我們可以每趟對4個數據進行排序，即5路歸并，具體方法如下述步驟：

• 我們先把“大”文件A，分割為a1，a2，a3，a4，a5等5個小文件，每個小文件4個數據

  • a1文件為：5 11 0 18
  • a2文件為：4 14 9 7
  • a3文件為：6 8 12 17
  • a4文件為：16 13 19 10
  • a5文件為：2 1 3 15

• 然后依次對5個小文件分別進行排序

  • a1文件完成排序后：0 5 11 18
  • a2文件完成排序后：4 7 9 14
  • a3文件完成排序后：6 8 12 17
  • a4文件完成排序后：10 13 16 19
  • a5文件完成排序后：1 2 3 15

• 最終多路歸并，完成整個排序

  • 整個大文件A文件完成排序后：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

問題實例

1、給10^7個數據量的磁盤文件排序

輸入：給定一個文件，里面最多含有n個不重復的正整數（也就是說可能含有少于n個不重復正整數），且其中每個數都小于等于n，n=10^7。 輸出：得到按從小到大升序排列的包含所有輸入的整數的列表。 條件：最多有大約1MB的內存空間可用，但磁盤空間足夠。且要求運行時間在5分鐘以下，10秒為最佳結果。

解法一：位圖方案

你可能會想到把磁盤文件進行歸并排序，但題目要求你只有1MB的內存空間可用，所以，歸并排序這個方法不行。

熟悉位圖的朋友可能會想到用位圖來表示這個文件集合。例如正如編程珠璣一書上所述，用一個20位長的字符串來表示一個所有元素都小于20的簡單的非負整數集合，邊框用如下字符串來表示集合{1,2,3,5,8,13}：

0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 

上述集合中各數對應的位置則置1，沒有對應的數的位置則置0。

參考編程珠璣一書上的位圖方案，針對我們的10^7個數據量的磁盤文件排序問題，我們可以這么考慮，由于每個7位十進制整數表示一個小于1000萬的整數。我們可以使用一個具有1000萬個位的字符串來表示這個文件，其中，當且僅當整數i在文件中存在時，第i位為1。采取這個位圖的方案是因為我們面對的這個問題的特殊性：

1. 輸入數據限制在相對較小的范圍內，
2. 數據沒有重復，
3. 其中的每條記錄都是單一的整數，沒有任何其它與之關聯的數據。

所以，此問題用位圖的方案分為以下三步進行解決：

• 第一步，將所有的位都置為0，從而將集合初始化為空。
• 第二步，通過讀入文件中的每個整數來建立集合，將每個對應的位都置為1。
• 第三步，檢驗每一位，如果該位為1，就輸出對應的整數。

經過以上三步后，產生有序的輸出文件。令n為位圖向量中的位數（本例中為1000 0000），程序可以用偽代碼表示如下：

//磁盤文件排序位圖方案的偽代碼  
//copyright@ Jon Bentley  
//July、updated，2011.05.29。  //第一步，將所有的位都初始化為0  
for i ={0,....n} bit[i]=0; //第二步，通過讀入文件中的每個整數來建立集合，將每個對應的位都置為1。 for each i in the input file bit[i]=1; //第三步，檢驗每一位，如果該位為1，就輸出對應的整數。 for i={0...n} if bit[i]==1 write i on the output file 

上述的位圖方案，共需要掃描輸入數據兩次，具體執行步驟如下：

第一次，只處理1—4999999之間的數據，這些數都是小于5000000的，對這些數進行位圖排序，只需要約5000000/8=625000Byte，也就是0.625M，排序后輸出。 第二次，掃描輸入文件時，只處理4999999-10000000的數據項，也只需要0.625M（可以使用第一次處理申請的內存）。 因此，總共也只需要0.625M 位圖的的方法有必要強調一下，就是位圖的適用范圍為針對不重復的數據進行排序，若數據有重復，位圖方案就不適用了。

不過很快，我們就將意識到，用此位圖方法，嚴格說來還是不太行，空間消耗10^7/8還是大于1M（1M=1024*1024空間，小于10^7/8）。

既然如果用位圖方案的話，我們需要約1.25MB（若每條記錄是8位的正整數的話，則10000000/(1024_1024_8) ~= 1.2M）的空間，而現在只有1MB的可用存儲空間，那么究竟該作何處理呢？

解法二：多路歸并

誠然，在面對本題時，還可以通過計算分析出可以用如2的位圖法解決，但實際上，很多的時候，我們都面臨著這樣一個問題，文件太大，無法一次性放入內存中計算處理，那這個時候咋辦呢？分而治之，大而化小，也就是把整個大文件分為若干大小的幾塊，然后分別對每一塊進行排序，最后完成整個過程的排序。k趟算法可以在kn的時間開銷內和n/k的空間開銷內完成對最多n個小于n的無重復正整數的排序。

比如可分為2塊（k=2，1趟反正占用的內存只有1.25/2M），1~4999999，和5000000~9999999。先遍歷一趟，首先排序處理1~4999999之間的整數（用5000000/8=625000個字的存儲空間來排序0~4999999之間的整數），然后再第二趟，對5000001~1000000之間的整數進行排序處理。

解法總結

1、關于本章中位圖和多路歸并兩種方案的時間復雜度及空間復雜度的比較，如下：

        時間復雜度        空間復雜度位圖          O(N)          0.625M多位歸并   O(Nlogn)             1M 

（多路歸并，時間復雜度為O（k_n/k_logn/k ），嚴格來說，還要加上讀寫磁盤的時間，而此算法絕大部分時間也是浪費在這上面）

2、bit-map

適用范圍：可進行數據的快速查找，判重，刪除，一般來說數據范圍是int的10倍以下

基本原理及要點：使用bit數組來表示某些元素是否存在，比如8位電話號碼

擴展：bloom filter可以看做是對bit-map的擴展

舉一反三

1、已知某個文件內包含一些電話號碼，每個號碼為8位數字，統計不同號碼的個數。 8位最多99 999 999，大概需要99m個bit，大概10幾m字節的內存即可。

---

6.5 MapReduce

方法介紹

MapReduce是一種計算模型，簡單的說就是將大批量的工作（數據）分解（MAP）執行，然后再將結果合并成最終結果（REDUCE）。這樣做的好處是可以在任務被分解后，可以通過大量機器進行并行計算，減少整個操作的時間。但如果你要我再通俗點介紹，那么，說白了，Mapreduce的原理就是一個歸并排序。

適用范圍：數據量大，但是數據種類小可以放入內存

基本原理及要點：將數據交給不同的機器去處理，數據劃分，結果歸約。

基礎架構

想讀懂此文，讀者必須先要明確以下幾點，以作為閱讀后續內容的基礎知識儲備：

1. MapReduce是一種模式。
2. Hadoop是一種框架。
3. Hadoop是一個實現了MapReduce模式的開源的分布式并行編程框架。

所以，你現在，知道了什么是MapReduce，什么是hadoop，以及這兩者之間最簡單的聯系，而本文的主旨即是，一句話概括：在hadoop的框架上采取MapReduce的模式處理海量數據。下面，咱們可以依次深入學習和了解MapReduce和hadoop這兩個東西了。

MapReduce模式

前面說了，MapReduce是一種模式，一種什么模式呢?一種云計算的核心計算模式，一種分布式運算技術，也是簡化的分布式編程模式，它主要用于解決問題的程序開發模型，也是開發人員拆解問題的方法。

Ok，光說不上圖，沒用。如下圖所示，MapReduce模式的主要思想是將自動分割要執行的問題（例如程序）拆解成Map（映射）和Reduce（化簡）的方式，流程圖如下圖1所示：

在數據被分割后通過Map函數的程序將數據映射成不同的區塊，分配給計算機機群處理達到分布式運算的效果，在通過Reduce 函數的程序將結果匯整，從而輸出開發者需要的結果。

MapReduce借鑒了函數式程序設計語言的設計思想，其軟件實現是指定一個Map函數，把鍵值對(key/value)映射成新的鍵值對(key/value)，形成一系列中間結果形式的key/value 對，然后把它們傳給Reduce(規約)函數，把具有相同中間形式key的value合并在一起。Map和Reduce函數具有一定的關聯性。函數描述如表1 所示：

MapReduce致力于解決大規模數據處理的問題，因此在設計之初就考慮了數據的局部性原理，利用局部性原理將整個問題分而治之。MapReduce集群由普通PC機構成，為無共享式架構。在處理之前，將數據集分布至各個節點。處理時，每個節點就近讀取本地存儲的數據處理（map），將處理后的數據進行合并（combine）、排序（shuffle and sort）后再分發（至reduce節點），避免了大量數據的傳輸，提高了處理效率。無共享式架構的另一個好處是配合復制（replication）策略，集群可以具有良好的容錯性，一部分節點的down機對集群的正常工作不會造成影響。

ok，你可以再簡單看看下副圖，整幅圖是有關hadoop的作業調優參數及原理，圖的左邊是MapTask運行示意圖，右邊是ReduceTask運行示意圖：

如上圖所示，其中map階段，當map task開始運算，并產生中間數據后并非直接而簡單的寫入磁盤，它首先利用內存buffer來對已經產生的buffer進行緩存，并在內存buffer中進行一些預排序來優化整個map的性能。而上圖右邊的reduce階段則經歷了三個階段，分別Copy->Sort->reduce。我們能明顯的看出，其中的Sort是采用的歸并排序，即merge sort。

問題實例

1. 1. The canonical example application of MapReduce is a process to count the appearances of each different word in a set of documents:
   2. 海量數據分布在100臺電腦中，想個辦法高效統計出這批數據的TOP10。
   3. 一共有N個機器，每個機器上有N個數。每個機器最多存O(N)個數并對它們操作。如何找到N^2個數的中數(median)？

---

6.6 多層劃分

方法介紹

多層劃分法，本質上還是分而治之的思想，因為元素范圍很大，不能利用直接尋址表，所以通過多次劃分，逐步確定范圍，然后最后在一個可以接受的范圍內進行。

問題實例

1、2.5億個整數中找出不重復的整數的個數，內存空間不足以容納這2.5億個整數

分析：有點像鴿巢原理，整數個數為2^32,也就是，我們可以將這2^32個數，劃分為2^8個區域(比如用單個文件代表一個區域)，然后將數據分離到不同的區域，然后不同的區域在利用bitmap就可以直接解決了。也就是說只要有足夠的磁盤空間，就可以很方便的解決。

2、5億個int找它們的中位數

分析：首先我們將int劃分為2^16個區域，然后讀取數據統計落到各個區域里的數的個數，之后我們根據統計結果就可以判斷中位數落到那個區域，同時知道這個區域中的第幾大數剛好是中位數。然后第二次掃描我們只統計落在這個區域中的那些數就可以了。

實際上，如果不是int是int64，我們可以經過3次這樣的劃分即可降低到可以接受的程度。即可以先將int64分成2^24個區域，然后確定區域的第幾大數，在將該區域分成2^20個子區域，然后確定是子區域的第幾大數，然后子區域里的數的個數只有2^20，就可以直接利用direct addr table進行統計了。

---

方法介紹

什么是Bit-map

所謂的Bit-map就是用一個bit位來標記某個元素對應的Value， 而Key即是該元素。由于采用了Bit為單位來存儲數據，因此在存儲空間方面，可以大大節省。

來看一個具體的例子，假設我們要對0-7內的5個元素(4,7,2,5,3)排序（這里假設這些元素沒有重復）。那么我們就可以采用Bit-map的方法來達到排序的目的。要表示8個數，我們就只需要8個Bit（1Bytes），首先我們開辟1Byte的空間，將這些空間的所有Bit位都置為0(如下圖：)

然后遍歷這5個元素，首先第一個元素是4，那么就把4對應的位置為1（可以這樣操作 p+(i/8)|(0×01

?

---

?

?

6.8 Bloom filter

方法介紹

一、什么是Bloom Filter

Bloom Filter，被譯作稱布隆過濾器，是一種空間效率很高的隨機數據結構，Bloom filter可以看做是對bit-map的擴展,它的原理是：

• 當一個元素被加入集合時，通過K個Hash函數將這個元素映射成一個位陣列（Bit array）中的K個點，把它們置為1**。檢索時，我們只要看看這些點是不是都是1就（大約）知道集合中有沒有它了：
  • 如果這些點有任何一個0，則被檢索元素一定不在；
  • 如果都是1，則被檢索元素很可能在。

其可以用來實現數據字典，進行數據的判重，或者集合求交集。

但Bloom Filter的這種高效是有一定代價的：在判斷一個元素是否屬于某個集合時，有可能會把不屬于這個集合的元素誤認為屬于這個集合（false positive）。因此，Bloom Filter不適合那些“零錯誤”的應用場合。而在能容忍低錯誤率的應用場合下，Bloom Filter通過極少的錯誤換取了存儲空間的極大節省。

1.1、集合表示和元素查詢

下面我們具體來看Bloom Filter是如何用位數組表示集合的。初始狀態時，Bloom Filter是一個包含m位的位數組，每一位都置為0。

為了表達S={x1, x2,…,xn}這樣一個n個元素的集合，Bloom Filter使用k個相互獨立的哈希函數（Hash Function），它們分別將集合中的每個元素映射到{1,…,m}的范圍中。對任意一個元素x，第i個哈希函數映射的位置hi(x)就會被置為1（1≤i≤k）。注意，如果一個位置多次被置為1，那么只有第一次會起作用，后面幾次將沒有任何效果。在下圖中，k=3，且有兩個哈希函數選中同一個位置（從左邊數第五位，即第二個“1“處）。

在判斷y是否屬于這個集合時，我們對y應用k次哈希函數，如果所有hi(y)的位置都是1（1≤i≤k），那么我們就認為y是集合中的元素，否則就認為y不是集合中的元素。下圖中y1就不是集合中的元素（因為y1有一處指向了“0”位）。y2或者屬于這個集合，或者剛好是一個false positive。

1.2、錯誤率估計

前面我們已經提到了，Bloom Filter在判斷一個元素是否屬于它表示的集合時會有一定的錯誤率（false positive rate），下面我們就來估計錯誤率的大小。在估計之前為了簡化模型，我們假設kn1, x2,…,xn}的所有元素都被k個哈希函數映射到m位的位數組中時，這個位數組中某一位還是0的概率是：

其中1/m表示任意一個哈希函數選中這一位的概率（前提是哈希函數是完全隨機的），(1-1/m)表示哈希一次沒有選中這一位的概率。要把S完全映射到位數組中，需要做kn次哈希。某一位還是0意味著kn次哈希都沒有選中它，因此這個概率就是（1-1/m）的kn次方。令p = e-kn/m是為了簡化運算，這里用到了計算e時常用的近似：

令ρ為位數組中0的比例，則ρ的數學期望E(ρ)= p’。在ρ已知的情況下，要求的錯誤率（false positive rate）為：

(1-ρ)為位數組中1的比例，(1-ρ)k就表示k次哈希都剛好選中1的區域，即false positive rate。上式中第二步近似在前面已經提到了，現在來看第一步近似。p’只是ρ的數學期望，在實際中ρ的值有可能偏離它的數學期望值。M. Mitzenmacher已經證明[2]?，位數組中0的比例非常集中地分布在它的數學期望值的附近。因此，第一步的近似得以成立。分別將p和p’代入上式中，得：

相比p’和f’，使用p和f通常在分析中更為方便。

1.3、最優的哈希函數個數

既然Bloom Filter要靠多個哈希函數將集合映射到位數組中，那么應該選擇幾個哈希函數才能使元素查詢時的錯誤率降到最低呢？這里有兩個互斥的理由：如果哈希函數的個數多，那么在對一個不屬于集合的元素進行查詢時得到0的概率就大；但另一方面，如果哈希函數的個數少，那么位數組中的0就多。為了得到最優的哈希函數個數，我們需要根據上一小節中的錯誤率公式進行計算。

先用p和f進行計算。注意到f = exp(k ln(1 ? e?kn/m))，我們令g = k ln(1 ? e?kn/m)，只要讓g取到最小，f自然也取到最小。由于p = e-kn/m，我們可以將g寫成

根據對稱性法則可以很容易看出當p = 1/2，也就是k = ln2· (m/n)時，g取得最小值。在這種情況下，最小錯誤率f等于(1/2)k≈ (0.6185)m/n。另外，注意到p是位數組中某一位仍是0的概率，所以p = 1/2對應著位數組中0和1各一半。換句話說，要想保持錯誤率低，最好讓位數組有一半還空著。

需要強調的一點是，p = 1/2時錯誤率最小這個結果并不依賴于近似值p和f。同樣對于f’ = exp(k ln(1 ? (1 ? 1/m)kn))，g’ = k ln(1 ? (1 ? 1/m)kn)，p’ = (1 ? 1/m)kn，我們可以將g’寫成

同樣根據對稱性法則可以得到當p’ = 1/2時，g’取得最小值。

1.4、位數組的大小

下面我們來看看，在不超過一定錯誤率的情況下，Bloom Filter至少需要多少位才能表示全集中任意n個元素的集合。假設全集中共有u個元素，允許的最大錯誤率為?，下面我們來求位數組的位數m。

假設X為全集中任取n個元素的集合，F(X)是表示X的位數組。那么對于集合X中任意一個元素x，在s = F(X)中查詢x都能得到肯定的結果，即s能夠接受x。顯然，由于Bloom Filter引入了錯誤，s能夠接受的不僅僅是X中的元素，它還能夠? (u - n)個false positive。因此，對于一個確定的位數組來說，它能夠接受總共n + ? (u - n)個元素。在n + ? (u - n)個元素中，s真正表示的只有其中n個，所以一個確定的位數組可以表示

個集合。m位的位數組共有2m個不同的組合，進而可以推出，m位的位數組可以表示

個集合。全集中n個元素的集合總共有

個，因此要讓m位的位數組能夠表示所有n個元素的集合，必須有

即：

上式中的近似前提是n和?u相比很小，這也是實際情況中常常發生的。根據上式，我們得出結論：在錯誤率不大于?的情況下，m至少要等于n log2(1/?)才能表示任意n個元素的集合。

上一小節中我們曾算出當k = ln2· (m/n)時錯誤率f最小，這時f = (1/2)k= (1/2)mln2 / n。現在令f≤?，可以推出

這個結果比前面我們算得的下界n log2(1/?)大了log2e≈ 1.44倍。這說明在哈希函數的個數取到最優時，要讓錯誤率不超過?，m至少需要取到最小值的1.44倍。

問題實例

1、給你A,B兩個文件，各存放50億條URL，每條URL占用64字節，內存限制是4G，讓你找出A,B文件共同的URL。如果是三個乃至n個文件呢？

分析：如果允許有一定的錯誤率，可以使用Bloom filter，4G內存大概可以表示340億bit。將其中一個文件中的url使用Bloom filter映射為這340億bit，然后挨個讀取另外一個文件的url，檢查是否與Bloom filter，如果是，那么該url應該是共同的url（注意會有一定的錯誤率）。”

---

6.9 Trie樹

方法介紹

1.1、什么是Trie樹

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

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

它有3個基本性質：

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

1.2、樹的構建

咱們先來看一個問題：假如現在給你10萬個長度不超過10的單詞，對于每一個單詞，我們要判斷它出沒出現過，如果出現了，求第一次出現在第幾個位置。對于這個問題，我們該怎么解決呢？

如果我們用最傻的方法，對于每一個單詞，我們都要去查找它前面的單詞中是否有它。那么這個算法的復雜度就是O(n^2)。顯然對于10萬的范圍難以接受。

換個思路想：

• 假設我要查詢的單詞是abcd，那么在它前面的單詞中，以b，c，d，f之類開頭的顯然不必考慮，而只要找以a開頭的中是否存在abcd就可以了。
  • 同樣的，在以a開頭中的單詞中，我們只要考慮以b作為第二個字母的，一次次縮小范圍和提高針對性，這樣一個樹的模型就漸漸清晰了。

即如果現在有b，abc，abd，bcd，abcd，efg，hii 這6個單詞，我們可以構建一棵如下圖所示的樹：

如上圖所示，對于每一個節點，從根遍歷到他的過程就是一個單詞，如果這個節點被標記為紅色，就表示這個單詞存在，否則不存在。

那么，對于一個單詞，只要順著他從根走到對應的節點，再看這個節點是否被標記為紅色就可以知道它是否出現過了。把這個節點標記為紅色，就相當于插入了這個單詞。

這樣一來我們查詢和插入可以一起完成，所用時間僅僅為單詞長度（在這個例子中，便是10）。這就是一棵trie樹。

我們可以看到，trie樹每一層的節點數是26^i級別的。所以為了節省空間，我們還可以用動態鏈表，或者用數組來模擬動態。而空間的花費，不會超過單詞數×單詞長度。

1.3、查詢

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。

問題實例

1、一個文本文件，大約有一萬行，每行一個詞，要求統計出其中最頻繁出現的前10個詞，請給出思想，給出時間復雜度分析

提示：用trie樹統計每個詞出現的次數，時間復雜度是O(nle)（le表示單詞的平均長度），然后是找出出現最頻繁的前10個詞。當然，也可以用堆來實現，時間復雜度是O(nlg10)。所以總的時間復雜度，是O(nle)與O(nlg10)中較大的哪一個。

2、尋找熱門查詢

原題：搜索引擎會通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來，每個查詢串的長度為1-255字節。假設目前有一千萬個記錄，這些查詢串的重復讀比較高，雖然總數是1千萬，但是如果去除重復和，不超過3百萬個。一個查詢串的重復度越高，說明查詢它的用戶越多，也就越熱門。請你統計最熱門的10個查詢串，要求使用的內存不能超過1G。

提示：利用trie樹，關鍵字域存該查詢串出現的次數，沒有出現為0。最后用10個元素的最小推來對出現頻率進行排序。

---

6.10 數據庫

方法介紹

當遇到大數據量的增刪改查時，一般把數據裝進數據庫中，從而利用數據的設計實現方法，對海量數據的增刪改查進行處理。

---

?

6.11 倒排索引

方法介紹

倒排索引是一種索引方法，被用來存儲在全文搜索下某個單詞在一個文檔或者一組文檔中的存儲位置的映射，常被應用于搜索引擎和關鍵字查詢的問題中。

以英文為例，下面是要被索引的文本：

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"將對應集合的交集。

正向索引開發出來用來存儲每個文檔的單詞的列表。正向索引的查詢往往滿足每個文檔有序頻繁的全文查詢和每個單詞在校驗文檔中的驗證這樣的查詢。在正向索引中，文檔占據了中心的位置，每個文檔指向了一個它所包含的索引項的序列。也就是說文檔指向了它包含的那些單詞，而反向索引則是單詞指向了包含它的文檔，很容易看到這個反向的關系。

問題實例

1、文檔檢索系統，查詢那些文件包含了某單詞，比如常見的學術論文的關鍵字搜索

提示：建倒排索引。

---

6.15 本章習題

本章海量數據的習題

1?有100W個關鍵字，長度小于等于50字節。用高效的算法找出top10的熱詞，并對內存的占用不超過1MB。

提示：老題，與caopengcs討論后，得出具體思路為：

• 先把100W個關鍵字hash映射到小文件，根據題意，100W_50B = 50_10^6B = 50M，而內存只有1M，故干脆搞一個hash函數 % 50，分解成50個小文件；
• 針對對每個小文件依次運用hashmap(key，value)完成每個key的value次數統計，后用堆找出每個小文件中value次數最大的top 10； -最后依次對每兩小文件的top 10歸并，得到最終的top 10。

此外，很多細節需要注意下，舉個例子，如若hash映射后導致分布不均的話，有的小文件可能會超過1M，故為保險起見，你可能會說根據數據范圍分解成50~500或更多的小文件，但到底是多少呢？我覺得這不重要，勿糾結答案，雖準備在平時，但關鍵還是看臨場發揮，保持思路清晰關注細節即可。

2

單機5G內存，磁盤200T的數據，分別為字符串，然后給定一個字符串，判斷這200T數據里面有沒有這個字符串，怎么做？ 如果查詢次數會非常的多, 怎么預處理？

提示：如果數據是200g且允許少許誤差的話，可以考慮用布隆過濾器Bloom Filter。但本題是200T，得另尋良策，具體解法請讀者繼續思考。

3

現在有一個大文件，文件里面的每一行都有一個group標識（group很多，但是每個group的數據量很小），現在要求把這個大文件分成十個小文件，要求：

• 1、同一個group的必須在一個文件里面；
• 2、切分之后，要求十個小文件的數據量盡可能均衡。

7

服務器內存1G，有一個2G的文件，里面每行存著一個QQ號（5-10位數），怎么最快找出出現過最多次的QQ號。

8

盡量高效的統計一片英文文章（總單詞數目）里出現的所有英文單詞，按照在文章中首次出現的順序打印輸出該單詞和它的出現次數。

9

在人人好友里，A和B是好友，B和C是好友，如果A　和C不是好友，那么C是A的二度好友，在一個有10萬人的數據庫里，如何在時間０（ｎ）里，找到某個人的十度好友。

12

海量記錄，記錄形式如下： TERMID URLNOCOUNT urlno1 urlno2 ..., urlnon，請問怎么考慮資源和時間這兩個因素，實現快速查詢任意兩個記錄的交集，并集等，設計相關的數據結構和算法。

14

有一億個整數，請找出最大的1000個，要求時間越短越好，空間占用越少越好。

18

10億個int型整數，如何找出重復出現的數字。

19

有2G的一個文本文檔，文件每行存儲的是一個句子，每個單詞是用空格隔開的。問：輸入一個句子，如何找到和它最相似的前10個句子。

提示：可用倒排文檔。

20

某家視頻網站，每天有上億的視頻被觀看，現在公司要請研發人員找出最熱門的視頻。 該問題的輸入可以簡化為一個字符串文件，每一行都表示一個視頻id，然后要找出出現次數最多的前100個視頻id，將其輸出，同時輸出該視頻的出現次數。

• 1.假設每天的視頻播放次數為3億次，被觀看的視頻數量為一百萬個，每個視頻ID的長度為20字節，限定使用的內存為1G。請簡述做法，再寫代碼。
• 2.假設每個月的視頻播放次數為100億次，被觀看的視頻數量為1億，每個視頻ID的長度為20字節，一臺機器被限定使用的內存為1G。

提示：萬變不離其宗，分而治之/Hash映射 + Hash統計 + 堆/快速/歸并排序。

21

有一個log文件，里面記錄的格式為：

QQ號     時間        flag123456   14：00：00     0 123457 14：00：01 1 

其中flag=0表示登錄 flag=1表示退出

問：統計一天平均在線的QQ數。

22

一個文本，一萬行，每行一個詞，統計出現頻率最高的前10個詞（詞的平均長度為Len）。并分析時間復雜度。

23

在一個文件中有 10G 個整數，亂序排列，要求找出中位數。內存限制為 2G。只寫出思路即可。

24

一個url指向的頁面里面有另一個url,最終有一個url指向之前出現過的url或空，這兩種情形都定義為null。這樣構成一個單鏈表。給兩條這樣單鏈表，判斷里面是否存在同樣的url。url以億級計，資源不足以hash。

25

一個1G大小的一個文件，里面每一行是一個詞，詞的大小不超過16字節，內存限制大小是1M。返回頻數最高的100個詞。

26

1000萬字符串，其中有些是重復的，需要把重復的全部去掉，保留沒有重復的字符串。請怎么設計和實現？

27?有10個文件，每個文件1G，每個文件的每一行都存放的是用戶的query，每個文件的query都可能重復。要你按照query的頻度排序。

28

現有一200M的文本文件，里面記錄著IP地址和對應地域信息，如

202.100.83.56 北京 北京大學202.100.83.120 北京 人民大學 202.100.83.134 北京 中國青年政治學院 211.93.120.45 長春市 長春大學 211.93.120.129 吉林市 吉林大學 211.93.120.200 長春 長春KTV 

現有6億個IP地址，請編寫程序，讀取IP地址便轉換成IP地址相對應的城市，要求有較好的時間復雜度和空間復雜度。

（本篇完~）

?