"BloomFilter" （数据结构）

"BloomFilter"

表示测试元素是否绝对不是成员的集合.

更多信息

  • Bloom 过滤器通常被用作概率集合 (probabilistic set)，可以测试元素是否绝对不是成员.
  • 如果一个元素不是集合的成员，则 Bloom 过滤器对其进行测试将始终返回 False.
  • 如果一个元素是集合的成员，则 Bloom 过滤器对其进行测试将始终返回 True：
  • CreateDataStructure[ "BloomFilter",capacity]创建新的指定 capacity 的 "BloomFilter"
    CreateDataStructure["BloomFilter", capacity,p]创建新的误报概率为 p 的 "BloomFilter"
    Typed[x,"BloomFilter"]指定 x 的类型为 "BloomFilter"
  • 对于类型为 "BloomFilter" 的数据结构，可进行以下操作：
  • ds["Capacity"]ds 的存储容量用时：O(1)
    ds["Copy"]返回 ds 的副本用时：O(n)
    ds["CouldContain",x]如果 ds 可能含有 x 则返回 True，否则返回 False用时：O(1)
    ds["Insert",x]把 x 插入 ds用时：O(1)
    ds["LoadFactor"]ds 的装载因子用时：O(1)
    ds["FalsePositiveProbability"]返回 ds 的误报概率用时：O(1)
    ds["Visualization"]返回 ds 的可视化用时：O(n)
  • 还支持以下函数：
  • dsi===dsj如果 dsi 等于 dsj 则为 True
    FullForm[ds]ds 的完全形式
    Information[ds]关于 ds 的信息
    InputForm[ds]ds 的输入形式
    Normal[ds]将 ds 转换成普通表达式

范例

打开所有单元关闭所有单元

基本范例  (1)

可用 CreateDataStructure 创建新的 "BloomFilter"：

可将任意表达式插入 "BloomFilter" 数据结构：

可以测试是否含有一个表达式. 如果结果为 False，则意味着 f[2] 绝对不在集合中：

如果结果为 True，则意味着f[1] 可能在集合中：

返回表达式形式的 ds：

可视化数据结构：

范围  (2)

信息  (1)

可用 CreateDataStructure 创建新的 "BloomFilter"：

数据结构 ds 的信息：

FalsePositiveProbability  (1)

创建具有高误报率的 "BloomFilter"：

创建具有默认误报率的 "BloomFilter"：

插入一个元素：

误报概率较高的数据结构会返回较多的误报：

可能存在的问题  (1)

非常满的 Bloom 过滤器更有可能在包含测试 (testing for inclusion) 中返回误报.

创建 Bloom 过滤器并插入许多元素. 可视化显示它看起来非常满：

装载因子显示过滤器是满的：

即使元素从未被插入，包含测试也会返回 True. 这是因为过滤器是满的：