海量数据处理问题（一）|海量数据处理问题（一） ---- 内存无法处理的词频统计
这篇博客源自对一个内存无法处理的词频统计问题的思考，最后给出的解决办法是自己想的，可以肯定这不是最好的解法。但是通过和同学的讨论，仍然感觉这是一个有意义及有意思的问题，所以和大家分享与探讨。
如果有误，请大家指正。如果有更好的方法，望不吝赐教。
一、提出问题
实际问题:
当前有10T中文关键词数据，需要统计出词频最高的1000个词。可用的只有1G内存和磁盘。那么如何提取？
大概估算一下这个问题，设中文词汇平均长度2.3，每次汉字用utf-8编码是3B，那么10T数据大概有 10T/7B ~ 1.4 * 2^40 条词汇。
1G内存即便对词汇一 一对应，再加上4B的整形记录词频，那么1G内存可以最多纪录 1G/4B * 2^8 ~ 2^36 条词汇。所以即便最完美的hash（一 一对应）也无法将所有词汇对应到1G内存中。
抽象问题:
假设当前内存只能存放1000个词，但是一共有100w词汇需要处理，问如何返回前100个高频词汇？（只能使用内存和磁盘）
下面我们以抽象的问题为基础进行分析。
二、提炼解决办法
这个问题大的方向有两步，1 、 统计词频 ； 2 、返回topK。
如果这两步中涉及的数据都能放入内存中，那么最不济 O(N^2) 便可以解决。不过由于内存无法承受，这两步的解决似乎都点问题。
一、 统计词频
1、压缩数据（不可行）
由上所诉，如果能压缩放入内存便可以解决问题。所以先考虑能否找到一种压缩数据的办法。但是通过上面的分析，即使转换为hash也无法存入内存，所以需要换一种思路。
2、归并统计（不可行）
既然hash不能把所有数据放入内存，那么至少可以放一部分。再加上利用磁盘的存储，把hash值在一定范围内的词存放到第 i 个文件中。这样每个文件直接互不相交，而且每个文件都能在内存中处理，一个一个文件的进行统计，那么统计词频的问题自然可以解决了。
这个想法看似可行，其实不然。
对于抽象问题所述，100w/1000 = 1000，所以至少需要1000个文件存放互不相交的词。但是这里有两个问题，1 是如何寻找这个hash函数，保证100w个词在hash后能平均分配到1000个文件中。 2 是需要保证这个hash函数不会产生冲突，不然的话会导致不同的词的统计到一起。
因此这个hash函数是比较难找的。（如果大家知道分享下啊）
3、仍然是归并（可行的解决办法）
上述2中的归并，是需要人为的把词分到不同的桶里。但是hash函数太难设计了。
不过受数据结构中对数值外排序的启发，我想到了类似排序归并的解决办法。对于抽象问题所述，首先按内存大小，把100w数据顺序分词1000份。对于每份数据，因为每个词在内存中对应了一个2进制数值，可以通过移位比较两两词之间的数值大小。这样，词直接可以进行比较了，因此就可以进行排序了。再利用外排序的方法，就可以构成一个归并的解，进而可以将所有数据进行统计。
复杂度为O(M/N * log(N) + M *log(M/N) ) 。 对于抽象问题，即O( 100w/100 * log(1000) (排序) + 100w * log(100w/1000) (归并) )
二、 返回topK
topK的方法有两种，一是 堆排序。 二是 K查找。
堆排序的时间复杂度是 O(logN) ，K查找的复杂度是 O(N) 。
但是空间复杂度，堆排序是O(K) ，K查找是 O(N) 。（K就是topK的K）
【海量数据处理问题（一）|海量数据处理问题（一） ---- 内存无法处理的词频统计】一、 堆排序（适合本题）
对于提到的抽象数据，使用堆排序更合适。首先拿出第一个文件中的1000条数据构造一个 top100的堆树。然后剩下的999个文件，每次从每个文件取500条数据放入内存，和top100的堆树重新构造堆。那么需要一遍文件读取就能得到top100的词。所以对于文件读取为主要时间消耗的外排来说，堆排序无疑更合适。
本题时间复杂度100*log100 + 100w * log100 + 1000 read file time
二、K查找（不可行）
似乎关于K查找相关文章不多，这里提一下。
K查找类似快排，一个头指针，一个尾指针。以头尾指针的中间值作为平衡点，调节平衡点两边数值大小（到这里和快排一致）。然后根据平衡点和K值的关系，选择头一半或尾一半进行上述递归的查找（快排是两边都查找）。直到平衡点和K相等退出。
因此K查找的时间复杂度为 N + N/2 + N/4 ... 1 ~ 2N ，为 O(N)
对于本题，如果强行在文件中直接进行K查找，那么时间消耗会非常大。因此不适合。
转载请注明出处，谢谢~http://www.cnblogs.com/xiaoboCSer/p/4202394.html
推荐阅读
- Docker应用:容器间通信与Mariadb数据库主从复制
- 使用协程爬取网页，计算网页数据大小
- Java|Java基础——数组
- Python数据分析(一)（Matplotlib使用）
- Jsr303做前端数据校验
- Spark|Spark 数据倾斜及其解决方案
- 数据库设计与优化
- 爬虫数据处理HTML转义字符
- 数据库总结语句
- MySql数据库备份与恢复