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
soho176
V2EX  ›  Python

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

  •  
  •   soho176 · 2013-04-11 15:16:27 +08:00 · 10678 次点击
    这是一个创建于 4226 天前的主题,其中的信息可能已经有所发展或是发生改变。
    23 条回复    1970-01-01 08:00:00 +08:00
    polythene
        1
    polythene  
       2013-04-11 15:25:34 +08:00   ❤️ 1
    Bloom Filter
    woshifyz
        2
    woshifyz  
       2013-04-11 15:28:16 +08:00   ❤️ 1
    bloom filter ,你要判断不在集合内,所以不会错,而且是常数时间
    richiefans
        3
    richiefans  
       2013-04-11 15:31:34 +08:00
    同求实例 这个算法还是没怎么理解
    cloudzhou
        4
    cloudzhou  
       2013-04-11 15:32:34 +08:00   ❤️ 2
    我提供一个思路给你,在索引里面,定长数据查询效率要远远高于不定长数据,url是不定长数据,但是可以转变成为定长,如果散列足够随机,冲突不大的话,那么可以考虑,比如:
    把url转换成为long值,hash(url) -> id
    long值的范围是 2^64,说实话,我不认为你能达到产生冲突的可能性
    然后做非uniq索引,在每次查询结果列表里面做遍历,在冲突小的情况下,每次基本返回一条数据。

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

    这其实就是hash的基本思想。
    sivacohan
        5
    sivacohan  
       2013-04-11 15:35:16 +08:00   ❤️ 1
    bloom filter
    SimHash
    littlekfc
        6
    littlekfc  
       2013-04-11 16:03:16 +08:00   ❤️ 1
    用bloom filter有个问题,它是有误判的。比如新的一条url,在bloom filter里查得系统已经存在了。但这会有一定的概率是错误的。数据量还不大的话这个概率很小很小。但是随着记录越来越多,误判的概率会增大的。所以,如果业务要求不能漏url的话,bloom filter不适合,否则可以考虑。
    lookhi
        7
    lookhi  
       2013-04-11 16:05:37 +08:00
    无论怎么做都行,最简单的MD5(URL),比对的时候简单的比对下就好了。

    等你md5都不够用了的话,系统早就要升级了。
    Muninn
        8
    Muninn  
       2013-04-11 17:17:39 +08:00 via Android
    你想变快 肯定要缩短url 想要缩短 肯定会损失信息
    损失了信息肯定会碰撞
    所以别纠结了
    这个地方想完美是没辙的
    和永动机一样做不到的
    Angelkid
        9
    Angelkid  
       2013-04-11 17:34:01 +08:00
    我刚好也在纠结这个问题
    binux
        10
    binux  
       2013-04-11 17:39:42 +08:00
    上10亿了吗?没有?直接hash查库
    Livid
        11
    Livid  
    MOD
       2013-04-11 17:46:25 +08:00 via iPhone   ❤️ 2
    把 URL 的 sha256 放到 Redis 里查。
    foxidea
        12
    foxidea  
       2013-04-11 17:49:20 +08:00   ❤️ 1
    告诉你怎么快速:

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

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

    然后再封装好算法,进行查、写入
    amazingjxq
        13
    amazingjxq  
       2013-04-11 18:26:47 +08:00
    @foxidea 为什么要反序一次?这样做有什么好处吗
    soho176
        14
    soho176  
    OP
       2013-04-11 18:42:57 +08:00
    @lookhi 当网址足够多的时间 这样的对比 效率很低吧
    soho176
        15
    soho176  
    OP
       2013-04-11 18:49:21 +08:00
    @woshifyz Bloom Filter在时间空间这两个因素之外又引入了另一个因素:错误率。在使用Bloom Filter判断一个元素是否属于某个集合时,会有一定的错误率。也就是说,有可能把不属于这个集合的元素误认为属于这个集合(False Positive),但不会把属于这个集合的元素误认为不属于这个集合(False Negative)。在增加了错误率这个因素之后,Bloom Filter通过允许少量的错误来节省大量的存储空间。
    这样的结果就是有可能这个页面还没有爬过 却跳过了。。。
    lookhi
        16
    lookhi  
       2013-04-11 20:03:07 +08:00
    @soho176 等足够多的时候再考虑。后续可以考虑@foxidea类似的方法。现在你想太多了!
    workaholic
        17
    workaholic  
       2013-04-11 21:52:48 +08:00
    Bloom Filter ++
    csx162
        18
    csx162  
       2013-04-11 22:42:13 +08:00
    先搞清楚慢的地方在哪里。。。
    dingyaguang117
        19
    dingyaguang117  
       2013-04-12 00:06:46 +08:00
    lddhbu
        20
    lddhbu  
       2013-04-12 18:54:13 +08:00
    trie树可以吧
    charnugagoo
        21
    charnugagoo  
       2013-04-14 04:46:43 +08:00
    很大的话,一般用bloomfilter, 如果再大或者是分布式爬虫的话就需要更高级的东西了。
    PS:似乎还可以同时考虑做simhash,找出重复页面。
    Zuckonit
        22
    Zuckonit  
       2013-04-19 16:02:48 +08:00
    hash啊。。。。。常量级
    h4x3rotab
        23
    h4x3rotab  
       2013-04-19 16:40:24 +08:00
    数量没有达到分布式的级别的话,哈希表就完全可以满足你的要求,任何一个实现良好的哈细表都能提供O(1)的查询和修改时间,也不会出错
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3070 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 13:42 · PVG 21:42 · LAX 05:42 · JFK 08:42
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.