如何從海量數據中找出高頻詞？

大家好，我是陌溪

今天分享一道面試常考的海量數據面試題。

題目描述

假如有一個 1G 大小的文件，文件裏每一行是一個詞，每個詞的大小不超過 16byte，要求返回出現頻率最高的 100 個詞。內存大小限制是 10M

解法 1

由於內存限制，我們無法直接將大文件的所有詞一次性讀到內存中。

可以使用分治策略，把一個大文件分解成多個小文件，保證每個文件的大小小於 10M，進而直接將單個小文件讀取到內存中處理。

第一步，首先遍歷大文件，對遍歷到的每個詞 x，執行 hash(x) % 500，將結果爲 i 的詞存放到文件 f(i) 中，遍歷結束後，可以得到 500 個小文件，每個小文件的大小爲 2M 左右；

第二步，接着統計每個小文件中出現頻數最高的 100 個詞。可以使用 HashMap 來實現，其中 key 是詞，value 是該詞出現的頻率。

對於遍歷到的詞 x，如果在 map 中不存在，則執行 map.put(x, 1)。

若存在，則執行 map.put(x, map.get(x)+1)，將該詞出現的次數加 1。

第三步，在第二步中找出了每個文件出現頻率最高的 100 個詞之後，通過維護一個小頂堆來找出所有小文件中出現頻率最高的 100 詞。

具體方法是，遍歷第一個文件，把第一個文件中出現頻率最高的 100 個詞構造成小頂堆。

如果第一個文件中詞的個數小於 100，可以繼續遍歷第二個文件，直到構造好有 100 個結點的小頂堆爲止。

繼續遍歷其他小文件，如果遍歷到的詞的出現次數大於堆頂上詞的出現次數，可以用新遍歷到的詞替換堆頂的詞，然後重新調整此堆爲小頂堆。

當遍歷完所有小文件後，這個小頂堆中的詞就是出現頻率最高的 100 詞。

總結一下，這種解法的主要思路如下：

  1. 採用分治的思想，進行哈希取餘

  2. 使用 HashMap 統計每個小文件單詞出現的頻次

  3. 使用小頂堆，遍歷步驟 2 中的小文件，找出詞頻 top100 的詞

但是很容易可以發現問題，在第二步中，如果這個 1G 的大文件中有某個詞詞頻過高，可能導致小文件大小超過 10m。這種情況下該怎麼處理呢？

接下來看另外一種解法。

解法 2

第一步：使用多路歸併排序對大文件進行排序，這樣相同的單詞肯定是緊挨着的

多路歸併排序對大文件進行排序的步驟如下：

① 將文件按照順序切分成大小不超過 2m 的小文件，總共 500 個小文件

② 使用 10MB 內存分別對 500 個小文件中的單詞進行排序

③ 使用一個大小爲 500 大小的堆，對 500 個小文件進行多路排序，結果寫到一個大文件中

其中第三步，對 500 個小文件進行多路排序的思路如下：

第二步：

① 初始化一個 100 個節點的小頂堆，用於保存 100 個出現頻率最多的單詞

② 遍歷整個文件，一個單詞一個單詞的從文件中取出來，並計數

③ 等到遍歷的單詞和上一個單詞不同的話，那麼上一個單詞及其頻率如果大於堆頂的詞的頻率，那麼放在堆中，否則不放

最終，小頂堆中就是出現頻率前 100 的單詞了。

解法 2 相對解法 1，更加嚴謹，如果某個詞詞頻過高或者整個文件都是同一個詞的話，解法 1 不適用。

想與我交流的話，可以到公衆號後臺獲取我的個人微信號~

程序員大彬 非科班轉碼，校招拿了京東、攜程等多家互聯網大廠 offer，專注分享 Java 技術乾貨

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/zj4Tc5xFPNV6K9fdsPdQcw

猜你喜歡