稳定 Bloom 过滤器

这是一个稳定 Bloom 过滤器的 Rust 实现，用于从数据流中过滤重复项，基于 BoomFilters

这是根据 Deng 和 Rafiei 在《使用稳定 Bloom 过滤器近似检测流数据中的重复项》中描述的稳定 Bloom 过滤器实现的。

稳定 Bloom 过滤器（SBF）会持续删除过时的信息，以便为最近元素腾出空间。与传统 Bloom 过滤器类似，SBF 具有非零的误报概率，该概率受多个参数控制。与经典 Bloom 过滤器不同，SBF 在引入非零误报率的同时，对误报率的增长率有一个紧的上限。经典 Bloom 过滤器的误报率最终会达到 1，之后所有查询都将产生误报。SBF 的稳定点属性意味着误报率渐近地接近一个可配置的固定常量。经典 Bloom 过滤器实际上是 SBF 的一个特殊情况，其中删除率为零且单元格大小为 1，因此这也为它们提供了支持（除了基于位集的 Bloom 过滤器之外）。

稳定 Bloom 过滤器适用于数据集大小事先未知且内存有限的情况。例如，SBF 可以用于从无界的事件流中删除事件，同时指定误报率的上限和最小误报。

使用方法

stable-bloom-filter = "0.3"

use stable-bloom-filter::StableBloomFilter;

let mut f = StableBloomFilter::new_default(10_000, 0.01);
assert!(!f.test(b"a"));

f.add(b"a");
assert!(f.test(b"a"));

assert!(f.test_and_add(b"a"));

assert!(!f.test_and_add(b"b"));
assert!(f.test(b"a"));

assert!(f.test(b"b"));

assert!(!f.test(b"c"));