普通解法:分治,hash,归并,最大(小)堆,map reducer等算法,你的小内存导致了只能用时间换空间的做法, 比如多次的遍历,big set分裂成小set,使用磁盘索引等。
文艺解法(ibm研究院提供):基于priori algorithm.
三种解法楼下对号入座。:)
先遍历1G的大文件,按照Hash%1000取模将大文件映射成1000个小文件,保证了相同的词分到同一个小文件中,这样每个小文件大概1M大(也可以分多些小文件,这样每个文件大小就更小),就可以放入内存中。在每个小文件中使用Hash_map,以单词为key,出现的次数为value,然后用最小堆得到每个小文件出现频数最多的100个单词,最后归并排序,就可以得到了
购物篮模型
数据的购物篮模型用于描述两类对象之间一种多对多关系。其中的一类对象是项(item),另一类对象是购物篮(basket),也称交易(transaction)。每个购物篮由多个项组成的集合(itemset)构成。假设一个购物篮中项的总数目较少,相对于所有项的总数目要小的多(这其实就是一种分治的思想)。而购物篮的数目通常假设很大,导致在内存中无法存放。整个数据假定由一个购物篮序列的问题件来表示。按下述分布式文件系统的说法,所有购物篮是文件中的一系列对象,而每个购物篮是一种“项集”类型的数据。
频繁项集定义:一个在多个购物篮中出现的项集称为“频繁”项集。假定有多个支持度阈值(support threshod) s。如果I是一个项集,I的支持度(support)是指包含I( 即I是购物篮中项集的子集)的购物篮数目。
一系列词语集合。每个集合都是一个购物篮 ,而词语就是项。由于购物篮是集合,所以一个词语在某个购物篮中出现两次不会被考虑。原则上,项在购物篮中只能出现一次。另外,大写忽略。
- 空集是任何集合的子集。因此空集的支持度是8。
- 单元素集合{dog}的支持度为7,除(5)之外的购物篮中都出现。{cat}的支持度为6。{and}支持度为5。{a}和{training}支持度为3。{for}和{is}为2。其他均为1。若支持度阈值s=3,那么有5个频繁的单元素集合。
- 双元素集合。一个双元素集合中的两个单元素本身必须都是频繁的。因此 ,所有可能的双元素频繁集合只有10个。
参考资料:
1)http://www.dewen.io/q/6830
2)http://blog.csdn.net/zzran/article/details/8443655
3)http://blog.csdn.net/v_july_v/article/details/6279498/
4)http://rakesh.agrawal-family.com/papers/vldb94apriori.pdf
附录:
分布时文件系统(Distributed File System)
- 文件非常大,比如TB级的文件
- 文件极少更新。文件作为某些计算的数据读入,并且不时有额外的数据追加到文件尾部。距离来说,机票预定系统的数据量虽然很大,但由于其数据变化过于频繁,不适用DFS。
DFS中,文件被分成文件块(chunk),文件块的大小通常为64MB。文件块会被复制多个副本放在几个不同的计算节点上。同时,存放同一文件块不同副本的节点应分布在不同机架上,以避免某个机架发生故障时丢失所有副本。