pybloom去重

周小董

发布于 2019-03-25 11:21:06

2K0

发布于 2019-03-25 11:21:06

文章被收录于专栏：python前行者python前行者

环境

python3.6
pip3 install bitarray-0.8.1-cp36-cp36m-win_amd64.whl（pybloom_live依赖这个包，需要先安装）
pip3 install pybloom_live

下载地址：https://www.lfd.uci.edu/~gohlke/pythonlibs/

1. pybloom_live

ScalableBloomFilter

from pybloom_live import ScalableBloomFilter

#mode=ScalableBloomFilter.SMALL_SET_GROWTH
sbf = ScalableBloomFilter(initial_capacity=100, error_rate=0.001, mode=ScalableBloomFilter.LARGE_SET_GROWTH)

url = "www.baidu.com"
url2 = "www.douban,com"

sbf.add(url)

print(url in sbf)   # True
print(url2 in sbf)  # False

BloomFilter

from pybloom_live import BloomFilter

bf = BloomFilter(capacity=1000)

bf.add("www.baidu.com")

print("www.baidu.com" in bf)   # True
print("www.douban.com" in bf)  # False

2. pybloom

BloomFilter 是定容。
ScalableBloomFilter 可以自动扩容

# -*- coding: utf-8 -*-
from pybloom import BloomFilter

f = BloomFilter(capacity=1000, error_rate=0.001)# capacity是容量, error_rate 是能容忍的误报率,超过误报率，抛出异常
print([f.add(x) for x in range(10)])#[False, False, False, False, False, False, False, False, False, False]
print(all([(x in f) for x in range(10)]))#True
print(10 in f)#False
print(5 in f)#True


f = BloomFilter(capacity=1000, error_rate=0.001)
print(f.capacity)#等于capacity
print('len(f):',len(f))
for i in range(0, f.capacity):
    f.add(i)
print('len(f):',len(f))
print((1.0 - (len(f) / float(f.capacity))) <= f.error_rate + 2e-18)#True


from pybloom import ScalableBloomFilter

sbf = ScalableBloomFilter(mode=ScalableBloomFilter.SMALL_SET_GROWTH)
count = 10000
for i in range(0, count):
    sbf.add(i)
print((1.0 - (len(sbf) / float(count))) <= sbf.error_rate + 2e-18)#True

3. Pybloomfilter（只适合py2）

Pybloomfilter（https://axiak.github.io/pybloomfiltermmap/#）是一个用java实现的bloomfilter版本，为了兼顾效率，内部位数组使用C实现。

Pybloomfilter构造时允许传入capacity（即n），error rate，位数组大小（m），哈希函数个数（即k）以及一个序列化的nmap文件。

下面示例代码简单的展示了如何使用Pybloomfilter：

#! /usr/bin/env python
# -*- coding:utf-8 -*-

import os
import sys
reload(sys)
sys.setdefaultencoding('utf-8')

import random

from pybloomfilter import BloomFilter

# 创建一个capacity等于100万，error rate等于0.001的bloomfilter对象
bfilter = BloomFilter(1000000,0.001,'bf_test.bloom')

# 添加100个元素
for x in xrange(1000000):
    bfilter.add(str(x))

# 与nmap文件同步
bfilter.sync()


# 测试error rate
error_in = 0
for x in xrange(2000000):
    if str(x) in bfilter and x > 1000000:
        error_in += 1

print "error_rate:%s" % (error_in*1.0/1000000)

最终结果输出：

error_rate:0.001009；非常接近于我们设置值0.001。

布隆滤波器是利用很小的错误率代价完美实现了海量数据规模下的去重和判断问题，在平时的大数据研究和开发中，不要总为完美的解决方案而费尽心血，尝试多使用近似的替代方案。

参考：https://github.com/jaybaird/python-bloomfilter https://blog.csdn.net/wh_springer/article/details/52193110 https://blog.csdn.net/a1368783069/article/details/52137417 https://www.jianshu.com/p/f57187e2b5b9

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018年08月01日，如有侵权请联系 cloudcommunity@tencent.com 删除

https