文章目录
- BloomFilter原理和使用
-
- BloomFilter原理
-
- 适用场景
- 基础性质
- False-Positive推导
- Bloom Filter之python包
-
- pybloomfilter
- pybloomfilter代码实例
BloomFilter原理和使用
BloomFilter原理
适用场景
在很多场景下，会遇到流式元素的处理，最主要的是集合判断与去重问题。例如我们会判断一个email地址是否在黑名单中，网络爬虫会判断一个url是否已经存在于待抓取列表或者已抓取，视频库的去重等等。不幸的是通常情况下这类问题面临的数据规模都较大，比如网络爬虫系统的抓取url通常达到数亿级别，如果采用哈希表存储这些url将会耗费大量的内存以至于在实际生产使用过程中几乎不可用，而布隆滤波器确实一种近乎完美的替代方案。（谨记：大部分的近似方案虽然会带来少量的损失，但是会给性能和效果带来极大的提升）
在个人研究方面，有一个场景需要对item进行流式处理，最主要的操作便是查询是否已经存在，由于需要查询的信息量较大，且需要在分布式场景下进行全局状态维护，为了降低分布式维护信息的量，减少通信代价，故希望采用bloom filter期待有所作用。
本实验目前采用最基础的bloom filter的形式，暂不深入研究bloom filter各种拓展形式。
基础性质
布隆过滤器（Bloom Filter）是由布隆（Burton Howard Bloom）在1970年提出的。它实际上是由一个很长的二进制向量和一系列随机映射函数组成，布隆过滤器可以用于检索一个元素是否在一个集合中。
文章：Space/Time Trade-offs in Hash Coding with Allowable Errors
布隆滤波器会有一个m位的bit数组（每位初始设为0）以及k个随机哈希函数，每个哈希函数的输出都是一个（0，m-1）之间的一个数（对应bit数组下标）。
添加操作：输入x，对于每一个哈希函数，计算j= hash(x)，将m_bit[j] 设成1；
查询操作：输入x，对于每一个哈希函数，计算j= hash(x)，如果m_bit[j] 不等于1，则说明x不在集合中，否则如果k个函数的映射位都为1，说明x存在于集合中。
优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率（假正例False positives，即Bloom Filter判断某一元素存在于某集合中，但是实际上该元素并不在集合中）和删除困难，但是没有识别错误的情形（即假反例Falsenegatives，如果某个元素确实没有在该集合中，那么Bloom Filter 是不会报告该元素存在于集合中的，所以不会漏报）。
False-Positive推导
假设k个哈希函数完全随机，即以等概率选在（0，m-1）中的一个数，那么m_bit中某一位在添加元素时一次哈希没有被置位的概率是：
经过k次哈希没有被置位的概率是：
添加n个元素该位仍然没有被置位的概率是：
那么该位在添加n个元素后被置位的概率是：
现在对于一个新元素，要判断其是否在集合中，如果判断该元素存在于集合中，说明k个哈希位都为1，但是有可能会错误的把实际不存在于集合中判断为存在于集合中（False Positive），该事件发生的概率为：
可以看出随着m（位数组大小）的增加，False Positive概率会下降，同时随着插入元素个数 n 的增加，False Positives的概率又会上升。
对于给定的m、n，哈希函数的个数k的最优值为：
对于给定的False Positives概率 p和元素个数n，位数组m的最优值为：
Bloom Filter之python包
- pybloom
- pybloom_live
- pybloomfilter
这里仅介绍pybloomfilter的安装与使用
pybloomfilter
Pybloomfilter是一个用java实现的bloomfilter版本，为了兼顾效率，内部位数组使用C实现。
Pybloomfilter构造时允许传入capacity（即n），error rate，位数组大小（m），哈希函数个数（即k）以及一个序列化的nmap文件。
官方文档：http://axiak.github.io/pybloomfiltermmap/ （需要开全局代理，否则可能被墙）
下载地址：https://github.com/axiak/pybloomfiltermmap
在ubuntu中可以直接使用命令安装：
sudo pip install pybloomfiltermmap
在安装过程中出现如下问题（不管是下载后编译安装还是直接使用命令安装）：
发扬曾经学到优良传统，遇到错误首先应该分析出错返回的结果，然后根据理解再去找问题。
这里发现是编译的时候有相关的c库找不到，于是开始谷歌：
真正解决问题的博客：https://blog.csdn.net/yingyujianmo/article/details/49634511
在ubuntu上安装软件时，经常出现这样的问题：
/usr/bin/ld: cannot find -l****
问题解决办法，详细内容参考上述博客。
另外还有一种常见解决方案，为给出博文的第一种，不过此处并没有解决问题：http://blog.51cto.com/eminzhang/1285705
核心问题在于该库是存在的，但是名称有所变化，需要增加一个软链接：
具体操作：
首先定位问题，使用命令：
locate libcrypto
查看，发现
libcrypto.so.XXX
是存在的，但是
libcrypto.so
是不存在。
因此进入对应的文件夹，建立对应的软链接：
[email protected]:/lib/x86_64-linux-gnu$ sudo ln -s libcrypto.so.1.0.0 libcrypto.so
问题解决
类似的
/usr/bin/ld: cannot find -l****
问题都可以通过这种方法解决。
进而使用命令编译安装
pybloomfilter
：
成功！
另外，使用如下命令安装
pybloomfilter
，安装貌似没有问题，但是无法使用，会出现错误：
pip install pybloomfilter
运行时出现错误：
应该是缺少了某C语言相关的包，之后尝试
pybloom
包，可以运行，API接口和
pybloomfilter
不太一样，速度上估计也慢一些，似乎还有一些不准确，这里主要使用
pybloomfilter
。
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)
输出结果为：
与0.001的既设值很接近，还是非常精确且值得信赖的。
关于API还需要进一步学习总结，以及在图划分的实际测试结果，见后续博客。