什么是d-Left计数布隆过滤器？

Question

有人能用一种简单的方式解释一下d-left计数布隆过滤器，特别是指纹和残数的使用吗？

有没有一个好的Python实现呢？

Answer 1

直观地说，左左计数布隆过滤器(或简称dlcBF )是Bloom filters的变体，旨在支持插入和删除。

常规布隆过滤器允许您在创建过滤器后添加新项目。要做到这一点，只需使用每个哈希函数对新项目x进行哈希运算，转到有问题的位，并将它们设置为1。然而，Bloom filters在添加项目后并不自然地支持删除。具体地说，您不能只是将一个项散列到的每个位都翻转为0，因为其他项可能散列到相同的位置。

dlcBF是一种(相对)节省空间的方法，可以提供与布隆过滤器相同的功能，但具有支持删除和添加的能力。dlcBF使用的空间大约是传统布隆过滤器的1.5-2倍。

自从2006年dlcBF被发明以来，模仿布隆过滤器的动态插入和删除的新数据结构也被发明出来。2014年首次介绍的cuckoo filter支持相同的操作集，但假设错误率相当低，内存开销要低得多。如果你只对可以插入和删除的Bloom filter替代品感兴趣，我建议你选择一个布谷鸟过滤器，它有很多好的实现可用。

至于dlcBF是如何工作的，它的操作有两个基本原则。第一个想法是桶和槽。dlcBF通过维护一个包含b个存储桶的数组来工作。这些桶被分成d组，每组(大致) b/d桶。每个桶又被细分为s个槽，其中每个槽由两位计数器和用于存储少量位的空间组成。

存储在每个存储桶内的槽中的值是使用一种称为fingerprinting.的技术导出的存储在指纹中的每一项都被散列为一个数字，我们称之为 dlcBF 。密钥源又被用来导出D个桶的位置和每个桶的称为余数的小比特序列。要查看某个项目是否存在于dlcBF中，可以计算其关键来源，然后派生d对存储桶和剩余物。接下来，检查每个指定的存储桶，看看特定的剩余部分是否存储在存储桶中的一个槽中。如果不存在，则该项目不存在。如果是这样，项目要么存在，要么我们有误报(就像在常规的布隆过滤器中一样)。

当添加一个项目时，d-left计数位出现。要添加一个项目，请计算其键源，然后获得d个存储桶/剩余部分的组合。找到这些存储桶中剩余项最少的那个，打破与左侧的关系(例如，较低的存储桶索引)，然后如果剩余项不在该存储桶的任何插槽中，则添加该剩余项，或者如果存在剩余项，则递增相关的计数器。要删除一项，只需像往常一样搜索它，如果找到与您的项匹配的存储桶/剩余项序列，则递减其计数器。

对dlcBF的分析归结为：(1)这种将物品放在物品较少的桶中的策略，抢七向左，倾向于将物品几乎均匀地分布，然后(2)计算出你需要多少桶，你的指纹应该有多长，以及每件物品需要多少位。直观地说，增大指纹可以降低表中存储的项与未存储在表中的项之间发生哈希冲突的可能性，但会增加所需的空间量。减小指纹大小会减少表的大小，但也会增加误报率。