CでのBloomフィルタの効率的な実装？

この質問は以前に尋ねられましたが、その時点で回答がありませんでしたので、もう一度質問しました。CでのBloomフィルタの効率的な実装？

C言語ではBloomフィルタを効率的に実装する必要があります（C++ではありません）。そのようなものが利用できない場合、私は時間を過度に取らないようにいくつかの良い参照が与えられれば、実装するのは気にしません。

インサートとテストにこのデータ構造を比率（1：20k）で使用したいので、主にテスト集約的です。テストされるデータは64ビットの整数です。

確率論的です。正確な答えが必要な場合は、Union Find Disjoint Setを使用してください。トップコーダーでこれを検索すると、そのためのチュートリアルがあるはずです。 – nhahtdh

C言語を書いているなら、これは一般的なライブラリが必要なものではありません。 100行未満のコードでなければならず、サードパーティのライブラリを統合するよりも書き込む時間が短くなければなりません。 Wikipediaなどでアルゴリズムの好きな説明を読んでください。 –

@ R書くのは時間がかかりますが、効率的に書くと効率的に書くことが問題になります。私はデータのメンバシップを10^7のオーダーでテストし、等価結合の結果をcount（*）クエリより高速にする必要があります。私は私の実装でもmsを失う余裕がない –

クロムはあまりにも自己宣伝をしないC++での1

2012-06-13 02:40:15 eqzx

男、彼らは実際に彼の（パブリックドメイン）ハッシュ関数の使用のためにボブ・ジェンキンスの著作権を含める必要があります... – tbert

がありますが、私はそれがブルームフィルタを使用して、重複したテキスト行をフィルタリングGeany editor/IDE用のプラグインを書いています。

実装はC言語であり、right here on GitHubとなります。それはGPL v3なので、あなたの正確なニーズに応じて、あなたはそれを使うことができるかもしれません。

私の実装に関するいくつかの注意事項：

文字列をフィルタリングするように設計されており、キータイプ抽象的ではないんです。つまり、ニーズに合わせてキー処理を変更する必要があります。
これは、非特有のセマンティクスをサポートしています。もしあなたが望むのであれば、実際にはそれを完全に非確率的存在テストに使用することができます。bloom_filter_new()によって使用されるコールバック関数ポインタBloomContainsを参照してください。 NULLを渡すだけで "純粋な"フィルタが得られます。
文字列ハッシュ関数は、Austin ApplebyのMurmurHash2です。より現行のMurmurHash3を評価しましたが、バージョン2は使いやすくなっています。
Geanyエコシステムに適合させるため、このコードでは全体を通してGLibタイプを使用しています。

パフォーマンスはあまり調整されていませんが、大丈夫です。もちろん、テストした後のフィードバックもありがとう！ https://github.com/jvirkki/libbloom

2012-06-13 06:59:12 unwind

ねえ、おかげでそれは本当に非常に役立つことができます。私はそれを試して、それについて教えてくれるでしょう。 –

glib –

以外の高性能ライブラリでは、コードを移植可能にする以外はglibライブラリを使用する特定の動機を示唆できますか？ –

は、私が使用のものとすることができるここでは、スタンドアローンのプレーンCライブラリを持っています。

'ブルームフィルタ' のgithubの上の簡単な検索は（C用）の結果のトンを得られます。

これだけREFERENCEためです。

2013-02-13 08:50:33

利点はありますか？ – bsiamionau

+11

+1 BSDライセンス。 –

私はこれが古い質問ですけど、参考のために、ここにいくつかのgithubの検索結果は次のとおりです。

2013-06-02 05:46:44

答えて