重疊的字節數組的子數組是否足以獨立地用作Bloom Filter的散列函數？

我在BloomFilter的上下文中有以下問題。 BloomFilters需要具有獨立的散列函數k。我們稱這些函數爲h1, h2, ... hk。在這種情況下獨立意味着它們的價值在應用於相同的集合時將具有非常小的相關性（希望爲零）。請參閱http://en.wikipedia.org/wiki/Bloom_filter上的算法描述（但當然，您已經知道該頁面裏面有:)。重疊的字節數組的子數組是否足以獨立地用作Bloom Filter的散列函數？

現在，假設我想使用一些n位（來自加密函數，如果您必須知道的，但它與問題無關）來定義我的散列函數，這些位彼此獨立。如果你想要更多的上下文，你可以閱讀http://bitworking.org/news/380/bloom-filter-resources這是做類似的事情。

例如，假設我要定義每個h爲（原諒我的僞代碼）：

bytes = MD5(value) 
h1 = bytes[0-3] as Integer 
h2 = bytes[4-7] as Integer 
h3 = bytes[8-11] as Integer 
...

我們當然會用完的散列函數非常快中。在這個MD5例子中我們只得到四個。

一種可能性是讓散列函數相互重疊，並且不要求這四個字節是連續的。這樣我們有許多散列函數作爲字節數組允許的排列。爲了保持它的簡單，如果我們以下面的方式定義的哈希函數：

bytes = MD5(value) 
h1 = bytes[0-3] as Integer 
h2 = bytes[1-4] as Integer 
h3 = bytes[2-5] as Integer 
...

不難看出，在MD5情況下，我們現在有12個散列函數，而不是四個。

最後，我們得到THE的問題。這些哈希函數是獨立的嗎？謝謝！

UPDATE：我決定嘗試從實際的角度回答這個問題，所以我創建了一個小程序來測試這個假設。見下文。

來源

2011-07-11 Andres Rodriguez

聰明的問題經常出現，答案是肯定的，不是。

是的，就是說有16位不在h1和h2之間共享。不，對你來說很重要的感覺（除非你實際上只使用八位哈希函數，我猜你不是）。

這裏的問題是適用於插入同一項目的兩個函數之間的依賴性較小，而在我看來這種情況下，這些函數應用於多個項目。

想想這樣。假設你的第一個例子使用g1-g4，第二個使用h1-h4。如果只使用h1和h2，h2和h3，MD5sum（或任何其他哈希函數）只有5個連續字節重疊（不太可能，但在統計上可行，尤其是如果您嘗試的話）的兩個項目將有碰撞的機會，或h3和h4。同時，g1-g4對這種可能性很有力。

現在與bloom過濾器的衝突並不像散列函數的其他應用那麼重要，但是您應該記住重疊的字節確實會降低散列函數的實用性。說實話，我有點驚訝，你需要超過四個獨立的散列函數。另外，如果您只使用每個數字的最後8位（256位布隆過濾器）或最後16位（2^16位布隆過濾器）或其他，那麼您可以'重疊'位你不是在肆意放棄而沒有風險的情況下使用。

免責聲明：我知道密碼學相當不錯，布盧姆過濾器，因爲他們是fricking真棒，但我的bloom過濾器的實用知識是有限的;你所描述的可能對你的用例非常有效。

來源

2011-07-13 03:58:30 Slartibartfast

感謝您的回答。我想我明白你所描述的權衡。但是，我不確定我是否理解你關於散列衝突的觀點。在我給出的例子中，字節來自MD5，但它們也可以來自Java的[Random.nextBytes]（http://download.oracle.com/javase/6/docs/api/java/util/Random .html＃nextBytes（byte []））函數。在這種情況下，問題將是：當我們生成一個序列字節數組「b1，b2，b3 ...」並將一個子鏈解釋爲一個整數（例如'b2 [3-7]'）時，這兩個子鏈相關係數高或低？ –

運行下面的程序將用隨機數發生器測試假設。

public static void main(String[] args) { 
    int R = 100, N = 10000, W = 8; 
    double[] totals = new double[33]; 
    Random r = new Random(); 

    for (int k = 0; k < R; k++) { 
     // Generate 10,000 random byte arrays 
     byte[][] bytes = new byte[N][W]; 
     for (int i = 0; i < N; i++) r.nextBytes(bytes[i]); 

     double[] a1 = new double[N], a2 = new double[N]; 
     for (int i = 0; i <= 32; i++) { 

      // Extract arrays 
      for (int j = 0; j < N; j++) { 
       a1[j] = readInt(bytes[j], 0, 31); 
       a2[j] = readInt(bytes[j], 32 - i, 31); 
      } 

      double c = (new PearsonsCorrelation()).correlation(a1, a2); 
      totals[i] += c; 
     } 
    } 
}

有趣比特是，只有當僅存在一個重疊的位，所述相關開始被顯著。以下是每個重疊位數的皮爾遜相關係數。我們開始非常低（意思是接近0重疊的情況），並且當它們完全重疊時得到1。

0 -0.001883705757299319 
1 -0.0019261826793995395 
2 -0.0018466135577488883 
3 -0.001499114477250019 
4 -0.0010874727770462341 
5 -1.1219111699336884E-5 
6 -0.001760700583842139 
7 3.6545455908216937E-4 
8 0.0014823972050436482 
9 0.0014809963180788554 
10 0.0015226692114697182 
11 0.00199027499920776 
12 0.001720451344380218 
13 -2.0219121772336676E-4 
14 6.880004078769847E-4 
15 8.605949344202965E-4 
16 -0.0025640320027890645 
17 -0.002552269654230886 
18 -0.002550425130285998 
19 -0.002522446787072504 
20 -0.00320337678141518 
21 -7.554573868921899E-4 
22 -6.463448718890875E-4 
23 -3.4709181348336335E-4 
24 0.0038077518094915912 
25 0.0037865326140343815 
26 0.0038728464390708982 
27 0.0035091958914765407 
28 0.005099109955591643 
29 0.016993434043779915 
30 0.06120260114179265 
31 0.25159073855202346 
32 1.0

底線：好像一個字節（這意味着上面的24值）的變化應該相對於散列函數生成相當安全的。

來源

2011-07-19 21:24:49

重疊的字節數組的子數組是否足以獨立地用作Bloom Filter的散列函數？

回答

相關問題