可伸缩布谷鸟过滤器
scalable-cuckoo-filter的Python项目详细描述
布谷鸟过滤器
布谷鸟滤波器是概率集隶属度的数据结构 具有低误报概率（fpp）的查询。作为改进 在经典的bloom过滤器上，可以将项目添加或移除到 布谷鸟可以随意过滤。布谷鸟过滤器也更能利用空间 很有效率。
布谷鸟过滤器最初描述于： Fan，B.，Andersen，D.G.，Kaminsky，M.，和Mitzenmacher，M.D.（2014年12月）。 布谷鸟过滤器：实际上比开花好。 第十届ACM国际新兴网络会议纪要 实验与技术（第75-88页）。ACM公司。
这个包实现了基本的布谷鸟过滤器以及几个 建立在它之上的派生。
安装
可以从以下位置安装包 PyPI
pip install scalable-cuckoo-filter
经典布谷鸟过滤器
importmathfromrandomimportrandrangefromcuckoo.filterimportCuckooFiltercapacity=1000000error_rate=0.000001# Create a classic Cuckoo filter with a fixed capacity of 1000000# bucketscuckoo=CuckooFilter(capacity=capacity,error_rate=error_rate)bucket_size=6# Setting the bucket size is optional, the bigger the bucket,# the more number of items a filter can hold, and the longer# the fingerprint needs to be to stay at the same error ratecuckoo=CuckooFilter(capacity=capacity,error_rate=error_rate,bucket_size=bucket_size)# The fingerprint length is computed using the following formula:fingerprint_size=int(math.ceil(math.log(1.0/error_rate,2)+math.log(2*bucket_size,2)))for_inrange(1,100000):item=str(randrange(1,1000000000))cuckoo.insert(item)ifcuckoo.contains(item):print'{} has been added'.format(item)cuckoo.delete(item)ifnotcuckoo.contains(item):print'{} has been removed'.format(item)
比特阵列布谷鸟滤波器
一个经典的布谷鸟过滤器是用一个python的bucket列表实现的 物体。每个桶，同样，存储一个固定的指纹列表。这个 实现简单明了，但不必要的浪费 对于需要保留数亿个项目的应用程序。
针对这种情况，我们设计了位阵列杜鹃滤波器。这个 整个过滤器被压缩成一个位数组，以最小化内存使用。 例如，容量为100.000.000的位阵列杜鹃滤波器， bucket size为4，错误率为0.000001将需要：
- 23位指纹，使用上述公式计算。
- 9.200.000.000位=1.08 GB=容量*存储桶大小*指纹。
理论上它可以满负荷储存多达40万件物品。
importmathfromrandomimportrandrangefromcuckoo.filterimportBCuckooFiltercapacity=1000000error_rate=0.000001# Create a bit array Cuckoo filter with a fixed capacity of 1000000# bucketscuckoo=BCuckooFilter(capacity=capacity,error_rate=error_rate)bucket_size=6# Setting the bucket size is optional, the bigger the bucket,# the more number of items a filter can hold, and the longer# the fingerprint needs to be to stay at the same error ratecuckoo=BCuckooFilter(capacity=capacity,error_rate=error_rate,bucket_size=bucket_size)# The fingerprint length is computed using the following formula:fingerprint_size=int(math.ceil(math.log(1.0/error_rate,2)+math.log(2*bucket_size,2)))for_inrange(1,100000):item=str(randrange(1,1000000000))cuckoo.insert(item)ifcuckoo.contains(item):print'{} has been added'.format(item)cuckoo.delete(item)ifnotcuckoo.contains(item):print'{} has been removed'.format(item)
可伸缩布谷鸟过滤器
在实际应用中，布谷鸟滤波器存在固定容量的问题。 分配太多的容量，在分配的同时也会浪费 很小，它会降低滤波器的性能并导致fp。因此， 为了解决这个问题，引入了可伸缩布谷鸟滤波器。 容量问题。
受可伸缩布卢姆过滤器的启发，可伸缩布谷鸟过滤器利用 多个过滤器可动态缩放容量。当存在时 过滤器接近其容量，一个新的，双尺寸，将 创建。一个可伸缩的布谷鸟过滤器将处理所有常见的操作 无缝透明。
在内部，可伸缩布谷鸟过滤器使用位阵列布谷鸟过滤器 效率虽然很容易改变。
importmathfromrandomimportrandrangefromcuckoo.filterimportScalableCuckooFilterinitial_capacity=1000000error_rate=0.000001# Create a scalable Cuckoo filter with an initial capacity of 1000000# bucketscuckoo=ScalableCuckooFilter(initial_capacity=initial_capacity,error_rate=error_rate)bucket_size=6# Setting the bucket size is optional, the bigger the bucket,# the more number of items a filter can hold, and the longer# the fingerprint needs to be to stay at the same error ratecuckoo=ScalableCuckooFilter(initial_capacity=initial_capacity,error_rate=error_rate,bucket_size=bucket_size)# The fingerprint length is computed using the following formula:fingerprint_size=int(math.ceil(math.log(1.0/error_rate,2)+math.log(2*bucket_size,2)))for_inrange(1,100000):item=str(randrange(1,1000000000))cuckoo.insert(item)ifcuckoo.contains(item):print'{} has been added'.format(item)cuckoo.delete(item)ifnotcuckoo.contains(item):print'{} has been removed'.format(item)
欢迎加入QQ群-->： 979659372
