3

セグメント化されたブルーム フィルター用のビット テーブルがあります。ここでは、すべての列が単一のハッシュ関数によって管理されています。

unsigned char bit_table_[ROWS][COLUMNS];//bit_table now have 8*ROWS*COLUMNS bits
unsigned char bit_mask[bits_per_char] = { 0x01,0x02,0x04,0x08,
                                          0x10,0x20,0x40,0x80};

それぞれがCOLUMNS*8ビットの設定とチェックを処理する、 ROWS個のハッシュ関数があります。

要素はハッシュされ、bit_indexとbitは次のように計算されます。

compute_indices(unsigned int hash)
{
   bit_index=hash%COLUMNS;
   bit=bit_index%8;
}

現在、挿入は次のように行われます

for (std::size_t i = 0; i < ROWS; ++i)
      {
        hash=compute_hash(i,set_element);
        compute_indices(hash);
        bit_table_[i][bit_index ] |= bit_mask[bit]; 
      }

そしてクエリは

for (std::size_t i = 0; i < ROWS; ++i)
      {
     hash=compute_hash(i,set_element);
      compute_indices(hash);

      if (((bit_table_[i][bit_index])& bit_mask[bit]) != bit_mask[bit])
         {
            return false;
         }      
  }

私の問題は、ブルーム フィルターがすぐにいっぱいになってしまうことです。文字の個々のビットを正しく使用していないと思われます。たとえば、次のようなものが必要だと思います。

bit_table_[i][bit_index][bit]|=bit_mask[bit];

挿入用ですが、bit_tableは 2 次元配列として宣言されているため、これを行うことはできません。

char 配列の個々のビットを利用するにはどうすればよいですか?

英語は私の第二言語なので、私の質問を理解するのに苦労するかもしれません. リクエストがあれば、私のポイントをさらに説明していただければ幸いです。

編集: compute_hash(i,set_elemnt)は、定義済みのソルト値を使用して、挿入またはクエリされる要素のハッシュ値を計算します。

4

1 に答える 1

1

Compute_indicesメソッドにエラーがあります。

列インデックスを計算してから、この列インデックスにモジュロ8を適用します。最後に、列内で常に同じビットを使用します。たとえば、列10の場合、常にビット2を使用します。

あなたが持っている必要があります：

compute_indices(unsigned int hash)
{
    int bitIndex = hash % (COLUMNS * 8);
    bit_index= bitIndex / 8;
    bit = bitIndex % 8;
}
于 2012-05-05T15:34:31.613 に答える