天津网站定制,外文网站建站,网站名称需要注册吗,网站访客qq抓取原理今天的文章和大家一起来学习大数据领域一个经常用到的算法——布隆过滤器。如果看过《数学之美》的同学对它应该并不陌生#xff0c;它经常用在集合的判断上#xff0c;在海量数据的场景当中用来快速地判断某个元素在不在一个庞大的集合当中。它的原理不难#xff0c;但是设…今天的文章和大家一起来学习大数据领域一个经常用到的算法——布隆过滤器。如果看过《数学之美》的同学对它应该并不陌生它经常用在集合的判断上在海量数据的场景当中用来快速地判断某个元素在不在一个庞大的集合当中。它的原理不难但是设计非常巧妙老实讲在看《数学之美》之前我也没有听说过这个数据结构所以这篇文章也是我自己学习的笔记。 原理 在我之前的理解当中如果想要判断某个元素在不在集合当中经典的结构应该是平衡树和hash table。但是无论是哪一种方法都逃不开一点都需要存储原值。
比如在爬虫场景当中我们需要记录下之前爬过的网站。我们要将之前的网址全部都存储在容器里然后在遇到新网站的时候去判断是否已经爬过了。在这个问题当中我们并不关心之前爬过的网站有哪些我们只关心现在的网站有没有在之前出现过。也就是说之前出现过什么不重要现在的有没有出现过才重要。
我们利用平衡树或者是Trie或者是AC自动机等数据结构和算法可以实现高效的查找但是都离不开存储下所有的字符串。想象一下一个网址大概上百个字符大约0.1KB如果是一亿个网址就需要10GB了如果是一百亿一千亿呢显然这么大的规模就很麻烦了今天要介绍的布隆过滤器就可以解决这个问题而且不需要存储下原值这是一个非常巧妙的做法让我们一起来看下它的原理。
布隆过滤器本身的结构非常简单就是一个一维的bool型的数组也就是说每一位只有0或者1是一个bit这个数组的长度是m。对于每个新增的项我们使用K种不同的hash算法对它计算hash值。所以我们可以得到K个hash值我们用hash值对m取模假设是x。刚开始的时候数组内全部都是0我们把所有x对应的位置标记为1。
举个例子假设我们一开始m是10K是3。我们遇到第一个插入的值是”线性代数“我们对它hash之后得到135那么我们将对应的位置标记成1. 然后我们又遇到了一个值是”高等数学“hash之后得到189我们还是将对应位置赋值成1会发现1这个位置对应的值已经是1了我们忽略就好。 如果这个时候我们想要判断”概率统计”有没有出现过怎么办很简单我们对“概率统计”再计算hash值。假设得到145我们去遍历一下对应的位置发现4这个位置是0说明之前没有添加过“概率统计”显然“概率统计”没有出现过。
但是如果“概率统计”hash之后的结果是138呢我们判断它出现过就错了答案很简单因为虽然138这个hash组合之前没有出现过但是对应的位置都在其他元素中出现过了这样就出现误差了。所以我们可以知道布隆过滤器对于不存在的判断是准确的但是对于存在的判断是有可能有错误的。
代码
布隆过滤器的原理很简单明白了之后我们很容易写出代码
# 插入元素
def BloomFilter(filter, value, hash_functions):m len(filter)for func in hash_functions:idx func(value) % mfilter[idx] Truereturn filter# 判断元素
def MemberInFilter(filter, value, hash_functions):m len(filter)for func in hash_functions:idx func(value) % mif not filter[idx]:return Falsereturn True 错误率计算 之前的例子当中应该展示得很明白了布隆过滤器虽然好用但是会存在bad case也就是判断错误的情况。那么这种错误判断发生的概率有多大呢
这个概率的计算也不难由于数组长度是所以插入一个bit它被置为1的概率是插入一个元素需要插入k个hash值所以插入一个元素某一位没有被置为1的概率是。插入n个元素之后某一位依旧为0的概率是它变成1的概率是。
如果在某次判断当中有一个没有出现过的元素被认为已经在集合当中了那么也就是说它hash得到的位置均已经在之前被置为1了这个时间发生的概率为
这里用到了一个极限
我们来求一下冲突率最低时k的取值为了方便计算我们令代入
两边求导 我们令导数等于0来求它的极值 我们将代入可以求出最值时的
同理我们也可以预设定集合元素n和错判率p来求解对应的n同样利用上面的公式推算可以得到
如果我们允许一定的容错并且能够大概估计会出现的元素的个数那么完全可以使用布隆过滤器来代替传统的容器判重的方法。这样不仅效率极高而且对于存储的要求非常小。 灵魂拷问 原理也明白了代码也看懂了这个时候我们来思考一个问题布隆过滤器可以删除元素吗
很遗憾布隆过滤器是不支持删除的。
因为布隆过滤器的每一个bit并不是独占的很有可能多个元素共享了某一位。如果我们直接删除这一位的话会影响其他的元素。
还是用上面的例子举例我们删除线性代数线性代数对应的位置是135虽然我们并没有删除高等数学但是由于我们移除了高等数学也用到的位置1如果我们再去判断高等数学是否存在就会得到错误的结果虽然我们并没有删除它。
当然在一些必须要有删除功能的场景下也是有办法的。方法也很简单就是修改数据结构将原本每一位一个bit改成一个int当我们插入元素的时候不再是将bit设置为true而是让对应的位置自增而删除的时候则是对应的位减一。这样我们删除单个结果就不会影响其他元素了。
这种方法并不是完美的由于布隆过滤器存在误判的情况很有可能我们会删除原本就不存在的值这同样会对其他元素产生影响。
布隆过滤器是一个优缺点都非常明显的数据结构优点非常出色速度足够快内存消耗小代码实现简单。但是缺点也很明显不支持删除元素会有误判的情况。这样特点鲜明的数据结构真的非常吸引人。 优点
(1) 、时间复杂度是O(K),k代表hash()的个数
(2) 、空间利用率高全量存储但又不存储数据本身
缺点
(1) 、有误判两个不同的key通过k个hash()函数之后可能映射到相同的bit位上
(2) 、不能计数不能删除元素本身
