布隆過濾器從O（n）中的整數流中移除重複項

Question

如何創建布隆過濾器以從O（n）時間複雜度的整數流中移除重複元素O（1）空間複雜度？ 如果可能的話，如果有人能指出我正確的方向，我將不勝感激。

Answer 1

我相當肯定，它只是：

對於每一個元素：

• 檢查它是否在布隆過濾器中存在，如果這樣做，很可能重複
• 將其插入布隆過濾器

現在有兩個問題：

• 存在誤報的可能性
• 它不是真正的O（1）空間（但有些人可能會這麼說），因爲大小需要在某種程度上取決於（唯一）元素的數量，否則，隨着我們增加元素的數量，錯誤率將顯着增加。

我不相信任何這些問題都可以避免給定的限制 - 都是使用（只）布隆過濾器的組成部分。

如果我們不是在處理流，而是在處理一個列表，我們可以通過記錄bloom過濾器拾取的所有元素並再次遍歷列表來檢查候選列表，從而消除誤報以確保它們是實際的重複項目。這仍然是O（n）時間，但顯然不是O（1）空間。

Answer 2

Google Guava提供了bloom過濾器實現。

請注意，bloom濾波器本身是不夠的。如果布隆過濾器聲稱數字不在其中，那麼它不在其中。但如果它聲稱這個數字已經在其中，那麼就有可能是錯的。所以你需要在那裏有另一個數據結構，並確保使用bloomfilter來減少數據結構中的查找次數。