A-A+

C++爬虫原理(七):布隆过滤器和暴雪字符串哈希的思考

2015年11月23日 大数据 暂无评论 阅读 218 次

结合布隆过滤器按位存储的思想,和暴雪字符串哈希算法的思想,写出适合所写程序的哈希。(主要参考,布隆过滤器)

如下:

一、首先申请约为1亿比特位的空间 = 1亿/8 字节 = 13MB,8次哈希,所以需要 8*13MB = 100MB的内存。

这里我为什么要取接近1亿的质数为哈希表大小呢?大约测试了8-9个垂直行业站点,数据量随机(几十万到千万),URL相似度存在高度相似等情况,这里有个奇怪的现象,在哈希表大小为1亿左右的时候,哈希冲突递减的最强。哈希表长度大于1亿的时候,冲突递减衰弱,而付出的内存代价得不偿失。反而8次哈希,同时碰撞,几乎可以避免这种极小的冲突。

二、按位存取哈希结果,8个哈希表,分别存取8个哈希算法的结果。取同时碰撞(都为1)才为真(相等字符串),否则假。首先根据哈希值,计算出索引位,也就是在那个字节号存储,然后计算出哈希在8字节中,所占的位置,置1。

三、读一个URL串,哈希计算。当所有的哈希位都为1的时候,也就是已经抓取(有可能碰撞产生),否则就是没有被抓取,继续任务。

四、存在极小情况的漏抓,但是不会出现重抓的情况。

测试结果:
测试数据均为:随机URL串,存在高度相似(规律站内翻页)、高度散列、最大长度256或者更高、中文串交叉等真实URL串,非构造出。

例如:

https://www.baidu.com/123213/344444/453453/657657/786786/1_1.html

https://www.baidu.com/123213/344444/453453/657657/786786/1_2.html

https://www.baidu.com/123213/344444/453453/657657/786786/1_3.html

30W,无任何碰撞!

100W,无任何碰撞!

500W,无任何碰撞!

1000W,(这时候txt文件大小已经接近1GB+),测试结果无任何碰撞

总结:千万级数据量的大小程序使用该方法不产生任何冲突(测试3次1000W随机站点数据),适用于垂直爬虫的抓取!所用哈希算法为最常见的字符串哈希算法,如果结合优秀的哈希,碰撞次数更小。

Copyright:www.cplusplus.me Share、Open- C/C++程序员之家

给我留言