Top K

csdn 【海量数据处理】如何从大量数据中找出高频词？

如何从大量数据中找出高频词？

题目描述

有一个 1GB 大小的文件，文件里每一行是一个词，每个词的大小不超过 16B，内存大小限制是 1MB，要求返回频数最高的 100 个词(Top 100)。

解答思路

由于内存限制，我们依然无法直接将大文件的所有词一次读到内存中。因此，同样可以采用分治策略，把一个大文件分解成多个小文件，保证每个文件的大小小于 1MB，进而直接将单个小文件读取到内存中进行处理。

思路如下：

首先遍历大文件，对遍历到的每个词x，执行 hash(x) % 5000，将结果为 i 的词存放到文件 ai 中。遍历结束后，我们可以得到 5000 个小文件。每个小文件的大小为 200KB 左右。如果有的小文件大小仍然超过 1MB，则采用同样的方式继续进行分解。

接着统计每个小文件中每个词出现频数。最简单的方式是使用 HashMap 来实现。其中 key 为词，value 为该词出现的频率。具体方法是：对于遍历到的词 x，如果在 map 中不存在，则执行 map.put(x, 1)；若存在，则执行 map.put(x, map.get(x)+1)，将该词频数加 1。

上面我们统计了每个小文件单词出现的频数。接下来，我们可以通过维护一个小顶堆来找出所有词中出现频数最高的 100 个。具体方法是：构建一个小顶堆，堆大小为 100。遍历map，如果遍历到的词的出现次数大于堆顶词的出现次数，则用新词替换堆顶的词，然后重新调整为小顶堆，当所有小文件对应的频数map遍历结束后，小顶堆上的词就是出现频数最高的 100 个词。

方法总结

一、分而治之，进行哈希取余；

二、使用 HashMap 统计频数；

三、求解最大的 TopN 个，用小顶堆；求解最小的 TopN 个，用大顶堆。

LeetCode 海量数据处理方法 # 海量数据求TopK

题目描述：

有一个 1GB 大小的文件，文件里每一行是一个词，每个词的大小不超过 16B，内存大小限制是 1MB，要求返回频数最高的 100 个词(Top 100)。 同类型题目：找出一天中访问百度次数最多的100个IP

解法第一步：分治法

先把1GB大小的文件分成5000份，每份200KB，这样内存操作足够。然后调用hash函数hash(words) % 5000

这样对每一份文件利用hash表进行统计，统计结果再调用topk算法得出前100，再将前100存放在一个文件中，假定是b系列文件。

每个词16B，再加上次数4B（int足够存放次数）和结尾的分隔符，也就是每条记录21B，每个b文件有100条记录，那么每个b文件就是2KB大小。

然后将5000个文件分成50组，每组100个文件进行合并，合并后的文件为200K吧，里面有10000条记录，然后再执行topk算法。再将文件缩小为2KB。

然后对剩下的这50个文件再合并一次，就能得到最后的结果了。