10

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

4

1 に答える 1

9

ハッシュ関数の出力をブルームフィルターのインデックスにマッピングする方法の概要

使用中のk個のハッシュ関数のそれぞれについて、ハッシュがハッシュテーブルのハッシュバケットにマップされるのと同じように、ブルームフィルターのビットにマップされます。したがって、非常に一般的には、32ビット整数を生成するハッシュ関数を言い、モジュラス%演算子を使用してビットインデックスを取得します0 << i < n。ここnで、はブルームフィルターのビット数です。

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

int bit_index = hash_function(input_value) % 1000;

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

編集-コメントのアドレス指定...

MD5関数がデータのバイトにunsigned char*「p」を返すと仮定して、次のMD5_DIGEST_LENGTHことを試してみることをお勧めします。

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コードは、10進数で48、99、99、49です。に読み込まれるintと、CPUのエンディアンに応じて値が異なる可能性がありますが、基本的には、これらの数値の1つに256 ^ 3を加えたものに、別の1つに256 ^ 2を加えたものに、3番目に256に加えて最終的な数値を取得します。 。

これが特に悪い考えだと私が言った理由は次のとおりです。

  • MD5文字列の各文字は、数字（ASCIIコード48〜57）または「a」から「f」までの文字（97〜102）のいずれかです。これらの16の値は、バイトが持つことができるバリエーションの16分の1であり、int生成する値は32ビットを占有しますが、実際には2^16の異なる値しか取得できません。
  • 一部のコンピュータでは、intsを2、4、8などの倍数のメモリアドレスに揃える必要があります。reinterpret_castテキストが互換性のないアドレスで始まる場合、コンピュータがクラッシュする可能性があります。注：IntelとAMDにはそのような調整要件はありませんが、適切に調整されたデータを操作する方が高速な場合があります。

だから、別の提案：

// 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);

ここで、md5表現がデータバッファよりも短い場合は、その最初の部分だけが安全にコピーされるため、BOOST_STATIC_ASSERTは必要ありません。

非暗号化ハッシュ関数を使用する方がはるかに簡単です。通常、数値の読み取り可能なテキストバッファ表現ではなく、数値を返すだけなので、このナンセンスをすべて回避できます。

于 2012-07-27T01:19:29.900 に答える