golomb-set

Rust中的高洛姆编码集合实现

高洛姆编码集合是一种概率性数据结构，通常比布隆过滤器小，但查询性能较低。随机分布样本之间差异的有序列表将大致具有几何分布，这使它成为Golomb-Rice编码的最佳前缀。由于一个好的哈希算法将是随机分布的，这种编码使得哈希值的存储效率更高。

感谢Giovanni Bajo的博客文章以及他们的Python和C++实现，这对编写和测试这个库非常有帮助，可以在以下链接找到：这里 和 这里。

用法和行为

创建高洛姆编码集合时，有三个主要参数需要选择：哈希算法、N 和 P。 N 是希望插入集合中的元素的最大数目，而 1 / 2 ^ P 是当集合满时希望出现的误报概率。如果插入的项较少，实际概率将显著降低。

选择的哈希算法必须具有均匀分布（这不同于加密安全），并且哈希输出的位数必须大于 log2(N * 2 ^ P) 位。目前库中没有强制执行此要求，未能做到可能会导致比预期更多的误报。在满足这些要求的基础上，选择一个速度较快的算法是合适的。如果硬件加速可用，CRC32对于最多一百万个元素和0.001%的误报概率是一个不错的选择。对于更大的集合或更低的概率，需要一个输出更长的哈希算法。

示例

use {golomb_set::UnpackedGcs, md5::Md5};

// Create a GCS where when 3 items are stored in the set, the
// probability of a false positive will be `1/(2^5)`, or 3.1%
let mut gcs = UnpackedGcs::<Md5>::new(3, 5);

// Insert the MD5 hashes of "alpha" and "bravo"
gcs.insert(b"alpha");
gcs.insert(b"bravo");

assert!(gcs.contains(b"alpha"));
assert!(gcs.contains(b"bravo"));
assert!(!gcs.contains(b"charlie"));

// Reduces memory footprint in exchange for slower querying
let gcs = gcs.pack();

assert!(gcs.contains(b"alpha"));
assert!(gcs.contains(b"bravo"));
assert!(!gcs.contains(b"charlie"));