ハッシュ関数出力をbloomfilterインデックスにマップする方法は？

Question

ハッシュ関数の出力がブルームフィルタのインデックスにどのようにマッピングされているかについての概要を提供することで、誰でも助けてくれますか？ bloomfiltersの概要は次のとおりです。

Answer 1

ハッシュ関数の出力は、ブルームフィルタ指標使用中Kハッシュ関数の各々について

にマッピングされる方法の概要、それらは、ブルームフィルタ同じようにビットにマッピングハッシュはハッシュテーブルのハッシュバケットにマップされます。したがって、非常に一般的には、32ビットの整数を生成するハッシュ関数を指定してから、係数%を使用してビットインデックス0 << i < nを取得します。ここで、nはブルームフィルタのビット数です。それはここ2ということに注意することが重要です

int bit_index = hash_function(input_value) % 1000; 

：、これは非常に具体的な作るのは、ハッシュ関数は、0から2^32-1までの数字を生成しましょう、とあなたのブルームフィルタで1000ビットがあるために

^32-1は1000よりもはるかに大きいです。代わりに、ハッシュ関数がかなり均等に分散された数を生成したとしますが、0から1023までしか含まない場合、モジュラス演算の後、bit_indexは0..23 （たとえば、入力2と1002の両方がポストモジュラス値2になりますが、入力25のみが25の出力を生成するため、24 ..999と比較して）そのため、32ビットを生成するハッシュ関数がある場合は、2の累乗のビット数に合わせたサイズのブルームフィルタを使用し、ハッシュ値のセクションをスライスして、独立したハッシュ関数のように使用できます - あなたがリンクしているウィキペディアの記事にすべて説明されています。しかし、ハッシュ関数の「クラスタリング」の欠陥はそのまま出力に渡されるため、良質のハッシュ関数が必要です。そのような貧弱なハッシュを軽減する1つの方法です。それでも、良いハッシュ関数では、2のべき乗は、ビット単位のAND演算と必要に応じてビットシフトを使用してビットインデックスを抽出することを容易にします。これは整数モジュラスよりも高速ですが、ハッシュ関数はおそらく全体のパフォーマンスプロファイル

編集 - コメントに対処...

あなたのMD5関数のは、データのMD5_DIGEST_LENGTHバイトにunsigned char* "P" を返すと仮定すると、私はあなたがしようと提案：

実際 特に悪かった

BOOST_STATIC_ASSERT(MD5_DIGEST_LENGTH >= sizeof(int)); 
int bit_index = *reinterpret_cast<unsigned int*>(p) % num_of_bloom_filter_bits; 

アイデア - 申し訳ありません - なぜ私は2つの理由を今すぐ説明します。まず、あなたの質問に答えてください：BOOST_STATIC_ASSERT()は、渡された式がfalseと評価された場合にコンパイルエラーを出すように設計されています。ここでは、基本的には、MD5_DIGEST_LENGTH（MD5ハッシュのテキスト表現の文字サイズである）が少なくともint整数型のシステムで使用されるバイト数と同じであるという要件を文書化する方法です。 （そのサイズはおそらく4バイトですが、8かもしれません）。この要求は、次の行のreinterpret_castが安全であることを保証することを意図しています。 MD5ハッシュのテキスト表現の先頭にあるバイトから値が読み取られ、そのバイトにintが含まれているかのように読み込まれます。 intサイズはです4、MD5ハッシュはコメントのように "0cc175b9c0f1b6a831c399e269772661"です。最初の4バイトには "0cc1"が含まれています。そのテキストのASCIIコードは48,99,99,49小数です。intに読み込まれると、CPUのエンディアンに応じて値が異なる可能性がありますが、基本的には、256^3倍と256倍の2倍と256倍の3倍数。私は、これは特に悪いアイデアであると言いました

な理由は以下のとおりです。

• MD5文字列の各文字は、数字（ASCIIコード48〜57）または「」から「F」からの手紙のいずれかであります（97-102）。これらの16の値は、バイトが持つことができるバリエーションの16番目であり、生成するintの値は32ビットを占めますが、実際には2^16の別個の値しか得られません。
• 一部のコンピュータでは、intは、2,4,8などの倍数のメモリアドレスにアライメントする必要があります。reinterpret_cast - 互換性のないアドレスからテキストが開始されると、コンピュータがクラッシュする可能性があります。注：インテル& AMDは、このようなアライメント要件はありませんが、正しくアライメントされたデータを処理する方が速い場合があります。

ので、別の提案：MD5表現は、データバッファよりも短かった場合はここで

// create a buffer of the right size to hold a valid unsigned long in hex representation... 
char data[sizeof(unsigned long) * 2 + 1]; 

// copy as much of the md5 text as will fit into the buffer, NUL terminating it... 
sprintf(data, "%.*s", sizeof data - 1, md5); 

// convert to an unsigned long... 
m = strtoul(data, /*endptr*/ NULL, /*base*/ 16); 

、それだけの最初の部分を安全にコピーされるので、BOOST_STATIC_ASSERTは必要ありません。

暗号化されていないハッシュ関数を使用するほうがずっと簡単です。一般に、数値の読みやすいテキストバッファ表現ではなく、数値を返すだけなので、このナンセンスを避けることができます。