Python中的Bloom Filter

2025年1月5日 | 阅读8分钟

布隆过滤器是一种数据结构，可以高效地检查一个元素是否在一个集合中。它们对于避免假阴性的应用程序非常有用，例如网络爬虫、拼写检查或缓存。然而，布隆过滤器有一个显著的缺点——它们可能产生假阳性，这意味着它们有时会错误地指示一个元素在集合中，而实际上它不在。本文将帮助您使用内置的哈希函数和位数组模块在 Python 中创建一个布隆过滤器。

什么是布隆过滤器？

布隆过滤器是一种数据结构，用于快速识别一个元素是否可能是集合成员。

它从一个位数组开始，所有位最初都设置为零。当您想向集合中添加一个元素时，您会对该元素应用一个或多个哈希函数，这会给您一组索引。数组中每个索引对应的位都会从零翻转到一。

要检查一个元素是否已在集合中，您对该元素应用相同的哈希函数，这会给您一组索引。然后您检查这些索引处的所有位是否都为一。如果它们都为一，则该元素可能在集合中（尽管有很小的假阳性几率）。如果任何位为零，则该元素肯定不在集合中。

总的来说，布隆过滤器是一种存储大量数据并快速检查元素是否属于该集合的有效方式。

布隆过滤器如何工作？

在了解布隆过滤器如何工作之前，了解它在实际场景中可以应用到哪里至关重要。让我们探讨一些示例。

拼写检查器：布隆过滤器是拼写检查器中的一个有用工具，可以快速确定单词的正确拼写。布隆过滤器可以用来验证特定单词是否存在于字典中，而不是筛选庞大的单词字典。
URL 过滤：Web 浏览器和内容过滤器使用布隆过滤器来维护被阻止或恶意网站的列表。浏览器可以快速检查网站的 URL 是否与过滤器中的任何 URL 匹配。
分布式系统：布隆过滤器通常用于分布式数据库和分布式文件系统，以最小化网络请求的数量。通过事先检查布隆过滤器，可以确定请求的数据是否可能在远程节点上可用。

工作方式

布隆过滤器是一种概率数据结构，用于检查一个元素是否属于一个集合。下面是它们的工作原理：

初始化：要创建布隆过滤器，首先选择固定数量的哈希函数 (k) 并创建一个固定大小的位数组（通常是全为零的数组）。位数组的大小和哈希函数的数量由打算存储在过滤器中的元素数量和所需的假阳性率决定。

添加元素：当您想向布隆过滤器中添加一个元素时，您会将其通过每个 k 哈希函数运行。每个哈希函数都会生成一个哈希值，该哈希值决定了位数组中要设置为 1 的位置。这些位置有时被称为“槽”。

示例

让我们取 k（哈希函数数量）= 3

设置位：一旦您确定了槽，您将位数组中这些位置的位设置为 1。

您想添加元素“apple”

哈希函数 1 生成哈希值 1 = 3
哈希函数 2 生成哈希值 2 = 7
哈希函数 3 生成哈希值 3 = 12
将位数组中位置 3、7 和 12 的位设置为 1。

您想添加元素“banana”

哈希函数 1 生成哈希值 1 = 4
哈希函数 2 生成哈希值 2 = 8
哈希函数 3 生成哈希值 3 = 10

将位数组中位置 4、8 和 10 的位设置为 1。

成员测试：要检查一个元素是否在集合中，您将相同的 k 哈希函数应用于该元素。这将生成 k 个哈希值，您将查看位数组中对应的位置。如果所有这些位置的位都设置为 1，则您得出结论该元素“可能”在集合中。但是，如果任何位置为 0，您可以确定该元素不在集合中。

示例

您想检查“apple”是否在集合中

哈希函数 1 生成哈希值 1 = 3
哈希函数 2 生成哈希值 2 = 7
哈希函数 3 生成哈希值 3 = 12
检查位数组中位置 3、7 和 12 的位。它们都为 1，因此您得出结论“apple”可能在集合中。

请记住，这是一种概率检查，虽然可能出现假阳性，但不会出现假阴性。

如何实现布隆过滤器类？

您必须定义一些属性和方法才能在 Python 中实现布隆过滤器类。属性包括 size、bit_array、hash_functions 和 count；方法包括 __init__、add、check 和 false_positive_rate。例如，__init__ 接受 size 和 hash_functions 作为参数，并初始化 bit_array 和 count。add 是一个方法，它接受一个元素作为参数，通过哈希它并翻转 bit_array 中的位来将其添加到集合中。check 是一个方法，它接受一个元素作为参数，如果它可能在集合中则返回 True，否则返回 False。false_positive_rate 是一个方法，它根据公式返回假阳性的估计概率。通过这些属性和方法，您可以在 Python 中创建一个布隆过滤器类，以帮助通知和安抚利益相关者，并为改进您的云安全状况提供有价值的见解。

程序

import math
import mmh3  # You can use the mmh3 library for fast hash functions

class BloomFilter:
    def __init__(self, size, hash_functions):
        # Initialize the Bloom filter with the specified size, number of hash functions, an empty bit array, and a count.
        self.size = size
        self.bit_array = [False] * size
        self.hash_functions = hash_functions
        self.count = 0

    def add(self, element):
        # Add an element to the Bloom filter by hashing it with each hash function and setting the corresponding bits.
        for i in range(self.hash_functions):
            hash_value = mmh3.hash(element, i) % self.size
            self.bit_array[hash_value] = True
        self.count += 1

    def check(self, element):
        # Check if an element may exist in the Bloom filter by hashing it with each hash function and checking bits.
        for i in range(self.hash_functions):
            hash_value = mmh3.hash(element, i) % self.size
            if not self.bit_array[hash_value]:
                return False
        return True

    def false_positive_rate(self):
        # Calculate and return the estimated probability of a false positive using the standard Bloom filter formula.
        return (1 - math.e ** (-self.hash_functions * self.count / self.size)) ** self.hash_functions

# Example usage:
if __name__ == "__main__":
    size = 1000  # Set the size of the Bloom filter
    hash_functions = 5  # Set the number of hash functions

    bloom_filter = BloomFilter(size, hash_functions)

    # Add elements to the Bloom filter
    elements_to_add = ["apple", "banana", "cherry", "date"]
    for element in elements_to_add:
        bloom_filter.add(element)

    # Check for membership
    elements_to_check = ["apple", "banana", "grape", "kiwi"]
    for element in elements_to_check:
        if bloom_filter.check(element):
            print(f"'{element}' may be in the set.")
        else:
            print(f"'{element}' is not in the set.")

    # Calculate and print the estimated false positive rate
    estimated_rate = bloom_filter.false_positive_rate()
    print(f"Estimated False Positive Rate: {estimated_rate:.5f}")

输出

'apple' may be in the set.
'banana' may be in the set.
'grape' is not in the set.
'kiwi' is not in the set.
Estimated False Positive Rate: 0.00000

说明

布隆过滤器在 __init__ 方法中初始化时指定大小、哈希函数数量、一个空位数组和一个用于跟踪已添加元素的计数。
add 方法使用每个哈希函数对元素进行哈希，并将位数组中相应的位设置为 True，同时增加计数。
check 方法对每个元素进行哈希，并比较位数组中相应的位，以确定是返回 True 还是 False。
false_positive_rate 方法使用标准布隆过滤器公式估算假阳性的概率。

在此示例中，我们创建一个具有指定大小和哈希函数数量的布隆过滤器，添加元素，检查成员资格，并估算假阳性率。

优点

内存高效

布隆过滤器是内存高效的，因为它们将数据存储为数组中的位，这在内存有限的情况下很有用。

快速成员测试

布隆过滤器允许进行快速成员测试。检查元素成员资格涉及固定的哈希计算和位数组查找，这些通常很快。

安全

布隆过滤器适用于隐私敏感型应用，因为它们不会泄露存储的元素。

局限性

误报

布隆过滤器可能会产生假阳性，这意味着它们可能会错误地指示元素存在于过滤器中，即使它不存在。随着添加到过滤器中的元素越多，假阳性的可能性就越大。然而，可以通过调整位数组的大小和使用的哈希函数数量来控制假阳性率。尽管如此，布隆过滤器本身就存在少量假阳性的风险。

示例

让我们考虑之前的位数组。

假设您需要检查列表中是否存在西瓜

哈希函数 1 产生哈希值 1 = 7
哈希函数 2 产生哈希值 2 = 10
哈希函数 3 生成哈希值 3 = 12

尽管“西瓜”不在列表中，但布隆过滤器错误地生成了假阳性结果，这意味着布隆过滤器指示其存在。

无法删除元素

布隆过滤器不允许在添加元素后将其删除。这是因为设置位数组中的位是单向操作。如果稍后删除一个元素，它可能会影响其他元素检查成员资格的能力。因此，布隆过滤器主要适用于添加元素但不删除元素的应用。

固定大小

布隆过滤器中位数组的大小在初始化时是固定的。如果预期的元素数量或假阳性率发生变化，您可能需要使用不同的参数创建新的布隆过滤器。

哈希函数依赖性

布隆过滤器的有效性与所用哈希函数的质量密切相关。分布不佳或效率低下的哈希函数会降低过滤器的性能。

结论

总而言之，布隆过滤器是一种数据结构，可以在 Python 中用于快速测试大型数据集中的成员资格，同时使用更少的内存。这种数据结构有其局限性，例如可能出现假阳性以及一旦添加就无法删除元素。在 Python 或任何其他编程语言中使用布隆过滤器时，平衡内存使用和可接受的假阳性率至关重要。

在实际场景中，当布隆过滤器满足特定的应用需求时，它们是一种宝贵的资产。它们在内存效率和速度之间取得了平衡，使其成为使用 Python 编程语言的开发人员的数据结构集合中的一个有价值的补充。

下一主题Python 中的 CDF 图

Python中的Bloom Filter

什么是布隆过滤器？

布隆过滤器如何工作？

工作方式

如何实现布隆过滤器类？

程序

说明

优点