海量資料處理 | 關于TopK的思考

   目  錄   

海量資料處理–TopK引發的思考

1 三問海量資料處理

2 解決Top K

     2.1抛出問題：尋找熱門查詢

     2.2分析問題

         2.2.1劃分

         2.2.2統計

          2.2.3資料結構

          2.2.4合并

          2.2.5結束

3 Trie樹和反向索引

    3.1反向索引

    3.2字典樹

    3.3應用執行個體

 海量資料處理–TopK引發的思考

01

三問海量資料處理

什麼是海量資料處理，為什麼出現這種需求？

如何進行海量資料處理，常用的方法和技術有什麼？

如今分布式架構已經很成熟了，為什麼還用學習海量資料處理的技術？

簡單回答

什麼是海量資料處理，為什麼出現這種需求？

如今網際網路産生的資料量已經達到PB級别，如何在資料量不斷增大的情況下，依然保證快速的檢索或者更新資料，是我們面臨的問題。所謂海量資料處理，是指基于海量資料的存儲、處理和操作等。因為資料量太大無法在短時間迅速解決，或者不能一次性讀入記憶體中。

如何進行海量資料處理，常用的方法和技術有什麼？

時間角度，我們需要設計巧妙的算法配合合适的資料結構來解決；例如常用到的資料結構：哈希、位圖、堆、資料庫（B樹），紅黑樹、反向索引、Trie樹等。空間角度：我們隻需要分而治之即可，兩大步操作：分治、合并。MapReduce就是基于這個原理。

如今分布式架構已經很成熟了，為什麼還用學習海量資料處理的技術？

這個問題，就相當于為什麼要學習算法，因為大部分人在工作中都很少用到這些算法和進階的資料機構。武俠講究内外兼修才是集大成着。算法就是内功，可以不用，不可以沒有。算法更多的是了解和推到的過程，這就是為什麼很多學數學和實體專業的學生，可以在計算機行業做的很好，因為他們的數學好，可以很好的了解各種推到過程和算法原理。最後一句話，知其然而後知其是以然，技術更好的成長。

02

解決Top K

這篇文章，我采用總分的結構進行寫作，我們每次都會抛出一個問題，這個問題對應的海量資料處理的一個方面，我們從下面幾個角度分析：

1、對應海量資料處理的哪個技術，從時間角度和空間角度考慮

2、分析這個問題，如何解決

3、提出解決方案，進行分析

4、詳細講解這處理這個問題時，用到的技術，例如什麼是堆，hash等

2.1 抛出問題：尋找熱門查詢

任何的搜尋引擎（百度、Google等）都會将使用者的查詢記錄到日志檔案。對于百度這種公司，我們知道每天有很多Query查詢，假設有100G的日志檔案，隻有一台4G記憶體的電腦，現在讓你統計某一天熱門查詢的Top 100. （Top 100的統計是很有用意義的，可以提供給使用者，知道目前什麼是最熱門的，關注熱點，例如金庸老先生的去世，現在應該就是熱門。）

2.2 分析問題

根據題目的描述，我們有100G日志檔案，隻有一台4G的電腦，這是空間不足的問題，我們需要分而治之。

1、劃分檔案，将100G日志檔案劃分成K的小檔案。K >= 100G / 4G = 25。這裡我們去K=50（為什麼不取25呢？），将所有的Query劃分到50個小檔案中，然後統計每一個小檔案中的Query的頻率，之後合并結果，得到最後的Top 100的Query。

2、需要我們處理的兩個點：劃分和合并。

劃分：保證相同的Query劃分到同一個小檔案中。

統計：統計每個小檔案中Query的頻率

合并：如何快速的合并得到結果。

劃分的時候我們需要用到一個叫做hash的技術，兩步走，

3、hash(string) = key_index,

4、File_index = Key_index % K(50)

劃分

設計一個hash函數，需要保證的正string -> index的轉換，這裡不需要考慮沖突，隻有保證相同的string對應一個key_index即可，一個好的hash函數會将均勻分布的資料，均勻分布到不同的檔案中去。常用的Hash函數和原理

const unsigned int BIG_MOD = 1000003;inline unsigned int hash_code(std::string&& key){unsigned int value = 0;for(int i = 0; i < key.size(); i++) {31 + (unsigned int) key[i];        value %= BIG_MOD;    }return}      

統計

這裡給出兩種方法， hash_map和Trie數。每一個小檔案有一個輸出結果，這裡我們隻需要輸出前Top 100頻率進行。

Hash_map這個原理跟前面的提到的hash函數基本一樣，隻是需要解決沖突問題，之後會在别的文章中專門提出。C++的結構map，或者Java中Hashmap或者Python中的dict基本使用方式一樣。Map[query] += 1.

HashMap的不足在于我們空間使用多，對于查詢這種Query，很多的查詢都是一樣的，我們可以使用Trie樹來解救，這是一個字首樹的結果，例如

Querys = {“我愛你”，“愛你們”，“我”，“我”，“我愛你“，”金庸“}，構造的樹的格式如需：

資料結構

const int MAXN = 10000;struct TreeNodestringintintstruct TreeNode *next[MAXN];};      

具體的Trie樹細節，這裡就不在繼續展開，可以搜尋相關文章，後續可能會繼續退出Trie樹的相關文章。

基于上述兩種方法，我們都可以直接得到Top 100的結果。輸出檔案格式如下：

Query1 Count1

。

。

。

Queryi Counti

合并

讀取所有的結果在記憶體中，根據Count排序取前100，時間複雜度是O(nlogn),n是所有個數n=50*100. 但是注意到我們隻要前k個最大的，我可以使用堆排序，使用一個叫做最小堆的問題。維護k(100)大小的最小堆，每次插入新的元素，去掉最小的元素，時間複雜度O(k + (n-k)logk),比排序小很多。

這裡同樣可以使用Trie樹，和上述的方式一樣，注意這可以轉化一個取第k個大小的問題，我們也可以使用快速排序中劃分函數，進行找到第k個，前面的就是我們需要的目标。

結束

到這裡我們的問題已經可以結束了，但是卻有幾個問題需要提出來。

這真的是熱門Query統計嗎？百度等公司是這麼做的嗎？相似的Query怎麼處理？如何實時的更新熱門榜單呢？等等的問題，需要我們思考。

Hash劃分的時候，劃分檔案不平衡怎麼辦？如何保證平均劃分？

 Trie樹和反向索引 

3.1 反向索引 

反向索引是一種索引方法，常用在搜尋引擎中，這個資料結構是根據屬性值來确定記錄的位置。對于一批文檔，我們的屬性值就是關鍵字，對應值是包含該屬性的文檔的ID或者文化的位置。

例如

T0T1T2      

建構反向索引

a: {0,1,2}b: {0,2}c: {0,2}d: {1}e: {1}      

檢索的時候可以根據關鍵字的交集或者并集進行檢索，可以看出，反向索引就是正向索引的相反。原理其實很簡單，可以通過學習或者問題的性質，來發現什麼時候使用倒排碎索引，最重要的反向索引怎麼優化，在記憶體中和檔案上如何配置設定，才能滿足快速的檢索。反向索引的建構可以根據自己的業務，決定需要存儲什麼資訊，但是屬性值是确定的，對應的集合中可以保留出現的次數等資訊。

3.2 字典樹

字典樹，Trie樹是一種字首樹，我們之前也有介紹過，一般應用在快速查詢中，例如搜尋提示，當你輸入前半部分，會提示後半部分的内容。字典樹用一句話表示就是根據字元串的字首構成的樹結構。

格式定義

template<typenamestruct TreeNodeint flag; // {1,0}1:表示存在，0:表示不存在int count: // 表示這個字元串出現的次數struct TreeNode **childs; // 索引的孩子節點    T value;};      

搜尋字典項目的方法為：(來自百度百科)

從根結點開始一次搜尋；

取得要查找關鍵詞的第一個字母，并根據該字母選擇對應的子樹并轉到該子樹繼續進行檢索；

在相應的子樹上，取得要查找關鍵詞的第二個字母,并進一步選擇對應的子樹進行檢索。

疊代過程……

在某個結點處，關鍵詞的所有字母已被取出，則讀取附在該結點上的資訊，即完成查找。

3.3 應用執行個體

1、串的快速檢索

給出N個單詞組成的熟詞表，以及一篇全用小寫英文書寫的文章，請你按最早出現的順序寫出所有不在熟詞表中的生詞。在這道題中，我們可以用數組枚舉，用哈希，用字典樹，先把熟詞建一棵樹，然後讀入文章進行比較，這種方法效率是比較高的。

2、“串”排序

給定N個互不相同的僅由一個單詞構成的英文名，讓你将他們按字典序從小到大輸出

用字典樹進行排序，采用數組的方式建立字典樹，這棵樹的每個結點的所有兒子很顯然地按照其字母大小排序。對這棵樹進行先序周遊即可。

3、最長公共字首

對所有串建立字典樹，對于兩個串的最長公共字首的長度即他們所在的結點的公共祖先個數，于是，問題就轉化為當時公共祖先問題。

4、搜尋引擎

一個搜尋引擎執行的目标就是優化查詢的速度：找到某個單詞在文檔中出現的地方。以前，正向索引開發出來用來存儲每個文檔的單詞的清單，接着掉頭來開發了一種反向索引。 正向索引的查詢往往滿足每個文檔有序頻繁的全文查詢和每個單詞在校驗文檔中的驗證這樣的查詢。實際上，時間、記憶體、處理器等等資源的限制，技術上正向索引是不能實作的。為了替代正向索引的每個文檔的單詞清單，能列出每個查詢的單詞所有所在文檔的清單的反向索引資料結構開發了出來。随着反向索引的建立，如今的查詢能通過立即的單詞标示迅速擷取結果（經過随機存儲）。随機存儲也通常被認為快于順序存儲。

作者簡介

xiaoran，Datawhale團隊成員， 中科院碩士，百度算法工程師，推薦系統、搜尋引擎愛好者。研究方向：圖像識别。個人經曆：ccf大資料計算智能大賽前25名，秋招中拿到百度、阿裡、頭條等多家公司的算法offer。

生活如此，問題不大

喵~

—  E N D  —

圖檔/伊小雪

排版/無多

Datawhale