11
回答
挑战大家的算法:超大集合数据的快速查找算法,web爬虫url采集过滤算法
利用AWS快速构建适用于生产的无服务器应用程序,免费试用12个月>>>   

Web信息的采集,通常是利用爬虫等工具去遍历万维网,把万维网看做是一个以网页为节点, 网页间链接为边的超大规模有向图,然后利用图的遍历算法对连接url进行遍历采集,  在遍历过程中,需要判断待采集的页面(表现为url)是否已经被采集过,这就需要把已经采集的网页url记录下来,组成已采集的网页地址集合(假设为:visited-url-set), 当新的采集开始之前,首先判断这个 url 是否在“ vistited-url-set ” 集合中,如果在,说明该url已经被采集过,否则采集该网页,并把这个url记录在 visited-url-set中。

大家可以想象这个 visited-url-set 集合的数据是多么的大,可以是百万,千万,亿,千亿等 数量级, 如何能在如此之大的集合中快速查找, 这些url采用何种方式存储?

 不知道大家对这种存储和查找算法 有没有接触过??  想知道

<无标签>
举报
山哥
发帖于7年前 11回/3K+阅
共有11个答案 最后回答: 7年前

先跟下:网上比较流行的算法是:Bloom Filter 算法,这种算法非常的快,但是会出现误判断错误,即:将不属于集合的元素误认为属于集合,但是这种误判断的概率很低。

对于不能容忍有误报情况发生的地方,就不适合使用 Bloom Filter 算法了。

看怎么存储了,visited-url-set存储方式要很有讲究,合理的存储方式效率就会大大的增加。

1、首先按照网站字母分类,意思如下:

a1.com a2.net ... 作为一类存储在一处,数量级最多就百万

可以这么理解,即按网址的头一个字母建表存储。A表存a开头的网址,B表存b开头的网址。

2、再来,a1.com站搜索过的网址存一处,数量最多就10万这个级别,可以用文件形式存储了或单独建个库,索引起来速度也不会慢。

千亿、亿级的索检转化为百万、十万这个级别的相信速度应该会快上好多倍。

Google BigTable uses Bloom filters to reduce the disk lookups for non-existent rows or columns. Avoiding costly disk lookups considerably increases the performance of a database query operation.

引用来自#9楼“JSON”的帖子

引用来自#8楼“linxiuxiu”的帖子

找了一天,没有找到 Bloom Filter 的PHP实现...

知道的支会一声.

http://code.google.com/p/php-bloom-filter/

在一台普通台式机上测试...

$field = 100000000,  时

new self(strlen(bitset_to_string($field)));

就花掉了  425ms ,

这样的性能实在无法用于生产环境.

有没有办法做成像 extension 方式加载, 只需要初始化一次, 就要可以永久使用?

顶部