最近在研究Python,想用Python写一个爬虫来爬数据。
爬虫有几个关键的地方,一个是防止如何递归地重复爬一个网址,一个就是页面信息的解析。
那么这里主要介绍一下如何通过bloom filter达到判断一个网址是否被爬过。
bloom filter的介绍refer:http://blog.csdn.net/jiaomeng/article/details/1495500
下面我们具体来看Bloom Filter是如何用位数组表示集合的。初始状态时,Bloom Filter是一个包含m位的位数组,每一位都置为0。
为了表达S={x1, x2,…,xn}这样一个n个元素的集合,Bloom Filter使用k个相互独立的哈希函数(Hash Function),它们分别将集合中的每个元素映射到{1,…,m}的范围中。对任意一个元素x,第i个哈希函数映射的位置hi(x)就会被置为1(1≤i≤k)。注意,如果一个位置多次被置为1,那么只有第一次会起作用,后面几次将没有任何效果。在下图中,k=3,且有两个哈希函数选中同一个位置(从左边数第五位)。
这个图我看的不是很明白,所以我自己画了一个图。
如果在Python下面使用bloom filter,可以导入一个包来使用。
http://sourceforge.net/projects/pybloom/
相关推荐
硬核 - Redis 布隆(Bloom Filter)过滤器原理与实战.doc
bloom filter布隆过滤器学习资料大全,收集了很多相关的论文,并总结了各种布隆过滤器的变种
分布式环境下改进的BloomFilter过滤技术
Bloomfilter布隆过滤器技术分享PPT。 介绍了布隆过滤器的使用方法与适用场景等。 适合用于技术分享。
介绍Bloom Filter(布隆过滤器)原理、实现及具体应用,包含9个不同PPT及PDF文档资料,对Bloom Filter感兴趣、想学习的同学可以下载查看下
Bloom Filter是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的:在判断一个元素是否属于某个集合时,有可能会把不...
bloomfilter.js, 使用FNV的JavaScript bloom filter快速散列 Bloom过滤器This过滤器实现使用非加密 Fowler-Noll-Vo散列函数来实现速度。用法var bloom = new BloomFilter( 32 * 256,//number of bits to all
自制布隆过滤器,采用八种不同哈希函数来获取随机数,错误率低
bloom-filter-scala, 用于 Scala的Bloom过滤器,最快的JVM Scala的 Bloom filter 概述Bloom过滤器是一种空间高效的数据结构,用于测试某个元素是否是集合的成员。 false 正匹配是可能的,但 false 负数不是。 ...
Java-BloomFilter, 在Java中,一个独立的Bloom过滤器 java-bloomfilterJava bloomfilter是一个独立于Java的Bloom过滤器实现。 它旨在在不需要额外库开销的情况下包含在现有项目中。 第一个版本是由 Ian的博客条目...
改进的Bloom filter主要将两个标准的Bloom filter组成二维并行Bloom filter,对RFID采集数据所包含的两个属性值tagID和readerID进行并行过滤。经实验可见,标准Bloom filter与哈希过滤(hash filter)相比具有明显的...
bloom filter 布隆过滤器,这是源码,简单易学易用
linux下编写的网络爬虫,可以实现bloom filter 去重过滤,不过是用来垂直爬取www.8684.cn网站的。运行的时候请输入www.8684.cn
高效的挡住无效的请求和流量,可用于数据库查询前,过滤非命中查询。也可以用来防止redis缓存击穿。
bloom filter(布隆过滤器)应用很广泛的高效算法,研究研究
Bloom filter是一个简明的空间效率极高的随机的数据结构。用Bloom filter 表示 cache 内容 ,可以高效地实现cache 协作。本文对BloomFilter及其改进型进行了综述性分析,探讨了它的实用性。
This is the bloom filter of 2.5 Million ... BloomFilter bf=new BloomFilter(); BitSet bitSet=bf.readBit(fileName); bf.setBits(bitSet); System.out.println(bf.exist("password")); } it will says true.
该文档中包含 bloomFilter过滤器中用到的对于字符串进行hash的hash函数共十一个,并带有测试程序..
leveldb中bloomfilter的优化。