BloomFilter原理和使用

本文主要是介绍BloomFilter原理和使用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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是不存在。

因此进入对应的文件夹，建立对应的软链接：

w@ubuntu:/lib/x86_64-linux-gnu$ sudo ln -s libcrypto.so.1.0.0 libcrypto.so

问题解决

类似的/usr/bin/ld: cannot find -l****问题都可以通过这种方法解决。

进而使用命令编译安装pybloomfilter：

w@ubuntu:~/Desktop/pybloomfiltermmap-master$ sudo python setup.py install

成功！

另外，使用如下命令安装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 randomfrom 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 += 1print "error_rate:%s" % (error_in*1.0/1000000)

输出结果为：

与0.001的既设值很接近，还是非常精确且值得信赖的。

关于API还需要进一步学习总结，以及在图划分的实际测试结果，见后续博客。

这篇关于BloomFilter原理和使用的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---