Bloomier Filter

說到 Bloomier Filter,看倌一定會覺得看起來和 Bloom Filter 很像(詳情請看 Bloom Filter )。 是的,而且兩者演算法本身確實也有相似之處,不過用途並不相同。

Bloom Filter 可以紀錄「某一個元素是否存在」這種型態的資料, 我們可以利用這種資料結構來查詢某元素是否存在的資訊,如查詢「某小雞是不是在這一間雞舍?」這種訊息。 雖然 Bloom Filter 的結果不準確,可能發生「明明不存在,卻回報存在」的狀況,但因為所佔空間小, 而且搜尋速度快的特性,所以常用來做前期的篩選。

但 Bloomier Filter 不同,它不會放棄資料的正確性,而且不像 Bloom Filter 只能存「某一個元素是否存在」的資訊, 因此可以當作實際存放資料的地方,是故 Bloomier Filter 雖然稱作 Filter,但並不只能做 Filter 的事。

Continue reading

Bloom Filter

Bloom Filter 是一種可以儲存「某一個元素是否存在」的集合, 我們可以用這種資料結構快速查詢像是「某隻小雞是否在這間雞舍」或「某位學生是不是在這間實驗室」 這一類的資訊。

這種資料結構有三個非常重要的特性:

  • 不存在漏報(False Negative):有一定會說
  • 但卻可能誤報(False Positive):但說了不一定會對
  • 確定某元素是否在集合的代價和元素數目無關:不管對不對,反正很快
Continue reading