用Python製作基數估計器的教程

假設你有一個很大的數據集，非常非常大，以至於不能全部存入內存。這個數據集中有重複的數據，你想找出有多少重複的數據，但數據並沒有排序，由於數據量太大所以排序是不切實際的。你如何來估計數據集中含有多少無重複的數據呢？這在許多應用中是很有用的，比如數據庫中的計劃查詢：最好的查詢計劃不僅僅取決於總共有多少數據，它也取決於它含有多少無重複的數據。

在你繼續讀下去之前，我會引導你思考很多，因爲今天我們要討論的算法雖然很簡單，但極具創意，它不是這麼容易就能想出來的。

一個簡單的樸素基數估計器

讓我們從一個簡單的例子開始吧。假定某人以下列方式來生成數據:

生成 n 個充分分散的隨機數 任意地從中選擇一些數字，使其重複某次 打亂這些數字

我們怎麼估計結果數據集中有多少非重複的數字呢？瞭解到原來的數據集是隨機數,且充分分散，一個非常簡單的方法是：找出最小的數字。如果最大的可能的數值是 m，最小的值是 x，我們 可以估計大概有 m/x 個非重複的數字在數據集裏面。舉個例子，如果我們掃描一個數字在 0 到 1 之間的數據集，發現最小的數字是 0.01。我們有理由猜想可能數據集裏大概有 100 個非重複的數字。如果我們找到一個更小的最小值的話，可能包含的數據個數可能就更多了。請注意不管每個數字重複了多少次都沒關係，這是很自然的，因爲重複多少次並不會影響?min?的輸出值.

這個過程的優點是非常直觀，但同時它也很不精確。不難舉出一個反例：一個只包含少數幾個非重複數字的數據集裏面有一個很小的數。同樣的一個含有許多非重複數字的數據集含有一個比我們想像中更大的最小值，用這種估計方法也會很不精確。最後，很少有數據充分分散充分隨機的數據集。但是這個算法原型給了我們一些靈感使得我們有可能達到我們的目的，我們需要更精緻一些的算法.

基於概率的計數

第一處改進來來自 Flajolet 和 Martin 的論文 Probabilistic Counting Algorithms for Data Base Applications。 進一步的改進來自 Durand-Flajolet 的論文 LogLog counting of large cardinalities 和 Flajolet et al 的論文 HyperLogLog：The analysis of a near-optimal cardinality estimation algorithm。從一篇論文到另一篇論文來觀察想法的產生和改進很有趣，但我的方法稍有不同，我會演示如何從頭開始構建並改善一個解決方法，省略了一些原始論文中的算法。有興趣的讀者可以讀一下那三篇論文，論文裏面包含了大量的數學知識，我這裏不會詳細探討.

首先，Flajolet 和 Martin 發現對於任意數據集，我們總可以給出一個好的哈希函數，使得哈希後的數據集可以是我們需要的任意一種排列。甚至充分分散的(僞)隨機數也是如此。通過這個簡單的靈感，我們可以把我們之前產生的數據集轉化爲我們想要的數據集，但是這遠遠還不夠.

接下來，他們發現存在更好的估計非重複數個數的方法。部分方法比記錄最小的哈希值表現得更好。Flajolet 和 Martin 用的估計方法是計算哈希後的值的首部的 0 字的個數。顯然在一個隨機的數據集中，平均每 2^k 個元素就出現一個長度爲 k 的全爲 0 的比特序列。我們要做的就是找出這些序列並記錄最長的來估計非重複元素的個數。然而這仍然不是一個很棒的估計器。它最多隻能給我們一個 2 的冪的數量的估計。而且不像基於最小值的估計方法，這個方法的方差很大。但在另一個方面，我們的估計需要的空間非常小：爲了記錄最長 32 比特的前導 0 比特序列，我們只需要一個 5 比特的數字就可以了.

　附註：Flajolet-Martin 原先的論文在這裏繼續討論了一種基於 bitmap 的過程來獲得一個更精確的估計。我不會討論這個細節因爲它馬上就會在隨後的方法中得到改進。更多細節對於有興趣的讀者可以閱讀原論文。

現在我們得到了一個確實比較糟糕的比特式估計方法。我們能做出一些什麼改進呢？一個直接的想法是使用多個獨立的哈希函數。如果每個哈希函數?輸出它自己的隨機數據集，我們可以記錄最長的前導 0 比特序列。然後在最後我們就可以對其求一個平均值以得到一個更精確的'估計。

從實驗統計上來看這給了我們一個相當好的結果，但哈希的代價的是很高的。一個更好的方式是一個叫做隨機平均的方法。相比使用多個哈希函數，我們僅僅使用一個哈希函數。但是把它的輸出進行分割然後使用它的一部分作爲桶序號來放到許多桶中一個桶裏去。假設我們需要 1024 個值，我們可以使用哈希函數的前 10 個比特值作爲桶的序號，然後使用剩下的哈希值來計算前導 0 比特序列。這個方法並不會損失精確度，但是節省了大量的哈希計算.

把我們目前學到的應用一下，這裏有一個簡單的實現。這和 Durand-Flajolet 的論文中的算法是等價的，爲了實現方便和清晰所以我計算的是尾部的 0 比特序列。結果是完全等價的。

def trailing_zeroes(num): """Counts the number of trailing 0 bits in num.""" if num == 0: return 32 # Assumes 32 bit integer inputs! p = 0 while (num >> p) & 1 == 0: p += 1 return p def estimate_cardinality(values，k): """Estimates the number of unique elements in the input set values. Arguments: values：An iterator of hashable elements to estimate the cardinality of. k：The number of bits of hash to use as a bucket number; there will be 2**k buckets. """ num_buckets = 2 ** k max_zeroes = [0] * num_buckets for value in values: h = hash(value) bucket = h & (num_buckets - 1) # Mask out the k least significant bits as bucket ID bucket_hash = h >> k max_zeroes[bucket] = max(max_zeroes[bucket]，trailing_zeroes(bucket_hash)) return 2 ** (float(sum(max_zeroes)) / num_buckets) * num_buckets * 0.79402

這很漂亮就像我們描述的一樣：我們保持一個計算前導(或尾部)0個數的數組，然後在最後對個數求平均值，如果我們的平均值是 x，我們的估計就是 2^x 乘以桶的個數。前面沒有說到 的是這個魔術數 0.79402。數據統計表明我們的程序存在一個可預測的偏差，它會給出一個比實際更大的估計值。這個在 Durand-Flajolet 的論文中導出的魔術常數是用來修正這個偏差的。實際上這個數字隨着使用的桶的個數(最大2^64)而發生變化，但是對於更多數目的桶數，它會收斂到我們上面用到的算法的估計數字。大量更多的信息請看完整的論文，包括那個魔術數是怎麼導出的。

這個程序給了我們一個非常好的估計，對於 m 個桶來說，平均錯誤率大概在 1.3/sqrt(m) 左右。所以1024個桶時()，我們大概會有 4% 的期望錯誤率。爲了估計每篇最多 2^27 個數據的數據集每個桶僅需要 5 比特就夠了。少於 1 kb 內存，這真的很贊(1024 * 5 = 5120，即 640 字節)!

讓我們在一些隨機的數據上測試一下它:

>>> [100000/estimate_cardinality([om() for i in range(100000)]，10) for j in range(10)][0.9825616152548807，0.9905752876839672，0.979241749110407，1.050662616357679，0.937090578752079，0.9878968276629505，0.9812323203117748，1.0456960262467019，0.9415413413873975，0.9608567203911741]

結果不壞，一些估計超過 4% 的預期偏差，但總而言之結果都很好。如果你自己再嘗試一遍這個實驗，請注意：Python 內建的 hash() 函數將整數哈希爲它們本身。導致運行像 estimate_cardinality(range(10000)，10) 這樣的會給出偏差很大的結果，因爲此時的 hash() 不是一個好的哈希函數。當然使用上述例子中的隨機數是沒有問題的.

改進準確度：SuperLogLog 和 HyperLogLog

雖然我們已經得到了一個非常好的估計，但它有可能做到更好。Durand 和 Flajolet 發現極端數值會很大地影響估計結果的準確度。通過在求平均前捨棄一些最大值，準確度可以得到提高。特別地，捨棄前 30% 大的桶，僅僅計算 70% 的桶的平均值，精確度可以用 1.30/sqrt(m) 提高到 1.05/sqrt(m)! 這意味着在我們之前的例子中，用 640 字節的狀態，平均錯誤率從 4% 變成了大約 3.2%。但並沒增加空間的使用.

最後，Flajolet et al 的論文的貢獻就是使用了一個不同類型的平均數。使用調和平均數而不是幾何平均數。通過這麼做，我們可以把錯誤率降到 1.04/sqrt(m)，同樣不增加需要的空間。當然完整的算法要更復雜一點，因爲它必須修正小的和大的基數誤差。有興趣的讀者應該，可能你已經猜到了，就是去閱讀完整的論文.

並行化

這些方案所共有的整齊性使得它們很容易就能並行化。多臺機器可以獨立地運行同樣的哈希函數同樣數目的桶。我們在最後只需要把結果結合起來，取每個算法實例中每個桶最大的值就可以了。這不僅很好實現，因爲我們最多隻需要傳輸不到 1kb 的數據就可以了，而且和在單臺機器上運行的結果是完全一模一樣的.

總結

就像我們剛剛討論過的基數排序算法，使得有可能得到一個非重複數字個數的很好的估計。通常只用不到 1kb 空間。我們可以不依賴數據的種類而使用它，並且可以分佈式地在多臺機器上工作，機器間的協調和數據的傳輸達到最小。結果估計數可以用來做許多事情，比如流量監控(多少個獨立IP訪問過？)和數據庫查詢優化(我們應該排序然後歸併呢還是構造一個哈希表呢？)。