首页所有驱动分类下载数据挖掘与人工智能搜索引擎与SEO技术备忘录站长随笔

介绍并制作布隆过滤器,提供接口DLL下载

2020-01-24 数据去重 浏览次数:115
 
简单的说,布隆过滤器就是将多个哈希函数的计算结果映射在一块存储区域(空间)上。

布隆过滤器主要应用于一些允许计算结果有一定错误率的场景,或者说,允许二次校验的场景。最常见的应用就是:重复数据查找。

布隆过滤器工作原理:

第一步:准备好一个存储空间,将空间全部置零。空间大小一开始定值是多少就是多少,后期不能改变。
第二步:将原始数据用多个哈希函数计算出结果,有多少个哈希函数,就有多少个结果。
第三步:将计算结果映射到之前准备的空间的某一位置上(即置1)。
第四步:开始判断,如果所有映射的位置都曾经被映射过,那么就说明这个数据有可能曾经出现过了;如果有任意一个位置从没被映射过,那么这个数据一定是第一出现。

用图来表示吧:



上图1假设我们已经做好了第一步,准备好了空间;也准备好了三个哈希函数,分别是:f1,f2,f3;有三个数据需要判断是否第一次出现,这三个数据分别是X,Y,Z。

第二步:每当对一个数据进行查找时,就将这个数据用三个哈希函数计算,得到三个哈希值。

第三步:然后用这三个哈希值按照某个公式(最简单的是取余数)映射到空间对应的位置上(已经被映射过的空间填写1;从未被映射过的空间填0)。

例如上图1里面,数据X和数据Y经过三个哈希函数计算最后的映射位置:
f1(x),f2(x),f3(x)最后分别映射到空间的位置是:第一位,第四位,第八位。
f1(y),f2(y),f3(y)最后分别映射到空间的位置是:第三位,第七位,第四位。

第四步:开始判断,由于一开始,所有位置都是空的,所以数据X将被判断为第一次出现;接下来到数据Y,数据Y的f3(y)函数映射到第四位,虽然这个位置被标记已使用,但是Y还有两个函数f1(y)和f2(y)映射到的位置是没有被使用过的,也就是说,满足了一下条件:如果有任意一个位置从没被映射过,那么这个数据一定是第一出现。所以数据Y虽然有一个位置跟数据X重合,但是数据Y依然被判断为第一次出现。

这就是布隆过滤器的原理,基于这个原理,可以明显看出,布隆过滤器是存在一些问题的,比较突出的问题是:错误率。就是有可能把一个新的数据误认为是已经出现过的旧数据。例如下面的图2:



在图1的基础上,现在要对一个新数据Z进行判断,但是由于函数f1(Z),f2(Z),f3(Z)所映射的位置分别为:第四位,第六位,第八位。而这三个位置全是曾经被其他数据映射过的,所以数据Z将会被误认为是重复的旧数据。

如何避免错误?

无法避免,这个只能说是尽量降低错误率。想降低错误率,可以增大空间,也可以增加哈希函数个数,但是增加哈希函数个数,虽然会减少误判,同时也会加快的消耗空间,因为空间大小后期不能改变,当空间被消耗到一定程度,错误率将会急剧增加。所以比较好的方法是,使用适量的哈希函数个数,空间越大越好。

另外一个问题就是,由于空间大小是不能变动的,所以设计时就相当于限制了以后可以处理的数据量,当数据量达到设计值时,就不能再使用这个过滤器了。

其实这个问题是可以解决的,就是将新的布隆过滤器和旧的进行串联,查询数据的时候逐个查询。

最后还有个缺点,因为一个位置可能会被多个数据映射,所以布隆过滤器只能添加新数据,不能修改和删除。

说完了布隆过滤器的缺点,再说说它的优点,优点就是速度快,占用空间小,在计算机里,可以用1位(一个字节有8位)来表示某个位置。

额外说的一些事情:

其实,我认为在第二步的时候,不必限制在哈希函数,第二步要的是一个尽量分散的数值(越分散越好),而使用哈希函数,是因为其可以产生散列数值。我试过,用一个比较好的随机函数,也是可以代替其中一个哈希函数的,方法就是用原始数据转化为随机种子,然后再调用随机函数产生映射数值,因为当随机种子相同时,得到的随机数也是相同的,然而好的随机函数是可以产生比较分散的数值的。

总的来说,一句话概括:布隆过滤器是一个带有错误率的快速查找器,不适合所有场景,但对于一些特殊场景,却是非常好的方案



这个代码很老了,不记得什么时候写的了,貌似是2012年之前写了~~

调用方法:

先调用CreatebloomIndexFile创建一个布隆过滤文件,注意:这个函数会覆盖掉已经存在的旧文件,所以只有在需要创建新的布隆过滤器的时候才调用这个函数,以后使用同一个布隆过滤文件的时候,只需要调用LoadbloomIndexFile装载布隆过滤器文件。将文件装载成功后,就可以反复调用SearDataFrombloomFile函数,对数据进行过滤了。

**********************************************************************************
功能: 创建布隆索引文件
参数:
strFilePath: 文件路径
CanSaveDataCount: 希望能过滤的数据总量

返回值: 无

extern "C" __declspec(dllexport) void __stdcall CreatebloomIndexFile(const char* strFilePath,unsigned int CanSaveDataCount);

**********************************************************************************
功能: 装载已经存在的布隆索引文件

参数:
strFilePath: 文件路径
buf: 数据缓冲区
buflen: 缓冲区最大长度,如果函数执行成功,将返回缓冲区里的数据长度
needSpaceSzie: 缓冲区最少需要的长度

返回值: 装载成功返回TRUE,失败返回FALS

extern "C" __declspec(dllexport) bool __stdcall LoadbloomIndexFile(const char* strFilePath,char* buf,unsigned int* buflen,unsigned int* needSpaceSzie);

**********************************************************************************
功能: 判断数据是否在索引文件内,此函数线程不安全,如果多线程调用此函数,需要用同步锁(互斥)机制

参数:
DataBuf: 要判断的数据缓冲区
DataBuflen: 要判断的数据缓冲区长度
bloomFilebuf: 布隆文件的缓冲区
needSpaceSzie: 布隆文件缓冲区的长度
bolReadOnly: True: 只查询;False: 查询并写入

返回值: 如果在过滤器内返回TRUE,否则,返回FALSE

extern "C" __declspec(dllexport) bool __stdcall SearDataFrombloomFile(const char* DataBuf,unsigned int DataBuflen,char* bloomFilebuf,unsigned int bloomFilebuflen,bool bolReadOnly);

DLL下载地址:bloomfilter.dll
留言

有啥想说的就说吧,有啥想问的就问吧
Good good study, day day up!

名称

Email

内容

预览(只读), 点击返回编辑.

 
最新文章
 
留言
版权所有 © 2020 mypcrun.com.
桂ICP备19002156号桂公网安备 45070202000667号
这回把网站设计得那么漂亮,这下子不会被人笑了吧。