位图、布隆过滤器及大数据处理

2017-08-24 10:24 阅读 1,440 次 评论 0 条

位图(bitmap)

位图是哈希的一种扩展,本质上是一种数组,即每个二进制位表示一种状态,0表示不存在,1表示存在。

我们用腾讯的一道大数据题引出位图结构吧。比如说:给40亿个不重复且无序的无符号整数,现在给你一个整数让你快速判断出它是否存在?(假设我们只有4G内存)

这道题就是典型的海量数据处理,40亿个数需要160亿字节,等同于16GB,一次性是无法将40亿个数据加入到内存中的,因此引入了位图。

对于这些无符号整数我们只需要两种状态来标识,0标识不存在,1标识存在,因此40亿无符号整数只需要2^32/8=512MB,显然这是可以接受的。

布隆过滤器(bloomfiliter)

布隆过滤器是哈希+位图的变种,它的基本思想是:通过一个Hash函数将一个元素映射成一个位矩阵中的一个点,我们只需查看这个点是不是1就知道集合中是否存在它。

但是由于哈希冲突的原因,即不同的元素经过散列函数后可能产生相同的哈希地址,我们很可能导致误判。为了降低误判的概率,我们将一个元素经过多个散列函数映射到多个位上,如果这几个位都为1,我们认为它是存在的;如果有一位为0,我们认为它不存在。

注意:对于布隆过滤器来说,存在不一定存在,但不存在一定不存在。

大数据处理案例

⒈ 给一个超过100G大小的log file,log中存着ip地址,设计算法找到出现次数最多的ip地址?

解决方法:哈希切分。将100G的文件分成1000份,通过同一个散列函数映射到相应的文件,同一个ip一定会映射到同一个文件,利用map进行存储,其他文件中的ip只需调用map[]进行插入,最后map中value最大的对应的key就是出现次数最多的ip。

⒉ 与上题相同,如何找到top K的ip?如何直接用Linux命令实现?

解决方法:哈希切分后统计每个ip出现的次数,然后利用最小堆获取出现次数最多的前k个ip。

⒊ 给定100亿整数,设计算法找到只出现一次的整数?

解决方法一:将100亿整数切分成100份,平均每份大约400M左右,将每一份加载到内存中,利用哈希表查找只出现一次的数,最后将100份的结构汇总查找。

解决方法二:位图。具体查看上述位图的实现。这道题一般考察的是扩展,比如找出出现1、2货多次,只用一个bit位表示状态显然是不够的,因此我们可以用两个比特位表示:00表示没出现,01表示出现1次,10表示出现2次,11表示出现多次。

⒋ 给两个文件,分别有100亿整数,我们只有1G内存,如何找到两个文件的交集?

解决方案一:将一个文件切割成100份,分别将每一份加载到内存中,然后用第二个文件中的数据到每一份中查找,事件复杂度为(O(n^2))。

解决方案二:哈希切分。通过一个散列函数,将相同的数映射到同一个文件中,并对文件进行编号。如果两个文件存在交集,一定会在编号相同的文件中产生交集,这时候只需要将他们编号相同的文件比较即可,时间复杂度为(O(N))。

解决方案三:位图。将一个文件中的数据映射到位图中,然后再用第二个文件中的数据到位图中查找。时间复杂度为(O(N))。

⒌ 1个文件有100亿个int,1G内存,设计算法找到出现次数不超过2次的所有整数?

⒍ 给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?

解决方案一:哈希切分。与第四题的方法一致,只需要将query转换成int,然后再经过散列函数映射到文件中。

解决方案二:布隆过滤器。将其中一个文件的内存映射到位图中,在用另一个文件中的内存到这个位图中寻找。

⒎ 如何扩展BloomFilter使得它支持删除元素的操作?

因为一个布隆过滤器的key对应多个位,冲突的概率比较大,所以不支持删除,因为删除有可能影响到其他元素。如果要对其元素进行删除,就不得不对每一个位进行引用计数。

⒏ 如何扩展BloomFilter使得它支持引用计数操作?

用一个vector<size_t>,将集合中的每个元素经过多个散列函数映射到多个位置,而每个位置的值则表示有多少个元素映射到这个位置。

⒐ 给上千个文件,每个文件大小为1K-100M,给n个词,设计算法对每个词找到所有包含它的文件,你只有100K内存?

① 一个文件info 准备用来保存n个词和包含其的文件信息。

② 首先把n个词分成x份。对每一份用生成一个布隆过滤器(因为对n个词只生成一个布隆过滤器,内存可能不够用)。把生成的所有布隆过滤器存入外存的一个文件Filter中。

③将内存分为两块缓冲区,一块用于每次读入一个布隆过滤器,一个用于读文件(读文件这个缓冲区使用相当于有界生产者消费者问题模型来实现同步),大文件可以分为更小的文件,但需要存储大文件的标示信息(如这个小文件是哪个大文件的)。

④ 对读入的每一个单词用内存中的布隆过滤器来判断是否包含这个值,如果不包含,从Filter文件中读取下一个布隆过滤器到内存,直到包含或遍历完所有布隆过滤器。如果包含,更新info 文件。直到处理完所有数据。删除Filter文件。

⒑ 有一个词典,包含N个英文单词,现在任意给一个字符串,设计算法找出包含这个字符串的所有英文单词?

本题需要借助一种特殊的数据结构---字典树。又称单词查找树、Trie树,是一种哈稀树的变种。它的应用有:用于统计、排序和保存大量的字符串,经常被搜索引擎系统用作文本词频统计。

优点:利用字符串的公共前缀减少查询时间,最大限度地减少无畏的字符串比较,查询效率高于哈希表。

缺点:每一个节点都开辟了26个字母的空间,而不管是否使用,浪费空间。

基本性质:根节点不包含字符,除根节点外每个节点都只包含一个字符。从根节点到某一节点,路径上所有经过的字符连接起来,为该节点对应的字符串。每个节点的所有子节点包含的字符都不相同。

解决方案:用给出的N个单词简历一棵与上述字典树不同的字典树,用任意字符串与字典树中的每个节点中的单词进行比较,在每层中查找与任意字符串首字母一样的,找到则遍历其下面的子树,直到全部相同。

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:位图、布隆过滤器及大数据处理 | 术与道的分享
分类:编程素养 标签:, ,
1024do.com导航_术与道导航平台

发表评论


表情