用python 做爬虫，抓取网站，在抓取的过程中会碰到重复的网址，随着抓取网址的越来越多，网址库越来越大，如果每次爬到网址都去网址库对比一下是否重复，这样的结果就是效率越来越低了，有什么办法或者算法提高过滤重复网址的效率？

推荐学习书目

› Learn Python the Hard Way

Python Sites

› PyPI - Python Package Index

› http://diveintopython.org/toc/index.html

› Pocoo

值得关注的项目

› PyPy

› Celery

› Jinja2

› Read the Docs

› gevent

› pyenv

› virtualenv

› Stackless Python

› Beautiful Soup

› 结巴中文分词

› Green Unicorn

› Sentry

› Shovel

› Pyflakes

› pytest

Python 编程

› pep8 Checker

Styles

› PEP 8

› Google Python Style Guide

› Code Style from The Hitchhiker's Guide

This topic created in 4956 days ago, the information mentioned may be changed or developed.

网址

抓取

网址库

23 replies • 1970-01-01 08:00:00 +08:00

polythene

Apr 11, 2013

Bloom Filter

woshifyz

Apr 11, 2013

bloom filter ,你要判断不在集合内，所以不会错，而且是常数时间

richiefans

Apr 11, 2013

同求实例这个算法还是没怎么理解

cloudzhou

Apr 11, 2013

我提供一个思路给你，在索引里面，定长数据查询效率要远远高于不定长数据，url是不定长数据，但是可以转变成为定长，如果散列足够随机，冲突不大的话，那么可以考虑，比如：
把url转换成为long值，hash(url) -> id
long值的范围是 2^64，说实话，我不认为你能达到产生冲突的可能性
然后做非uniq索引，在每次查询结果列表里面做遍历，在冲突小的情况下，每次基本返回一条数据。

如果你的数据量很小，允许一定误差，那就根本不考虑冲突的情况。

这其实就是hash的基本思想。

sivacohan

Apr 11, 2013

bloom filter
SimHash

littlekfc

Apr 11, 2013

用bloom filter有个问题，它是有误判的。比如新的一条url，在bloom filter里查得系统已经存在了。但这会有一定的概率是错误的。数据量还不大的话这个概率很小很小。但是随着记录越来越多，误判的概率会增大的。所以，如果业务要求不能漏url的话，bloom filter不适合，否则可以考虑。

lookhi

Apr 11, 2013

无论怎么做都行，最简单的MD5(URL),比对的时候简单的比对下就好了。

等你md5都不够用了的话，系统早就要升级了。

Muninn

Apr 11, 2013 via Android

你想变快肯定要缩短url 想要缩短肯定会损失信息
损失了信息肯定会碰撞
所以别纠结了
这个地方想完美是没辙的
和永动机一样做不到的

Angelkid

Apr 11, 2013

我刚好也在纠结这个问题

binux

Apr 11, 2013

上10亿了吗？没有？直接hash查库

Livid

MOD

PRO

Apr 11, 2013 via iPhone

把 URL 的 sha256 放到 Redis 里查。

foxidea

Apr 11, 2013

告诉你怎么快速：

把 url 地址反序一次， md5 一次，然后取 md5 前三位

命名为表名 string tableName = "table_"+md5[0]+md5[1]+md5[2];

然后再封装好算法，进行查、写入

amazingjxq

Apr 11, 2013

@foxidea 为什么要反序一次？这样做有什么好处吗

soho176

Apr 11, 2013

@lookhi 当网址足够多的时间这样的对比效率很低吧

soho176

Apr 11, 2013

@woshifyz Bloom Filter在时间空间这两个因素之外又引入了另一个因素：错误率。在使用Bloom Filter判断一个元素是否属于某个集合时，会有一定的错误率。也就是说，有可能把不属于这个集合的元素误认为属于这个集合（False Positive），但不会把属于这个集合的元素误认为不属于这个集合（False Negative）。在增加了错误率这个因素之后，Bloom Filter通过允许少量的错误来节省大量的存储空间。
这样的结果就是有可能这个页面还没有爬过却跳过了。。。

lookhi

Apr 11, 2013

@soho176 等足够多的时候再考虑。后续可以考虑@foxidea类似的方法。现在你想太多了！