思路:从简单的排序谈到BitMap算法,再谈到数据去重问题,谈到大数据量处理利器:布隆过滤器。
情景1:对无重复的数据进行排序
@给定数据(2,4,1,12,9,7,6)如何对它排序?
方法1:基本的排序方法包括冒泡,快排等。
方法2:使用BitMap算法
方法1就不介绍了,方法2中所谓的BitMap是一个位数组,跟平时使用的数组的唯一差别在于操作的是位。
首先是开辟2个字节大小的位数组,长度为16(该长度由上述数据中最大的数字12决定的)如图
然后,读取数据,2存放在位数组中下标为1的地方,值从0改为1,4存放在下标为3的地方,值从0改为1....结果如图
最后,读取该位数组,得到排好序的数据是:(1,2,4,6,7,9,12)
比较方法1和方法2的差别:方法2中,排序需要的时间复杂度和空间复杂度很依赖与数据中最大的数字比如12,因此空间上讲需要开2个字节大小的内存,时间上需要遍历完整个数组。当数据类似(1,1000,10万)只有3个数据的时候,显然用方法2,时间复杂度和空间复杂度相当大,但是当数据比较密集时该方法就会显示出来优势。
情景2:对有重复的数据进行判重
数据(2,4,1,12,2,9,7,6,1,4)如何找出重复出现的数字?
首先是开辟2个字节大小的位数组,长度为16(该长度由上述数据中最大的数字12决定的)如图
当读取完12后,数组中的数据如下图:
当读取2的时候,发现数组中的值是1,则判断出2是重复出现的。
应用
应用1:某文件中包含一些8位的电话号码,统计出现的号码的个数?(判断有谁出现)
8为最大是99 999 999,大约是99M的bit,12.5MB的内存,就可以统计出来出现的号码。
应用2:某文件中包含一些8位的电话号码,统计只出现一次的号码?(判断有谁出现并且指出现1次)
需要扩展一下,可以用两个bit表示一个号码,0代表没有出现过,1代表只出现过1次,2代表至少出现2次。
应用3:有两个文件,文件1中有1亿个10位的qq号码,文件2中有5千万个10位qq号码,判断两个文件中重复出现的qq号。
首先建立10的10次方个大小的位数组(占用内存大约是1.25G),全部初始化为0,读取第一个文件,对应的qq号存放到对应的未知,数值改为1,如果重复出现仍是1.读取完毕第一个文件后,读取第二个文件,对应的位置为1则表示重复出现。
应用4:有两个文件,文件1中有1亿个15位的qq号码,文件2中有5千万个15位的qq号码,判断两个文件中重复出现的qq号。
应用4中,qq号码上升为15位的时候,显然内存是不够用了,这个时候怎么办?使用Bloom Filter(布隆过滤器)
Bloom Filter(布隆过滤器):
对于Bit-Map分析一下,每次都会开辟一块表示最大数值大小的bit数组,比如情景1中的16,将对应的数据经过映射到bit数组的下标,这其实是一种最简单的hash算法,对1去模。在上述应用4中,当qq号码改为15位的时候,Bit-Map就不太好用了,如何改进呢?解决办法:减少bit数组的长度,但是增加hash函数的个数
对于每一个qq号码,我用K个hash函数,经过k次映射,得到k个不同位置,假设k=3,那么对于一个qq号码,映射到位数组中3个不同的位置
当读取第二个包含5千万个qq号码的文件的时候,使用同样的3个hash函数进行映射,当3个位置全部是1的时候才表示出现过,否则表示没有出现过。
有什么疑问吗?
显然,对于一个qq号码,如果它在第一个文件中没有出现过,但是它映射的3个位置已经全部是1的情况会有吗?答案是会的,但是这种概率是可控的,可控的意思是:这种误差跟hash函数的个数和质量是有关系的,可以通过控制hash函数的个数和位数组的大小来控制误差概率。至于表示3者之间的关系精确的数学公式就不再详细研究了。
可以这样讲,布隆过滤器是Bit-Map的进一步扩展,对于大数据量判重,布隆过滤器可以在内存中进行判断,避免了对磁盘的读写,效率是很高的。以上是自己关于两者的理解,有错误望指教。
分享到:
相关推荐
下面是一个简单的布隆过滤器的C/C++实现,以及使用例程。使用sdbmhash字符串hash方法来进行hash。
LevelDB 学习笔记1:布隆过滤器.doc
做成dll可以在很多场合使用,如自己写爬虫,要判断一个url是否已经访问过,判断一个单词是否在某个字典内,当集合很大的时候,用布隆过滤器很有优势,不过使用前,请了解它的优缺点(缺点是有一定的误判率)
布隆过滤器,大家学过数据结构的应该都清楚,一般的字典树要实现嵌入和查找都内存的消耗非常大,布隆过滤器有BloomFilter,string, BKDRHash, APHash, DJBHash> bf五个参数你要查找的元素个数,查找元素类型,三个...
一个简单的golang布隆过滤器
使用java实现的布隆过滤器算法,jdk-1.7,使用java实现的布隆过滤器算法,jdk-1.7,使用java实现的布隆过滤器算法,jdk-1.7,
布隆过滤器在网页去重中的应用 , 海量数据处理中的一个绝好应用
自制布隆过滤器,采用八种不同哈希函数来获取随机数,错误率低
布隆过滤器JavaScript实现 用法 要在您的项目中使用BloomJS,只需从dist目录中导入bloom.min.js文件即可! 构造函数: var bloom = new Bloom(k, m, n, hashFunction) k :散列数量,默认为Math.max(Math.round(m ...
布隆过滤器C源码
布隆过滤器是空间高效的概率 数据结构,通过设想伯顿霍华德布卢姆于1970年,是用于测试一个是否元件是一个的成员组。可能会出现假阳性匹配,但否定否定匹配-换句话说,查询返回“可能在集合中”或“绝对不在集合中”...
布隆过滤器的python库,通过python setup.py install安装
基于Redis的布隆过滤器,内含scrapy示例程序,github地址:https://github.com/kongtianyi/BloomFilterRedis
布隆过滤器Bloom Filters的一个简单Java库
布隆过滤器 源码 java版 /** * This program is free software: you can redistribute it and/or modify * it under the terms of the GNU Lesser General Public License as published by * the Free Software ...
比如在字处理软件中,需要检查一个英语单词是否拼写正确(也就是要判断它是否在已知的字典中);在 FBI,一个嫌疑人的名字是否已经在嫌疑名单上;在网络爬虫里,一个网址是否被访问过等等。最直接的方法就是将集合中...
Bloomfilter布隆过滤器技术分享PPT。 介绍了布隆过滤器的使用方法与适用场景等。 适合用于技术分享。
自动清空过滤器内部信息的使用比率,传null则表示不会自动清理,当过滤器使用率达到100%时,则无论传入什么数据,都会认为在数据已经存在了当希望过滤器使用率达到80%时自动清空重新使用,则传入0.8
布隆过滤器的一个Go实现,参考bloomfilter.js
布隆过滤器插件