c - 在 C 中有效实现布隆过滤器？

Question

这个问题之前有人问过，但当时没有答案，所以我决定再问一次。

我需要在 C（不是 C++）中有效地实现布隆过滤器。如果没有这样的东西可用，我不介意实施一个，如果有一些好的参考，这样就不会花费我太多的时间。

我想按比例（1:20k）使用这个数据结构进行插入和测试，所以它主要是测试密集型的。要测试的数据是 64 位整数。

score 16 · Accepted Answer

16

我在这里有一个独立的纯 C 库，可能有用： https ://github.com/jvirkki/libbloom

于 2013-02-13T08:50:33.613 回答

score 4 · Accepted Answer

不要做太多的自我推销，但我已经为Geany 编辑器/IDE编写了一个插件，它可以过滤掉重复的文本行，它使用了一个 Bloom 过滤器。

该实现是用 C 语言实现的，您可以在 GitHub 上找到它。它是 GPL v3，因此根据您的确切需求，您可能会也可能不会使用它。

关于我的实现的一些注意事项：

它旨在过滤字符串，并且不抽象键类型。这意味着您将不得不修改密钥处理以满足您的需要。
它支持非特征语义，如果您愿意，您实际上可以将其用于完全非概率的存在测试（请参阅使用的BloomContains回调函数指针bloom_filter_new()）。只需通过NULL即可获得“纯”过滤器。
字符串散列函数是Austin Appleby 的MurmurHash2。我评估了最新的 MurmurHash3，但版本 2 更易于使用。
为了适应 Geany 生态系统，此代码始终使用GLib类型。

它没有针对性能进行大量调整，但应该没问题。当然，如果您在测试后得到任何反馈，我将不胜感激！

score 2 · Accepted Answer

2

Chromium 在 C++ 中有一个

于 2012-06-13T02:40:15.333 回答

score 0 · Accepted Answer

我知道这是一个老问题，但作为参考，这里有一些 github 搜索结果。

在 github 上简单搜索“bloomfilter”会产生大量结果（对于 C）：

这仅供参考。

score 0 · Accepted Answer

此项目中提供了几种布隆过滤器实现和替代算法：https ://github.com/FastFilter/fastfilter_cpp

涵盖了常规布隆过滤器、阻塞布隆过滤器、布谷鸟过滤器、哥伦布编码集等。它是 C++，但主要算法很容易移植到 C。

5 回答 5