WOLFRAM

Wolfram言語 ＆ システムドキュメントセンター

"BloomFilter" (データ構造)

"BloomFilter"

要素が確実にメンバでないかどうかを検証する集合を表す．

詳細

  • Bloomフィルタは通常，要素が確実にメンバでないかどうかを検証することができる確率集合として使われる．
  • ある要素が集合のメンバではない場合には，その要素がBloomフィルタのメンバかどうかを検証すると，必ずFalseが返される．
  • ある要素が集合のメンバである場合には，その要素がBloomフィルタのメンバかどうかを検証しても，必ずTrueが返されるとは限らない．
  • CreateDataStructure[ "BloomFilter",capacity]指定の capacity の新しい"BloomFilter"を作成する
    CreateDataStructure["BloomFilter", capacity,p]指定の誤検出の確率 p で新しい"BloomFilter"を作成する
    Typed[x,"BloomFilter"]x に"BloomFilter"型を与える
  • "BloomFilter"型のデータ構造には，以下の演算が使える．
  • ds["Capacity"]ds の記憶容量time: O(1)
    ds["Copy"]ds のコピーを返すtime: O(n)
    ds["CouldContain",x]ds に x が含まれる可能性がある場合にはTrue，それ以外の場合にはFalseを返すtime: O(1)
    ds["Insert",x]x を ds に挿入するtime: O(1)
    ds["LoadFactor"]ds のロード係数time: O(1)
    ds["FalsePositiveProbability"]ds の誤検出の確率を返すtime: O(1)
    ds["Visualization"]ds の可視化を返すtime: O(n)
  • 以下の関数もサポートする．
  • dsi===dsjdsi が dsj に等しい場合はTrue
    FullForm[ds]ds の完全形
    Information[ds]ds についての情報
    InputForm[ds]ds の入力形
    Normal[ds]ds を通常の式に変換する

例題

すべて開く すべて閉じる

例  (1)

新しい"BloomFilter"は，CreateDataStructureを使って作成できる：

Wolfram Language code: ds = CreateDataStructure["BloomFilter", 2]

任意の式を"BloomFilter"のデータ構造に挿入することができる：

Wolfram Language code: ds["Insert", f[1]]

式がないかどうかを検証することは可能である．結果がFalseである場合には，f[2]が確実にその集合内にないことを意味する：

Wolfram Language code: ds["CouldContain", f[2]]

結果がTrueである場合には，f[1]がその集合内に存在する可能性があることを意味する：

Wolfram Language code: ds["CouldContain", f[1]]

式バージョンの ds を返す：

Wolfram Language code: Normal[ds]

データ構造の可視化を生成することができる：

Wolfram Language code: ds["Visualization"]

スコープ  (2)

情報  (1)

新しい"BloomFilter"は，CreateDataStructureを使って作成することができる：

Wolfram Language code: ds = CreateDataStructure["BloomFilter", 2]

データ構造 ds についての情報：

Wolfram Language code: Information[ds]

誤検出の確率  (1)

誤検出の確率が高い"BloomFilter"を作成する：

Wolfram Language code: dsH = CreateDataStructure["BloomFilter", 2, 0.7]

デフォルトの誤検出の確率で"BloomFilter"を作成する：

Wolfram Language code: dsL = CreateDataStructure["BloomFilter", 2]

要素を挿入する：

Wolfram Language code: dsH["Insert", f[1]]
Wolfram Language code: dsL["Insert", f[1]]

誤検出の確率が高いデータ構造は，より多くの誤検出を返す：

Wolfram Language code: Count[Map[dsH["CouldContain", #]&, Range[100]], True]
Wolfram Language code: Count[Map[dsL["CouldContain", #]&, Range[100]], True]

考えられる問題  (1)

満杯であるBloomフィルタは，含まれているかどうかを検定した場合に誤検出を返す可能性が高くなる．

Bloomフィルタを作成し，多くの要素を挿入する．可視化はかなり満杯であることを示す：

Wolfram Language code: ds = CreateDataStructure["BloomFilter", 1];Do[ ds["Insert", RandomReal[]], {1000}]; ds["Visualization"]

ロード係数は，フィルタが満杯であることを示す：

Wolfram Language code: ds["LoadFactor"]

含まれているかどうかを検定すると，要素が挿入されなかったにも関わらず，Trueが返される：

Wolfram Language code: ds["CouldContain", "element"]