Bloomier filterとは? わかりやすく解説

Bloomier filter

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/07/15 00:00 UTC 版)

ブルームフィルタ」の記事における「Bloomier filter」の解説

2004年Bernard Chazelle、Joe Killian、Ronitt Rubinfeld、Ayellet Talブルームフィルタ追加した要素関連させた値を持つ連想配列設計したブルームフィルタと同様、このデータ構造空間効率良く偽陽性発生可能性がある。Bloomier filter での偽陽性は、キー値がマッピングされていないのに値が返される場合である。ただしマッピングされているキーに対して不正な値を返すことはない。 単純な Bloomier filter でその動作説明しよう。まず取り得る値が 0 と 1 だけの連想配列考える。2つブルームフィルタ A0B0作成する。そうして値が 0 であるキーA0登録し、値が 0 であるキーB0登録する。あるキー対応する値を求めときには両方フィルタ参照する。もしどちらにもそのキーない場合には、そのキーとそれに対応する値はない。キーA0 にあって B0ない場合には、そのキー対応する値は 1 ではなくて、高い確率で 0 であると言える逆にキーB0 にあって A0 になければ、キー対応する値は 0 ではなくて、高い確率で 1 であると言えるブルームフィルタ偽陽性発生していて両方フィルタキー存在する判定され場合には問題発生する連想配列であるから、同じキー両方ブルームフィルタには追加していない。しかし、どちらのフィルタが嘘をついているのかを、このままでは判別できないこのため別の小さな2つフィルタ A1 と B1用意する。そうして 値が 0 でB0 では偽陽性となるキーを A1 に、また値が 1 でA0 では偽陽性となるキーB1登録しておく。そうして A0 にも B0 にも存在するとされたキーについては、そのキーを A1 と B1検証する。 しかしこの段階でもまだ偽陽性発生する可能性はある。これに対しても同じ解決策再帰的適用するフィルタペア上位ペア片方マップされていてもう片方偽陽性となるものだけを登録するので、登録すべきキーの数は劇的に減っていき、ある段階になると確率的ではないデータ構造収めることのできる数になる。また、このフィルタ階層構造下っていかなければならない場合の数非常に少ないため、全体として検索時間線形時間になる。また、全体必要な空間のほとんどは最初のフィルタペアのものであり、n には無関係である。 以上でデータ構造検索アルゴリズム与えられた。新たなキーと値のペア格納する方法次の通りである。このとき、プログラムは同じキー両方の値を設定するような動作絶対にてはならない。いま値が 0 の場合には、キーA0追加し、そのキーB0持っていると(嘘を)答えかどうか調べる。もしも B0 が(持っているという)偽陽性結果返すならば、そのキー次のレベルの A1 にも追加して、以下同様の処理をする。最終レベルにまで到達したら、そのキー単純に挿入する。あるいは値が 1 の場合であれば、この操作を A と B を入れ替えておこなえばよい。 さて、これでキーに対して値 0 または値 1 を正しくマッピングすることができるようになったが、任意の値を格納するにはどうすればよいであろうか? それは簡単である。値の各ビット返すような Bloomier filter をビット幅個数だけ作成すればよい。値のビット幅大き場合には、値そのものではなくて何らかのハッシュ値を Bloomier filter が返すようにする。n ビットの値を扱う Bloomier filter が必要とする空間量はブルームフィルタ 2n 個分よりも若干大きいだけである。

※この「Bloomier filter」の解説は、「ブルームフィルタ」の解説の一部です。
「Bloomier filter」を含む「ブルームフィルタ」の記事については、「ブルームフィルタ」の概要を参照ください。

ウィキペディア小見出し辞書の「Bloomier filter」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「Bloomier filter」の関連用語

Bloomier filterのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



Bloomier filterのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaのブルームフィルタ (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS