江苏龙网

  1. 主页 > 生活百科 > >

海量数据处理的算法 海量数据处理

海量数据处理(海量数据处理算法)
主要说说Bloom Filter算法 。
Bloom Filter(BF)是一种高效的空之间的随机数据结构，它使用位数组简洁地表示一个集合，可以判断一个元素是否属于该集合 。判断是否有一组元素是一种快速概率算法 。Bloom Filter可能会做出错误的判断，但不会错过判断 。也就是BloomFilter判断元素不再组装，所以肯定不是 。如果集合中存在判断元素，那么判断有一定的概率是错误的 。因此，BloomFilter不适合那些“零误差”的应用 。
与其他常见算法(如哈希、二分搜索法)相比，BloomFilter在可以容忍低错误率的应用中大大节省了空 。
BloomFilter详细介绍:针对海量数据处理的Bloom Filter详细讲解 。
[适用范围]
它可以用来实现数据字典，数据的重复判断，或者集合的交集 。
【基本原则和要点】
要点:一是位数组，而是k个独立的哈希函数 。
1)位阵列:
假设BloomFilter使用m位数组来存储信息 。在初始状态下，Bloom Filter是一个m位的数组，每个位都设置为0，也就是BF整个数组的元素都设置为0 。
2)k个独立的散列函数 。
为了表示一组n个元素，s = {x1，x2，...，xn}，BloomFilter使用k个独立的Hash函数，将集合中的每个元素映射到{1，...，m} 。
当我们的资源网络向Bloom Filter添加任何元素x时，我们使用k个哈希函数来获取k个哈希值，然后将数组中相应的位设置为1 。也就是说，ith散列函数映射的位置hashi(x)将被设置为1(1≤i≤k) 。请注意，如果一个位置被多次设置为1，只有第一次有效，接下来的几次无效 。下图中，k=3，两个哈希函数选择相同的位置(左边第五个位置，也就是第二个“1”) 。
3)判断是否有一组元素 。
在判断y是否属于这个集合时，我们只需要使用k个哈希函数就可以得到k个哈希值 。如果hashi(y)的所有位置都是1(1≤i≤k)，即所有k个位置都设置为1，那么我们将把y看作集合中的元素，否则我们将把y看作集合中的非元素 。在下图中，y1不是集合中的元素(因为y1在一个地方指向“0”位) 。Y2要么属于这个集合，要么恰好是假阳性 。
显然，这个判断并不能保证搜索结果100%正确 。
BloomFilter的缺点:
1)布隆过滤器无法从布隆过滤器集合中删除元素 。因为这个元素对应的位会影响其他元素 。因此，一个简单的改进是计数布隆过滤器，它可以通过用计数器数组替换位数组来支持删除 。此外，BloomFilter的哈希函数选择也会影响算法的效果 。
2)另一个重要问题是如何根据输入元素个数n确定位数组m的大小和哈希函数的个数，即哈希资源网络函数的选择会影响算法的效果 。当哈希函数的数量k=(资源网络ln2)*(m/n)时，错误率最小 。在误差率不大于E的条件下，m必须至少等于n*lg(1/E)才能表示任意一组n个元素 。但m应该更大，因为至少有一半的位数组应该是0，所以m应该是>:=nlg(1/E)*lge，大约是nlg(1/E)的1.44倍(lg代表以2为底的对数) 。
例如，如果误差率是0.01，那么m应该是n的13倍左右，所以k大约是8 。
注意:
这里，m的单位不同于n的单位，m的单位是比特，而n的单位是元素的个数(准确的说是不同元素的个数) 。通常，单个元素的长度有许多位 。因此，使用布隆过滤器通常在内存方面是经济的 。
通常，BF可以与一些键值数据库一起使用，以加快查询速度 。由于BF使用的空非常小，所以所有BF都可以驻留在内存中 。这样，对于大多数不存在的元素，我们只需要访问内存中的BF，只有一小部分，我们需要访问硬盘上的键值数据库 。从而大大提高了效率 。
[扩展]
Bloom filter将集合中的元素映射到位数组，并通过是否所有k个映射位(k是哈希函数的个数)都为1来指示元素是否在集合中 。计数布隆过滤器(CBF)将位数组中的每个位扩展成一个计数器，从而支持删除元素 。光谱布隆过滤器(SBF)将其与收集元素的出现次数相关联 。SBF使用计数器中的最小值来近似元素的出现频率 。
[问题示例]
给你两个文件，A和B，每个存储50亿个URL，每个占用64字节，内存限制为4G，这样你就可以找出A和B文件的常用URL 。如果是三个甚至n个文件呢？
根据这个问题，我们计算内存占用 。4g = 2 32约为40亿*8约为340亿比特，n = 50亿，如果误码率为0.01，则需要约650亿比特 。目前有340亿元可用，相差不大，可能会增加出错率 。另外，如果这些urlip一一对应，就可以转换成ip，大大简化了 。实现部分的代码稍后会分享，我们会在近期继续研究算法的这一部分 。朋友们，请期待吧！！！


推荐阅读


上一篇：婴儿湿疹怎么办 小儿湿疹膏

下一篇：关节脱位了怎么办？ 脱臼的处理