如何在空間不足時擴展布隆過濾器？

我正在學習bloom濾波算法。這個概念非常簡單，下面是我在Java中簡單實現的「布隆過濾器結構」。
我的問題是如何擴大容量時，位集幾乎滿了？如果我改變了bitset的大小，顯然我必須再次考慮散列函數，並且我必須重新排列這些存在的元素。
第二個想法是初始化布隆過濾器的另一個實例。但這些只是我的想法，任何人都可以幫助這些？謝謝！如何在空間不足時擴展布隆過濾器？

public class BloomFilter { 

    private static final int DEFAULT_SIZE = 2 << 24; 
    private static final int[] seeds = {7, 11, 13, 31, 37, 61}; 

    static class SimpleHash { 
     private int cap; 
     private int seed; 

     public SimpleHash(int cap, int seed) { 
      this.cap = cap; 
      this.seed = seed; 
     } 

     public int hash(String str) { 
      int result = 0; 
      int length = str.length(); 
      for (int i = 0; i < length; i++) { 
       result = seed * result + str.charAt(i); 
      } 
      return (cap - 1) & result; 
     } 
    } 

    private BitSet bitSet; 
    private SimpleHash[] hashes; 

    public BloomFilter() { 
     bitSet = new BitSet(DEFAULT_SIZE); 
     hashes = new SimpleHash[seeds.length]; 
     for (int i = 0; i < seeds.length; i++) { 
      hashes[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]); 
     } 
    } 

    public void add(String str) { 
     for (SimpleHash hash : hashes) { 
      bitSet.set(hash.hash(str), true); 
     } 
    } 

    public boolean mightContains(String str) { 
     if (str == null) { 
      return false; 
     } 
     boolean result = true; 
     for (SimpleHash hash : hashes) { 
      result = result && bitSet.get(hash.hash(str)); 
     } 

     return result; 
    } 
}

來源

2016-07-26 M.Guo

不要混淆布隆過濾器與集合或集合;他們有不同的屬性。值得注意的是，調整布隆過濾器並沒有多大意義。您需要重新計算所有因此被添加到過濾器中的哈希，這需要仍然引用它們。 – dimo414

[Guava]（https://github.com/google/guava）提供了一個不錯的['BloomFilter']（https://google.github.io/guava/releases/snapshot/api/docs/com/google/ common/hash/BloomFilter.html）[實施]（https://google.github.io/guava/releases/snapshot/api/docs/src-html/com/google/common/hash/BloomFilter.html），您可能會喜歡參考。 – dimo414

雖然我剛剛找到[本文]（http://gsd.di.uminho.pt/members/cbm/ps/dbloom.pdf），它提出了一個由多個布隆過濾器組成的布隆過濾器狀數據結構。它更復雜，漸近性能更差，但它很聰明。儘管如此，爲您的過濾器確定一個良好的起始價值，而不是實現這一目標會更好。 – dimo414

只有當您知道預先插入的元素的數量時，布隆過濾器才起作用。通常你需要假陽性錯誤P和要插入的元素數量N，然後用它們來計算散列函數H和容量M的數量。

如果您事先不知道元素數量，那麼唯一的方法是將所有元素添加到bloom過濾器（例如，在文件中）時在外部存儲所有元素。當添加元素數量超過安全閾值N，您：

刪除當前布隆過濾器實例
創建新M和H從P衍生和N*2（或N*3/2）
讀新布隆過濾器實例將文件中的所有元素插入到新的布隆過濾器實例中

來源

2016-07-26 05:21:41 gudok

如何在空間不足時擴展布隆過濾器？

回答

相關問題