Bloom Filter - 布隆过滤器

by
noyesno
at

有一张清单，每当某类事件发生的时候，就在对应的条目上做个标记。根据这个标记可以知道某个事件是否之前发生过。

理想情况下，这张清单足够长，每种事件都有一个对应的条目。

但是如果事件的种类太多，而清单的长度却有限制，该怎么检查是否发生过呢。

基于概率的判断

清单长度小于事件的种类，意味着一定是有重复的可能的。但只要这种重复的可能足够小，结果仍然是可以接受的。

而减少错误的概率的秘诀在于采用多种方法交叉验证。

布隆过滤器

Bloom Filter with Tcl

@block bloom-filter {
   @input  item
   @output exist

   @config hasher_list [list]
   @config M           1000

   @state checklist    [lrepeat $M 0]


   @action add {item} {
      foreach hasher $hasher_list {
         set idx [$hasher $item]
         lset checklist $idx 1
      }
   }

   @action exist {item} => @output exist {
      set exist true

      foreach hasher $hasher_list {
         set idx [$hasher $item]
         if {[lindex $checklist $idx]==0} {
            set exist false
            break
         }
      }

      return $exist
   }
}

Bloom Filter 看作特殊的 Hash 函数

Bloom Filter 的关键是同时采用多个相对独立的 Hash 函数。

在此基础上，我们也可以把 Bloom Filter 看作一种特殊的 Hash 函数 —— Hash 结果中 bit 1 的数目是固定的。

Bloom Filter 误判的概率

TODO

网络资源