我正在阅读布隆过滤器,他们看起来很傻.使用bloom过滤器可以完成的任何事情,你可以在更少的空间内,更有效率地完成,使用单个散列函数而不是多个,或者它看起来像是什么.为什么要使用布隆过滤器？它有什么用？
来自维基百科:
与用于表示集合的其他数据结构相比,布隆过滤器具有强大的空间优势,例如自平衡二进制搜索树,尝试,哈希表或简单数组或条目的链接列表.其中大多数都要求至少存储数据项本身,这可能需要从少量位到小整数,到任意数量的位,例如字符串(尝试是一个例外,因为它们之间可以共享存储)具有相同前缀的元素).链接结构会为指针带来额外的线性空间开销.另一方面,具有1%误差和最佳值k的布隆过滤器每个元素仅需要大约9.6位 - 无论元素的大小如何.这种优势部分来自于其紧凑性,继承自阵列,部分来自其概率性质.如果1%的误报率似乎太高,每次我们每个元素添加大约4.8位时,我们将它减少十倍.
对我来说很清楚.
布隆过滤器不会存储元素本身,这是关键点.你不使用布隆过滤器来测试一个元素是否存在,你用它来测试它是否肯定不存在,因为它保证没有假阴性.这使您无需为集合中不存在的元素(例如磁盘IO查找它们)执行额外的工作.
并且所有这些空间都远远小于哈希表(对于大型数据集可能部分在磁盘上).虽然您可以将布隆过滤器与哈希表之类的结构结合使用,但一旦您确定该元素有可能存在.
因此,示例使用模式可能是:
你在磁盘上有很多数据 - 你决定你想要的错误限制(例如1%),它规定了m的值.然后确定最佳k(根据文章中给出的公式).您可以从此磁盘绑定数据中填充一次过滤器.
现在你有了RAM中的过滤器.当您需要处理某个元素时,您会查询过滤器以查看它是否有可能存在于您的数据集中.如果没有,则不会进行额外的工作.没有磁盘读取等(如果它是一个哈希或树,你将不得不这样做).
否则,如果过滤器显示"是,它就在那里",则有1%的可能性是错误的,所以你做了必要的工作才能找到答案.99%的时间,它真的会在那里,所以这项工作并非徒劳无功.
亚历克斯已经解释得很好.对于那些仍然没有掌握它的人,希望这个例子可以帮助你理解:
让我说我在谷歌工作,在Chrome团队工作,我想在浏览器中添加一项功能,通知用户他输入的网址是否是恶意网址.所以我有一个大约100万个恶意URL的数据集,这个文件的大小约为25MB.由于大小很大(与浏览器本身的大小相比较大),我将这些数据存储在远程服务器上.
情况1:我使用带哈希表的哈希函数.我决定使用有效的散列函数,并通过散列函数运行所有100万个url以获取散列键.然后我创建一个哈希表(一个数组),其中哈希键将为我提供放置该URL的索引.所以现在一旦我散列并填充了散列表,我就检查它的大小.我已经在哈希表中存储了所有100万个URL及其密钥.所以大小至少为25 MB.此哈希表由于其大小将存储在远程服务器上.当用户出现并在地址栏中输入URL时,我需要检查它是否是恶意的.因此,我通过哈希函数运行URL(浏览器本身可以这样做),我得到该URL的哈希键.我现在必须使用该哈希密钥向我的远程服务器发出请求,以检查具有该特定密钥的哈希表中的特定URL是否与用户输入的内容相同.如果是,那么它是恶意的,如果不是,则它不是恶意的.因此,每次用户输入URL时,都必须向远程服务器发出请求以检查它是否是恶意URL.这将花费大量时间,从而使我的浏览器变慢.
案例2:我使用布隆过滤器.使用多个散列函数通过布隆过滤器运行100万个URL的整个列表,并且在大的0数组中将相应的位置标记为1.假设我们想要1%的误报率,使用布隆过滤器计算器(http://hur.st/bloomfilter?n=1000000&p=0.01),我们得到布隆过滤器所需的大小仅为1.13 MB.这个小的大小是预期的,即使数组的大小很大,我们只存储1或0而不是散列表中的URL.这个数组可以被视为位数组.也就是说,由于我们只有两个值1和0,我们可以设置单个位而不是字节.这将减少8倍的空间.这个1.13 MB的布隆过滤器由于体积小,可以存储在网页浏览器中!因此,当用户出现并输入URL时,我们只需应用所需的哈希函数(在浏览器本身中),并检查bloom过滤器中的所有位置(存储在浏览器中).任何位置的值为0都告诉我们此URL绝对不在恶意URL列表中,用户可以自由进行.因此,我们没有调用服务器,因此节省了时间.值1表示URL可能位于恶意URL列表中.在这些情况下,我们调用远程服务器,在那里我们可以使用一些其他哈希函数和一些哈希表,如第一种情况一样,检索并检查URL是否实际存在.由于大多数时候,URL不太可能是恶意的,因此浏览器中的小型布隆过滤器会将其显示出来,从而通过避免调用远程服务器来节省时间.只有在某些情况下,如果bloom过滤器告诉我们网址可能是恶意的,只有在那些情况下我们才会调用服务器.'可能'是99%的权利.
因此,通过在浏览器中使用小型bloom过滤器,我们节省了大量时间,因为我们不需要为输入的每个URL进行服务器调用.
我们可以看到具有单个散列函数的散列表完全用于与布隆过滤器不同的目的.希望这能清除你的疑惑:)
我已经为Python中的恶意URL测试任务实现了一个bloom过滤器.代码可以在这里找到 - https://github.com/tarunsharma1/Bloom-Filter 代码很容易理解,自述文件中提供了详细的描述.
我将与什么是布隆过滤器的解释开始,所能做和不能做什么,我们为什么需要它,显示的直观描述它是如何工作,然后举一些例子说明时,他们可能是有用的.
因此标准布隆过滤器是一种概率数据结构,可以*:
将元素添加到集合中
通过告诉definitely not in the set或检查元素是否在集合中possibly in the set
这possibly in the set正是它被称为概率的原因.使用智能词语意味着可能存在误报(可能存在错误地认为该元素为正的情况)但是否定的假阴性是不可能的.
但它不能 *:
从集合中删除项目
为您提供当前所有元素的列表
*这套可以/不能用于基本布隆过滤器.因为它是很久以前创建的有用数据结构,所以人们发现了如何使用其他有用的功能来扩充它.
但是等一下:我们已经知道一个数据结构可以回答所有这些,而不会模糊"可能",也没有所有限制(无法删除,无法显示所有).它被称为一组.这里有一个布隆过滤器的主要优点:它具有空间效率和空间常数.
这意味着我们存储多少元素并不重要,空间将是相同的.是的,带有10^6元素的布隆过滤器(无用布隆过滤器)将使用与布隆过滤器相同的空间,其中10^20元素和布隆过滤器具有相同的空间0元素.那需要多少空间？由你来决定(但有一个交易:你拥有的元素越多,你对你的possible in the set回答越不确定.
另一个很酷的事情是它是空间不变的.将数据保存到集合时,必须实际保存此数据.因此,如果您存储,this long string in the set您必须至少使用27个字节的空间.但是对于1%的误差和k **的最佳值,每个元素需要~9.6位(<2字节)(无论是短文本还是大文本墙).
另一个特性是所有的操作都以固定时间,这是绝对不一样的以成套(记住,如果set碰撞,它可以在恶化的情况下分期常量时间O(n)的时间).
**k是布隆过滤器中使用的散列函数的值
我不会描述布隆过滤器是如何工作的(维基百科文章可以很好地解释所有内容).在这里,我将简要介绍一下基础知识.
你启动一个长度为空的位数组 m
你选择k不同的哈希函数(越独立越好)
如果要添加元素,则计算k此值的所有哈希值并将相应位设置为1
如果要检查元素是否存在,还要计算所有k哈希值,如果未设置其中至少一个哈希值,则肯定不在集合中.否则它可以在集合中.
甚至这个描述也足以理解为什么我们不能确定(你可以从各种其他值中获取所有位).这是一个非常好的可视化工作方式.
那么何时可以使用bloom过滤器？简短的回答是无处不在,其中假阳性是可以接受的,在那里你会要检查,如果事情是在集,但即使他们都没有,它可以防御的第一线,以排除昂贵的呼叫核查员.
以下是更具体描述的列表:
在人们谈论布隆过滤器的几乎任何地方都描述了恶意网站和浏览器的标准示例
是一个密码弱:没有一大堆所有可能的弱密码,你可以检查密码是否肯定不弱与一个更小的布隆过滤器
如果您有文章列表和用户列表,则可以使用bloom过滤器显示用户尚未阅读的文章.有趣的是,你只能有一个过滤器(你检查user_id + article_id的组合是否存在)
比特币使用bloom过滤器进行钱包同步
Akamai的Web服务器使用Bloom过滤器来防止"一击"奇迹存储在其磁盘缓存中.一次性奇迹是用户只需要一次请求的Web对象,这是Akamai发现应用于其缓存基础架构近四分之三的内容.使用Bloom过滤器检测Web对象的第二个请求,并仅在第二个请求时缓存该对象,可防止单击奇迹进入磁盘缓存,从而显着减少磁盘工作负载并提高磁盘缓存命中率(取自Bloom过滤器中的示例)维基上的文章)
Bloom过滤器在生物信息学中非常有用.与使用常规哈希相比,它们可以更节省空间,特别是当您使用的字符串的大小可能是数亿字母,字母非常小,即{A,G,T,C}时.它们通常用于评估基因组中是否存在某种k聚体.还有一个用于相关的事情的例子在这里.
编辑:
多个散列函数用于最小化误报.希望是在所有k-hash函数之间,每个值在位数组中将具有与每个其他可能值相比的唯一签名.但是,确实存在误报,但可以将它们最小化到可管理的水平.使用此技术可以独立于其大小来哈希元素.当您搜索它们时,您使用每个哈希函数并检查以确保它们的位值都是1.
将其与人类基因组进行比较,其中元素大小的增加显着增加了哈希表的大小(表大小为4*4 k).假设您使用2位/字母对元素进行编码.
如果Bloom过滤器返回一个项目是该集合的成员,则存在一定误报的可能性.如果仅使用单个散列函数来指示集合中的成员资格,则误报的概率将高于使用多个散列函数.
京公网安备 11010802040832号 | 京ICP备19059560号-6 
