爲什麼將1添加到超級日誌算法中的前導零計數

Question

如果在哈希的位模式中存在k個前導零數，爲什麼估計大小被認爲是2 ^{k + 1}？不應該是2 ^k？具有k個前導零的概率應該是1 /（2 ^ķ），並且因此尺寸​​應2 ^ķ

在我的代碼總是得到尺寸的正確估計當我使用K + 1代替k的。但我不明白這背後的邏輯。

Answer 1

您正在尋找的直覺是該算法依賴於在哈希開始處（k個零，後面是1）看到整個位模式的概率，而不僅僅是零。

更困難的部分是從那裏到估計基數在2 ^{k + 1}。不幸的是，這種形式的證明並不簡單。實際上，介紹該方法的大多數原始原始論文（Flajolet和Martin，數據庫應用的概率計數算法，http://algo.inria.fr/flajolet/Publications/FlMa85.pdf）致力於證明用它計算的估計值是一個很好的估計值。隨後的論文（LogLog和HyperLogLog論文）對他們的改進估算也有類似的證明。

希望有幫助！

Answer 2

根據概率論，你是對的！在觀察到具有k個前導零的值之前，您會期望得到（平均值）。

您的估計值是原來的兩倍的原因可能是因爲您的隨機函數（或散列函數）正在返回總是正數的帶符號整數，並且始終存在前導零。這應該使您看到k個前導零的值的概率增加一倍。這就是爲什麼當你使用2 ^{k + 1}而不是2 ^k時你會得到正確的答案。

Answer 3

k前導零表示前k位是後面跟一位的零。 （否則，我們將有超過k個前導零比特）。因此，k個前導零實際上由長度爲（k + 1）的比特序列表徵，其概率爲1/2 ^（k + 1）。