|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ブル ： [ぶる] 【名詞】 1. bull 2. (n) bull ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana) ・ フィル ： [ふぃる] 【名詞】 1. fill 2. (n) fill ・ フィルタ ： [ふぃるた] (n) filter, (n) filter
ブルームフィルタ（Bloom Filter）は、1970年に Burton H. Bloom が考案した空間効率の良い確率的データ構造であり、要素が集合のメンバーであるかどうかのテストに使われる。偽陽性（False Positive）による誤検出の可能性があるが、偽陰性（False Negative）はない。要素を集合に追加することができるが、削除することはできない（Counting filter を使えば削除できる）。集合に要素が追加されればされるほど、偽陽性の可能性が高くなる。 == 使用例 == 例えば、ブルームフィルタを使って空間効率の良いスペルチェックを行うことができる。正しい単語を集めた辞書のブルームフィルタは、辞書に登録されている全単語を受容し、登録されていない単語はほとんど受容しない。若干不正確ではあるが、それで十分な場合もある。偽陽性の発生率を考慮すれば、単語当たり 1バイト程度でデータ構造が構築できる。 このスペルチェッカーの面白い特性として、そのデータ構造から正しい単語のリストを取り出すことができないのである。せいぜい頑張っても、正しい単語のリストとさらにおびただしい偽陽性の単語のリストが得られてしまう（混じっていて、どれが正しいかわからない）。これを機能と捉えれば、例えばディスク内に残っている重要な番号（クレジットカード番号など）を探し出すとか、大量の電子メールから特定の（他人に知られたくない）アドレスを含むものを探し出すといった用途が考えられる。これは完全に安全な方法ではないが、偽陽性は別の手段で取り除くことができるだろう。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ブルームフィルタ」の詳細全文を読む スポンサード リンク
|