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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

推荐学习书目

› 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

这是一个创建于 4242 天前的主题，其中的信息可能已经有所发展或是发生改变。

网址

抓取

网址库

23 条回复 • 1970-01-01 08:00:00 +08:00

polythene

2013-04-11 15:25:34 +08:00

Bloom Filter

woshifyz

2013-04-11 15:28:16 +08:00

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

richiefans

2013-04-11 15:31:34 +08:00

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

cloudzhou

2013-04-11 15:32:34 +08:00

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

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

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

sivacohan

2013-04-11 15:35:16 +08:00

bloom filter
SimHash

littlekfc

2013-04-11 16:03:16 +08:00

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

lookhi

2013-04-11 16:05:37 +08:00

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

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

Muninn

2013-04-11 17:17:39 +08:00 via Android

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

Angelkid

2013-04-11 17:34:01 +08:00

我刚好也在纠结这个问题

binux

2013-04-11 17:39:42 +08:00

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

Livid

MOD

2013-04-11 17:46:25 +08:00 via iPhone

把 URL 的 sha256 放到 Redis 里查。

foxidea

2013-04-11 17:49:20 +08:00

告诉你怎么快速：

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

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

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

amazingjxq

2013-04-11 18:26:47 +08:00

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

soho176

2013-04-11 18:42:57 +08:00

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

soho176

2013-04-11 18:49:21 +08:00

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

lookhi

2013-04-11 20:03:07 +08:00

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