pybloom去重_ 字节宝

环境

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

代码语言：javascript复制

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

代码语言：javascript复制

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 可以自动扩容

代码语言：javascript复制

# -*- 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：

代码语言：javascript复制

#! /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

https 网络安全 github scala git

0 人点赞