URL去重
URL去重主要有两种方式:
- 布隆过滤器去重
Hash表去重
布隆过滤器去重
- 需要一个数组和k个映射函数,初始将数组array所有位置都置0。
- 将元素集S={s1,s2……sn}中每个元素sj,通过k个映射函数{f1,f2……fk}映射为K个值{g1,g2……gk},将array中对应的array[g1],array[g2]……array[gk]置为1.
- 若元素item通过映射函数得到的k个值在array中对应的值全为1,则item在S中,否则不在。
python有两个第三方插件实现了此功能:
- Python-bloomfilter
项目地址:https://github.com/jaybaird/Python-bloomfilter - Pybloomfiltermmap
项目地址:https://github.com/axiak/Pybloomfiltermmap
官方文档:https://axiak.github.io/pybloomfiltermmap/
Pybloomfiltermmap模块实现两类布隆过滤器:Bloomfilter和ScalableBloomfilter。
Bloomfilter是一个定容过滤器,error_rate指最大误报率;
ScalableBloomfilter是一个不定容过滤器。1
2
3from pybloomfilter import BloomFilter
# 创建一个capacity等于100万,error rate等于0.001的bloomfilter对象
bfilter = BloomFilter(1000000,0.001,'bf_test.bloom')方法add是添加元素,若元素已存在,则返回True,若不存在则返回False,并添加到过滤器中。
布隆过滤器存在一定的误判率。
Hash表去重
遍历URL列表,判断每个URL是否在去重后的列表里,如果不在,则加入列表。根据哈希表存放的位置,可以分为两种方式:一种是基于内存的Hash表去重;一种是基于硬盘的Hash表去重。
方法一:利用内存Hash表去重
使用如下代码:
1
2
3
4
5
6......
result = []
for url in url_list:
if url not in result:
result.append(url)
......由于URL长度不固定,单个URL长度越长,使用URL存储内存和性能损耗过快,此时需对URL进行Hash运算压缩,如:16位md5运算。
1
2
3
4
5
6
7# Python 2.x
import hashlib
print hashlib.md5("hello").hexdigest()[8:-8]
# Python 3.x
import hashlib
print(hashlib.md5("hello".encode('utf-8')).hexdigest())[8:-8]方法二:利用BerkeleyDB去重
BerkeleyDB是一个key-value database,简单的说,就是一个在disk上的hash表。存储的是“key-value”键值对。
下载安装Berkeley DB安装。Python需要安装bsddb3模块来提供BerkeleyDB数据库的操作接口。
Berkeley DB次你在四种数据访问模式:- btree:树结构,存储任意复杂key和value
- hash:hash存储,访问量巨大时,效果好
- queue:队列操作,只能存储定长数据,key必须是数字
- recno:与queue相似,但支持边长value
1
2
3
4
5import bsddb
mydb = bsddb.db.DB()
mydb.open('mydb.db',dbtype = bsddb.db.DB_HASH, flags = bsddb.db.DB_CREATE)
mydb.put("key","value")
mydb.close()设置数据访问方法:
btree是 bsddb.db.DB_BTREE, hash是bsddb.db.DB_HASH
queu 是 bsddb.db.DB_QUEUE, recno 是bsddb.db.DB_RECNO
设置flags参数为DB_CREATE表明如果数据文件不存在则新建一个空的数据文件。
使用DB的put方法存储一个Key/Value对
URL去似去含
相似URL特征:
- 协议相同(protocol)
- 主机名相同(host)
- 端口相同(port)
- 资源路劲相同(path)
- 参数名所组成列表相同或包含
python2.x使用urlparse,python3.x使用urllib,以python2.x为例:1
2
3
4
5
6
7
8
9
10import urlparse
url='http://www.baidu.com:80/s?wd=python&ie=utf-8#123'
r=urlparse.urlparse(url)
print r
print r.netloc
print r.hostname
print r.port
print urlparse.parse_qs(r.query)
res = urlparse.urlsplit(url)
print res
输出结果:1
2
3
4
5ParseResult(scheme='http', netloc='www.baidu.com:80', path='/s', params='', query='wd=python&ie=utf-8', fragment='123')
www.baidu.com:80
www.baidu.com
80
SplitResult(scheme='http', netloc='www.baidu.com:80', path='/s', query='wd=python&ie=utf-8', fragment='123')
r = urlparse.urlparse(url)返回一个6个元组,分别为scheme, netloc, path, params, query, fragment,ParseResult类还有几个常用方法:
res.username
res.password
res.hostname
res.port
res.geturl()
urlunparse与之相反,将6个元组组成一个string。
urlsplit将path与params合并为path,存在urlunsplit与之相反功能。
使用urlparse.parse_qs()函数获取r.query中的参数列表,输出为字典。
注释:url必须以http://xxx开头,否则会出错。