统计：Delicious数据集中收藏最多的书签是哪些？（有【存疑】）
之前从网上下载到Delicious的书签数据集，从200309.bz2~200712.bz2，每月一个.bz2压缩文件，总共6.7G左右（解压缩应该40G左右）。
这些天一直在做怎么统计这些数据，得到收藏最多的书签。基本思路简单，就是扫描每个文件，保存出现的次数，最后做排序，得到Top K个书签。
关于海量数据处理，July在教你如何迅速秒杀掉：99%的海量数据处理面试题列了很多方法来实现，基本思想都是大而化小，分而治之，各个击破。
我一直在看Hash的部分，希望能实现Hash+堆排序的算法，因此把这个数据拿来用。
不过在实现中还是有很多问题。
一、扫描文件
数据集给的是.bz2文件，一一解压出来不仅麻烦，还占存储空间（约40G），而且之后做Hash的时候，还需要再占用40G空间，电脑存储空间不够。
因此，在网上搜索能直接读取.bz2文件的方法，具体见前文：bz2:Java中读取bz2文件数据
二、内存不足
最开始的想法是：创建一个HashMap<String, Integer>，放入url和count。但在执行过程中，发现内存不足。
为了查看到底是哪些对象占用内存，搜索了计算Object内存的方法，具体见前文：Java：如何查看Object的大小
如那个所说，使用这种方法，在放入260W行之后，HashMap占内存185M。其实很容易算出来：
虽然保存的url长度不一，但一般如："http://www.nordlys.no/debatt/article253576.ece"的长度是46，每个char占内存2byte，所以url占内存46*2=92byte，260W行则占内存：260W * 92byte = 239,200,000，约为239M。
而我的eclipse内存最大设置是350M。何况，现在来看所有文档估计有5亿行左右，不重复的虽然没统计但也肯定远大于260W了。因此，需要另想办法。
对于无法一下放入内存的数据，July也给出了办法，是：将大文件通过hash映射到N个小文件中，之后对每个小文件分别统计Top k，最后汇总统计总的Top k。
这里有个我之前不解的地方，即：如何保证相同的url都出现在同一个小文件中。其实很简单，只需要取url的hashcode，然后根据此hashcode对N取余，决定将其放入哪个小文件中即可。这样，对相同url的统计就不会遗漏（其实还是当时对hash没有理解。。）
方法是这样，但是是否可行？
这里需要考虑：
1. 需要分成多少个小文件才合适？
2. N值太大的话，在写入过程中，会不会FileOutputStream太多也会占用内存过大而死掉？
我先测试了一下，写了10000个FileOutputStream，每个创建一个txt文件，写入一行，最后关闭。测试FileOutputStream[] 总的占内存大小，结果发现没多大，也就十多M的样子。这下OK了。
那考虑需要分成多少个小文件呢？
之前对文件总量没有太好的估计，随便选了一个2000的值。这样，40G的文件平均下来，每个txt文件就是20M。
由于不知道创建多个文件+每个文件较小和少数文件+每个文件较大那个比较快（需要比较写入速度和读取速度），所以没有深入研究这个N该如何取最合适。在此【存疑】，以后要是感兴趣可以再研究。目前来看，2000个文件还是OK的。
三、Top 1和Top k
最开始为了简单，写的是Top1的代码，只需要比较一个就好了。在测试通过之后，改写为Top k的代码，同时，希望尽可能完整的保存原始信息（包括：date，hashcode，url，tags）。因此，写了新类BookMark.java，并重写了其中的equals方法和hashcode方法，具体操作可以参考前文：孪生兄弟：How to override equals and hashCode Method in Java?
另外，对于排序算法，现在还没写堆排序，使用的最简单的时间复杂度为O(n^2)的排序。等我再修改后，对比一下各个排序算法的效果。
好了，架构完成！
在调试了n多个bug之后，表示测试通过。
在测试的时候，估算了下，6.7G的.bz2文件大概需要跑7、8个小时，因此，在晚上睡觉前运行。第二天早上起来，尼玛，竟然还没运行完！预估错误！才跑了1/3左右的数据，约1.6亿行，索性不跑了，开始统计，最后结果如下：
*Delicious书签数据集200309.bz2~200612.bz2(该文件只跑了430W行，没跑完)，bz2文件总大小2.64G，写入的2000个txt文件总大小为15.4G，总行数为1亿6170万行，总耗时8个小时左右。
*运行环境：Intel Core i3 CPU M380 2.53G * 4，eclipse -Xmx为350M，window xp sp3，32位。
*还剩200701.bz2~200712.bz2文件（剩下的文件总共4G）。
*最后得到的Top 10的书签为：
URL:http://www.alvit.de/handbook/ Count:64922
URL:http://slashdot.org/ Count:51204
URL:http://www.flickr.com/ Count:52396
URL:http://script.aculo.us/ Count:69018
URL:http://www.last.fm/ Count:43641
URL:http://www.oswd.org/ Count:39915
URL:http://en.wikipedia.org/wiki/Main_Page Count:40104
URL:http://www.lifehacker.com/ Count:43137
URL:http://www.pandora.com/ Count:62574
URL:http://www.netvibes.com/ Count:45967
终于到接收成果的时候了，可以看出，03-06年最火的收藏是flicker, last.fm, wiki, lifehacker, pandora这样耳熟的名字。
下一步工作：
1. 修改排序算法，比较各个排序算法的时间复杂度；
2. 按照要求的错误率p，设计布隆过滤器，统计不重复的url个数；
3. 改进布隆过滤器，统计出现奇数次的url个数（即：bit为0/1的个数，或可删减的布隆过滤器）；
4. 改进布隆过滤器，统计出现k次的url的个数；
5. 可否统计出现k次的url有哪些？怎么保存和实现？（只维护一个出现次数小于k的HashMap？应该也不够）
参考资料：
