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有两个第三方插件实现了此功能:

    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为例:

1
2
3
4
5
6
7
8
9
10
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

输出结果:

1
2
3
4
5
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开头,否则会出错。

-------------本文结束感谢您的阅读-------------