布隆過濾器設計

Question

我想知道我在哪裏可以找到布隆過濾器的實現，並對散列函數的選擇做了一些說明。

此外，我有以下問題：
1）布隆過濾器已知有誤報。是否有可能通過使用兩個過濾器來減少它們，一個用於已使用的元素，一個用於未使用的元素（假設該集合是有限的並且先驗已知的）並比較兩者？
2）在CS文獻中還有其他類似的算法嗎？

Answer 1

我的直覺是通過使用反濾波器佔用的額外空間來擴大正濾波器，可以更好地減少誤報。

至於資源方面，3月8日從my course syllabus引用的論文將是有用的。

Answer 2

Bloom filter的Java實現可以從here找到。如果你不能查看它，我會把代碼粘貼到下面（用中文評論）。

import java.util.BitSet; 

publicclass BloomFilter 
{ 
    /* BitSet初始分配2^24個bit */ 
    privatestaticfinalint DEFAULT_SIZE =1<<25; 
    /* 不同哈希函數的種子，一般應取質數 */ 
    privatestaticfinalint[] seeds =newint[] { 5, 7, 11, 13, 31, 37, 61 }; 
    private BitSet bits =new BitSet(DEFAULT_SIZE); 
    /* 哈希函數對象 */ 
    private SimpleHash[] func =new SimpleHash[seeds.length]; 

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

    // 將字符串標記到bits中 
    publicvoid add(String value) 
    { 
     for (SimpleHash f : func) 
     { 
      bits.set(f.hash(value), true); 
     } 
    } 

    //判斷字符串是否已經被bits標記 
    publicboolean contains(String value) 
    { 
     if (value ==null) 
     { 
      returnfalse; 
     } 
     boolean ret =true; 
     for (SimpleHash f : func) 
     { 
      ret = ret && bits.get(f.hash(value)); 
     } 
     return ret; 
    } 

    /* 哈希函數類 */ 
    publicstaticclass SimpleHash 
    { 
     privateint cap; 
     privateint seed; 

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

     //hash函數，採用簡單的加權和hash 
     publicint hash(String value) 
     { 
      int result =0; 
      int len = value.length(); 
      for (int i =0; i < len; i++) 
      { 
       result = seed * result + value.charAt(i); 
      } 
      return (cap -1) & result; 
     } 
    } 
} 

在設計布隆過濾器而言，哈希函數的布隆過濾器需要多少可確定爲here也闖民宅的Wikipedia article about Bloom filters，然後你發現誤報的部分概率。本節解釋散列函數的數量如何影響誤報的概率，並給出用於根據期望的預期概率確定k的公式。的誤報。從維基百科文章

---

引用：

顯然，假 陽性的概率爲m（比特陣列中的數 ）減小而增加，並且 增加爲n（數插入的 元素）增加。爲了最大限度地減少給定m和 N，K（散列 函數的數量）的值 概率

Answer 3

我認爲，我們應該看看布隆過濾器的應用，祕密在名稱中，它是一個過濾器而不是數據結構。它主要用於通過檢查項目是否不是集合的一部分來節省資源。如果想要將誤報最小化爲0，則必須插入所有不屬於該集合的項目，因爲對於精心設計的布隆過濾器沒有誤報，除非布隆過濾器是巨大且不切實際的，不妨將這些項存儲在跳過列表中:)如果有人對此感興趣，我在Bloom Filters上寫了一個簡單的教程。

http://techeffigy.wordpress.com/2014/06/05/bloom-filter-tutorial/

Answer 4

它非常容易使用Java 8個功能來實現布隆過濾器。你只需要一個long[]來存儲這些位，以及一些散列函數，你可以用ToIntFunction<T>來表示。我在doing this from scratch上做了簡短的介紹。

要注意的部分是從數組中選擇正確的位。

public class BloomFilter<T> { 

    private final long[] array; 
    private final int size; 
    private final List<ToIntFunction<T>> hashFunctions; 

    public BloomFilter(long[] array, int logicalSize, List<ToIntFunction<T>> hashFunctions) { 
     this.array = array; 
     this.size = logicalSize; 
     this.hashFunctions = hashFunctions; 
    } 

    public void add(T value) { 
     for (ToIntFunction<T> function : hashFunctions) { 
       int hash = mapHash(function.applyAsInt(value)); 
       array[hash >>> 6] |= 1L << hash; 
     } 
    } 

    public boolean mightContain(T value) { 
     for (ToIntFunction<T> function : hashFunctions) { 
       int hash = mapHash(function.applyAsInt(value)); 
       if ((array[hash >>> 6] & (1L << hash)) == 0) { 
        return false; 
       } 
     } 
     return true; 
    } 

    private int mapHash(int hash) { 
     return hash & (size - 1); 
    } 


    public static <T> Builder<T> builder() { 
     return new Builder<>(); 
    } 

    public static class Builder<T> { 
     private int size; 
     private List<ToIntFunction<T>> hashFunctions; 

     public Builder<T> withSize(int size) { 
      this.size = size; 
      return this; 
     } 

     public Builder<T> withHashFunctions(List<ToIntFunction<T>> hashFunctions) { 
       this.hashFunctions = hashFunctions; 
       return this; 
      } 

     public BloomFilter<T> build() { 
       return new BloomFilter<>(new long[size >>> 6], size, hashFunctions); 
     } 
    } 
}