ブルームフィルタ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/15 00:00 UTC 版)
ブルームフィルタ（英語: Bloom filter）は、1970年に Burton H. Bloom が考案した空間効率の良い確率的データ構造であり、あるデータが集合の要素である（集合に含まれている）かどうかの判定に使われる。ただし判定は正確ではなくて、含まれていないのに含まれていると誤って判定すること偽陽性（false positive）の可能性がある。しかし含まれているものを含まれていないと誤判定すること偽陰性（false negative）はない。なお集合に要素を追加することはできるが、集合から要素を削除することはできない（ただし、拡張をした counting filter であれば削除もできる）。集合に要素を追加していくにつれて偽陽性の可能性は増す。
[続きの解説]
「ブルームフィルタ」の続きの解説一覧
- 1 ブルームフィルタとは
- 2 ブルームフィルタの概要
- 3 偽陽性確率
- 4 特性
- 5 外部リンク
ブルームフィルタ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/02 09:30 UTC 版)
ハッシュ関数はブルームフィルタの基本的構成要素である。ブルームフィルタはキーが集合に含まれるかどうかを近似的に表すコンパクトなデータ構造である。
※この「ブルームフィルタ」の解説は、「ハッシュ関数」の解説の一部です。
「ブルームフィルタ」を含む「ハッシュ関数」の記事については、「ハッシュ関数」の概要を参照ください。
ウィキペディア小見出し辞書の「ブルームフィルタ」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- ブルームフィルタのページへのリンク
