使用 Bloom 过滤器的优点是什么？

Bloom 过滤器在生物信息学中非常有用。与使用常规散列相比，它们可以更加节省空间，特别是当您正在处理的字符串的大小可以是使用非常小的字母表即{ A，G，T，C }的数亿个字母时。它们通常用于评估基因组中是否存在某种 k-mer。这里有一个用于与 给你相关的东西的例子。

编辑:

多个散列函数用于最小化误报。我们希望在所有 k-hash 函数之间，与其他所有可能的值相比，每个值在位数组中都有唯一的签名。然而，假阳性确实存在，但是它们可以被最小化到一个可管理的水平。使用这种技术，您可以散列其大小的元素 独立的。当您搜索它们时，您使用每个散列函数并检查以确保它们的位值都是1。

与人类基因组相比，元素大小的增加会显著增加哈希表的大小(表的大小为4 * 4^K)。这是假设您使用2位/字母对元素进行编码。

来自 维基百科:

Bloom 过滤器有很强的空间 优于其他数据结构 用于表示集合，例如 自平衡二叉搜索树, 尝试、哈希表或简单数组 或链接列表的条目。大多数 其中至少有一部分需要储存 数据项本身，这可以 要求从小数量到任何地方 对于小整数来说，对于一个 任意位数，如 for 字符串(try 是一个例外，因为 他们可以共享存储空间 前缀相同的元素) 结构产生额外的线性 指针空间 误差为1% 的最优滤波器 另一方面，k 的值, 只需要大约每个9.6位 元素ーー不管 这个优势来了 部分原因在于它的紧凑性 来自数组，部分来自它的 概率性质。如果1% 的错误 阳性率似乎太高，每个 每个元素增加4.8位的时间 我们把它减少十倍。

我很清楚。

开花过滤器本身不存储元素，这是关键点。您不需要使用 Bloom 过滤器来测试某个元素是否存在，而是使用它来测试它是否肯定存在 没有，因为它保证不会出现假负值。这使您不必为集合中不存在的元素做额外的工作(例如查找它们的磁盘 IO)。

而且所有这些都明显比哈希表(对于大型数据集而言，它可能部分存在于磁盘上)之类的表的空间小得多。虽然您可以使用具有类似散列表结构的 Bloom 过滤器 联合起来，但是一旦您确定元素有可能存在。

因此，一个示例使用模式可能是:

磁盘上有大量的数据——您可以决定需要什么样的错误界限(例如1%) ，它规定了 我的值。然后确定最优 K(根据文中给出的公式)。只需一次从这个磁盘绑定数据填充筛选器。

现在在 RAM 中有了过滤器。当需要处理某些元素时，可以查询过滤器，以确定它是否有可能存在于数据集中。如果没有，就不需要做额外的工作。没有磁盘读取等(如果是散列或树等，就必须这样做)。

否则，如果过滤器说: “是的，它在那里”，有1% 的机会，它是错误的，所以你做必要的工作来找出。99% 的时间，它真的 威尔在那里，所以工作不是没有意义的。

如果 Bloom 过滤器返回一个条目是集合的成员，则存在一定的假阳性概率。如果只使用一个散列函数来表示集合中的成员关系，那么假阳性的概率将高于使用多个散列函数。

Alex 已经解释得很清楚了。对于那些还没有完全掌握它的人，希望这个例子能帮助你理解:

假设我在 Chrome 团队中为 Google 工作，我想在浏览器中添加一个功能，如果用户输入的网址是恶意网址，该功能就会通知用户。因此，我有一个大约100万个恶意 URL 的数据集，这个文件的大小约为25MB。因为它的大小很大(与浏览器本身的大小相比很大) ，所以我将这些数据存储在一个远程服务器上。

案例1: 我使用一个散列函数和一个散列表。我决定使用一个高效的哈希函数，并通过哈希函数运行所有100万个 URL 以获得哈希键。然后我创建一个哈希表(一个数组) ，哈希键将在其中给出放置 URL 的索引。所以现在，一旦我散列并填充了散列表，我就检查它的大小。我将所有100万个 URL 连同它们的键一起存储在散列表中。所以大小至少是25MB。由于其大小，此哈希表将存储在远程服务器上。当一个用户出现并在地址栏中输入一个 URL 时，我需要检查它是否是恶意的。因此，我通过哈希函数运行 URL (浏览器本身可以做到这一点) ，并得到该 URL 的哈希键。现在，我必须使用这个散列键向远程服务器发出请求，以检查散列表中具有这个特定键的特定 URL 是否与用户输入的内容相同。如果是，那么它是恶意的; 如果不是，那么它就不是恶意的。因此，每次用户输入 URL 时，都必须向远程服务器发出请求，以检查它是否是恶意 URL。这将花费大量的时间，因此使我的浏览器速度变慢。

案例2: 我使用了一个鲜花过滤器。整个100万个 URL 的列表使用多个散列函数通过 Bloom 过滤器运行，并且各个位置被标记为1，在一个巨大的0数组中。假设我们想要一个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 过滤器可以识别出这一点，从而避免对远程服务器的调用，从而节省时间。只有在某些情况下，如果 Bloom 过滤器告诉我们 URL 可能是恶意的，只有在这些情况下，我们才会调用服务器。那个“可能”是99% 正确的。

因此，通过在浏览器中使用一个小型 Bloom 过滤器，我们节省了大量的时间，因为我们不需要对每个输入的 URL 进行服务器调用。

我们可以看到，具有单个散列函数的散列表与 Bloom 过滤器的用途完全不同。希望这能消除你的疑虑:)

编辑 :

我已经在 Python 中实现了一个针对恶意 URL 测试任务的 Bloom 过滤器。代码可以在这里找到-< a href = “ https://github.com/tarunsharma1/Bloom-Filter”rel = “ norefrer”> https://github.com/tarunsharma1/bloom-filter 代码非常容易理解，并且在自述文件中提供了详细的描述。

我将从解释什么是开花过滤器开始，它能做什么，不能做什么，为什么我们需要它，展示一个直观的描述如何工作，然后给出一些例子，当他们可以是有用的。

所以 标准方坯过滤器是 概率数据结构概率数据结构，可以^*:

• 向集合中添加元素
• 通过告诉 definitely not in the set或 possibly in the set来检查一个元素是否在集合中

这个 possibly in the set正是它被称为概率的原因。使用聪明的词语，它意味着 假阳性是可能的(在某些情况下，它可能错误地认为元素是正的) ，但是错误的否定是不可能的。

但它是 不行 ^*:

• 从集合中删除一项
• 给你一个列表的所有元素，目前在您的设置

^* < sub > 这套 can/ca 不能用于基本的 Bloom 过滤器。因为它是一个有用的数据结构，是很久以前创建的，人们发现如何 增强它与其他 很有用的功能。

但是等一下: 我们已经知道一个数据结构可以回答所有这些问题，而不需要模糊的“可能”，也不需要所有的限制(不能删除，不能显示所有)。它叫做 准备好了。这里有一个开花过滤器的主要优点: 它是 空间效率和空间常数。

这意味着无论我们在那里存储多少元素，空间都是相同的。是的，一个含有 10^6元素的开花过滤器(无用的开花过滤器)将占用与含有 10^20元素的开花过滤器相同的空间，与含有 0元素的开花过滤器占用相同的空间。那么它需要多大的空间呢？这取决于你的决定(但有一个交易: 更多的元素，你有更多的不确定性，你与你的 possible in the set答案。

另一个很酷的事情是它是空间常数。当您将数据保存到一个集合时，您必须实际保存这些数据。因此，如果存储 this long string in the set，则必须至少使用27个字节的空间。但是，对于1% 的错误和 k ^**的最佳值，每个元素(无论是短 int 还是大量文本)都需要约9.6位(< 2字节)。

另一个属性是，所有的操作都采用常量时间，这与集合的摊销常量时间完全不同(记住，如果集合有冲突，它可能在 O(n)时间恶化)。

^{* *} < sub > k 是 Bloom 过滤器中使用的 hash 函数的值

我不会描述 开花过滤器正常工作(维基百科的文章很好地解释了一切)。在这里，我将简要介绍一些基础知识。

• 启动一个长度为 m的空位数组
• 选择 k不同的散列函数(越独立越好)
• 如果要添加元素，则需要计算此值的所有 k散列，并将相应位设置为1
• 如果要检查元素是否存在，还需要计算所有 k散列，如果至少有一个散列没有设置，那么它肯定不在集合中。否则它可以在集合中。

即使这个描述也足以理解为什么我们不能确定(你可以从其他不同的值中设置所有的位)。这里是 很好地展示了它是如何工作的。

那么什么时候开花过滤器有用呢？简短的答案是 在任何地方假阳性是可以接受的，并且你想检查是否有东西在集合中，但即使它们不是，它也可以成为排除对验证者进行昂贵调用的第一道防线。

下面是一些更具体的描述:

• 恶意网站及浏览器的一个标准例子被描述在几乎所有的 地点中，人们谈论开花过滤器
• 是一个弱密码: 而不是有一个庞大的集所有可能的弱密码，你可以只是检查密码是否肯定不弱的方式更小的开花过滤器
• 如果您有一个文章列表和一个用户列表，您可以使用 Bloom 过滤器来显示用户的文章，他们没有阅读。有趣的是，您只能有一个过滤器(您可以检查 user _ id + article _ id 的组合是否存在)
• 比特币 使用开花滤波器进行钱包同步
• Akamai 的网络服务器使用 Bloom 过滤器来防止“一击即中的奇迹”被存储在其磁盘缓存中。一次性命中的奇迹是用户只请求一次的 Web 对象，Akamai 发现这种情况适用于他们近四分之三的缓存基础设施。使用 Bloom 过滤器检测 Web 对象的第二个请求，并且只在第二个请求时缓存该对象，可以防止一次命中的奇迹进入磁盘缓存，大大减少磁盘工作负载并提高磁盘缓存的命中率(取自 Bloom 在 wiki 上的过滤器文章的例子)

Bloom 过滤器是一种空间有效的概率数据结构，用于测试元素是否是集合的成员。它之所以被称为概率，是因为当一个否定的答案是100% 准确的时候，可能会有错误的肯定意味着如果答案是“是的，这个元素出现在数据集中，它不是100% 准确的。

为什么 Bloom 过滤器是高效的内存:

基本 Bloom 过滤器不存储数据; 它们只回答一个元素是否为集合成员的问题。为了实现一个布鲁姆过滤器，我们需要位数组或者把它想象成一个最初为零的二进制数字。(我认为大小应该是数据大小的2倍)

然后应用 k (k < length thOfBits)不同的散列函数来检查元素是否存在。这个 k是确定当你开始实施开花过滤器，你存储在内存中这个 k。每个散列函数输出0到长度 -1之间的索引。将结果索引元素转换为1。

最后，您要将这个二进制表示转换为10个基数，并且让它为1000003232232。现在这个数字是 bloom filter，你把这个数字存储在内存中。不管它包含的字节大小是多少，您都在消耗该字节大小

Bloom 过滤器用于缓存，但不是所有地方都使用。如果你知道 Bloom 过滤器的一些应用，你会发现它们是多么的有用:

路由器

现代路由器的空间有限，而且由于数据包的大小 他们需要非常快的算法。因此 布鲁姆过滤器的完美接受者 可以处理小比率的错误。除了缓存，路由器经常 使用 Bloom 过滤器来跟踪禁用的 IP 地址，并保持 用于揭示拒绝服务攻击的统计数据。

爬虫

爬虫是自动化的软件代理程序，它扫描网络并进行查找 用于内容、解析和索引他们找到的任何东西 在页面或文档中找到链接，它通常被编程为跟随 并递归地抓取链接的目标。

爬虫程序忽略使用带有属性的标记创建的链接 rel="nofollow".

实际上，建议您以这种方式将任何锚标记为 链接到具有副作用的行为。否则，搜索引擎的 爬行器，即使他们尊重这一政策，将导致不可预测的 行为。

可能发生的情况是，如果您编写了自己的爬虫程序，而您没有编写 小心，它可能会在两页或更多页之间无休止地循环下去 互相连接(或链接)。避免这样 爬虫程序需要跟踪它们已经访问过的页面。

Bloom 过滤器是最好的方法，因为它们可以在其中存储 URL 一个紧凑的方法，并执行检查和保存的网址不变 时间。

IO Fetcher

基于 Bloom 过滤器的缓存有助于减少不必要的 获取/存储昂贵的 IO 资源 与爬行一样: 只有当我们有一个 “ miss”，而“ hit”通常会触发一个更深入的比较(for 例如，在命中时，只从磁盘检索前几行或 文档的第一个块，并对它们进行比较)。

拼写检查器

用于实现 Bloom 过滤器的更简单版本的拼写检查器 然而，今天，拼写检查者大多利用 尝试: 这些数据结构提供了良好的文本搜索性能 没有假阳性。

分布式数据库和文件系统

Cassandra 使用 Bloom 过滤器进行索引扫描，以确定 SSTable 拥有特定行的数据 Bloom 过滤器作为测试 StoreFile 是否为 包含特定的行或行-colcell 整体读取速度，通过过滤掉不必要的磁盘读取 HFile 不包含特定行或行列的块。

参考文献

使用 Bloom 过滤器可以完成的任何事情，都可以在更少的空间内更有效地完成，使用单个散列函数而不是多个散列函数

不是这样的。使用多个散列函数可以降低误报率。具体来说，假设内存中有一个固定的空间，我们愿意以位(我位)和它将包含的固定数量的元素(N)的形式用于 Bloom 过滤器，那么最佳的哈希函数 K的数量是 < a href = “ https://cs.stackexchange.com/q/132088/19315”> K = (我/N) ln 2 。

为什么不像您建议的那样使用单个散列函数呢？看到这一点的最简单方法是考虑包含单个元素的 Bloom 过滤器。如果只使用一个散列函数，那么查找的任何不同元素都有1/我的几率产生假阳性(由于散列值与过滤器中真正包含的元素相同)。但是，如果使用 K > 1散列函数，那么出现假阳性的几率就会小得多(如果 我 > > K，那么假阳性的几率大约是1/MK) ，因为所有 K散列值都需要碰撞。一般来说，只要 N小，我大，K小，增加 K将减少你的假阳性率。

为什么最佳数字不是很大呢？因为如果有太多散列函数，就会将 Bloom 过滤器中的所有(或几乎所有)位设置为1，从而导致100% (或接近100%)的假阳性率。

因此，假正极小化解决方案是使用多个散列函数(但不要太多)。

对1M 元素使用哈希表意味着在每次插入1k 元素后由于 生日悖论而发现冲突。Bloom 过滤器有助于显著减少冲突次数，但也可以给出假阳性结果。