URL去重去似

URL去重

URL去重主要有两种方式：

布隆过滤器去重
Hash表去重

布隆过滤器去重
1. 需要一个数组和k个映射函数，初始将数组array所有位置都置0。
2. 将元素集S={s1,s2……sn}中每个元素sj，通过k个映射函数{f1,f2……fk}映射为K个值{g1，g2……gk},将array中对应的array[g1],array[g2]……array[gk]置为1.
3. 若元素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
3
from 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
5
import 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为例：

import 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

输出结果：

ParseResult(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开头,否则会出错。

URL去重

布隆过滤器去重

Hash表去重

方法一：利用内存Hash表去重

方法二：利用BerkeleyDB去重

URL去似去含