假如你有一個巨大的含有重復數據項數據集，這個數據集過于龐大以至于無法全部放到內存中處理。現在你想知道這個數據集里有多少不同的元素，但是數據 集沒有排好序，而且對如此大的一個數據集進行排序和計數幾乎是不可行的。你要如何估計數據集中有多少不同的數據項？很多應用場景都涉及這個問題，例如設計 數據庫的查詢策略：一個良好的數據庫查詢策略不但和總的數據量有關，同時也依賴于數據中不同數據項的數量。

我建議在繼續閱讀本文前你可以稍微是思考一下這個問題，因為接下來我們要談的算法相當有創意，而且實在是不怎么直觀。

一個簡單直觀的基數估計方法

讓我們從一個簡單直觀的例子開始吧。假設你通過如下步驟生成了一個數據集：

1、隨機生成n個服從均勻分布的數字

2、隨便重復其中一些數字，重復的數字和重復次數都不確定

3、打亂這些數字的順序，得到一個數據集

我們要如何估計這個數據集中有多少不同的數字呢？因為知道這些數字是服從均勻分布的隨機數字，一個比較簡單的可行方案是：找出數據集中最小的數字。 假如m是數值上限，x是找到的最小的數，則m/x是基數的一個估計。例如，我們掃描一個包含0到1之間數字組成的數據集，其中最小的數是0.01，則一個 比較合理的推斷是數據集中大約有100個不同的元素，否則我們應該預期能找到一個更小的數。注意這個估計值和重復次數無關：就如最小值重復多少次都不改變 最小值的數值。

這個估計方法的優點是十分直觀，但是準確度一般。例如，一個只有很少不同數值的數據集卻擁有很小的最小值；類似的一個有很多不同值的數據集可能最小 值并不小。最后一點，其實只有很少的數據集符合隨機均勻分布這一前提。盡管如此，這個原型算法仍然是了解基數估計思想的一個途徑；后面我們會了解一些更加 精巧的算法。

[[104049]]

基數估計的概率算法

最早研究高精度基數估計的論文是Flajolet和Martin的Probabilistic Counting Algorithms for Data Base Applications，后來Flajolet又發表了LogLog counting of large cardinalities和HyperLogLog: The analysis of a near-optimal cardinality estimation algorithm兩篇論文對算法進行了進一步改進。通過逐篇閱讀這些論文來了解算法的發展和細節固然有趣，不過在這篇文章中我會忽略一些算法的理論細節，把精力主要放在如何通過論文中的算法解決問題。有興趣的讀者可以讀一下這三篇論文；本文不會介紹其中的數學細節。

Flajolet和Martin最早發現通過一個良好的哈希函數，可以將任意數據集映射成服從均勻分布的（偽）隨機值。根據這一事實，可以將任意數據集變換為均勻分布的隨機數集合，然后就可以使用上面的方法進行估計了，不過只是這樣是遠遠不夠的。

接下來，他們陸續發現一些其它的基數估計方法，而其中一些方法的效果優于之前提到的方法。Flajolet和Martin計算了哈希值的二進制表示 的0前綴，結果發現在隨機數集合中，通過計算每一個元素的二進制表示的0前綴，設k為最長的0前綴的長度，則平均來說集合中大約有2k個不同的元素；我們 可以用這個方法估計基數。但是，這仍然不是很理想的估計方法，因為和基于最小值的估計一樣，這個方法的方差很大。不過另一方面，這個估計方法比較節省資 源：對于32位的哈希值來說，只需要5比特去存儲0前綴的長度。

值得一提的是，Flajolet-Martin在最初的論文里通過一種基于bitmap的過程去提高估計算法的準確度。關于這點我就不再詳述了，因為這種方法已經被后續論文中更好的方法所取代；對這個細節有興趣的讀者可以去閱讀原始論文。

到目前為止，我們這種基于位模式的估計算法給出的結果仍然不夠理想。如何進行改進呢？一個直觀的改進方法就是使用多個相互獨立的哈希函數：通過計算每個哈希函數所產生的最長0前綴，然后取其平均值可以提高算法的精度。

實踐表明從統計意義來說這種方法確實可以提高估計的準確度，但是計算哈希值的消耗比較大。另一個更高效的方法就是隨機平均（stochastic averaging）。這種方法不是使用多個哈希函數，而是使用一個哈希函數，但是將哈希值的區間按位切分成多個桶（bucket）。例如我們希望取 1024個數進行平均，那么我們可以取哈希值的前10比特作為桶編號，然后計算剩下部分的0前綴長度。這種方法的準確度和多哈希函數方法相當，但是比計算 多個哈希效率高很多。

根據上述分析，我們可以給出一個簡單的算法實現。這個實現等價于Durand-Flajolet的論文中提出的LogLog算法；不過為了方便，這個實現中統計的是0尾綴而不是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，桶數量是m，則 最終的估計值是2x×m。其中一個沒提過的地方是魔法數字0.79402。統計分析顯示這種預測方法存在一個可預測的偏差；這個魔法數字是對這個偏差的修 正。實際經驗表明計算值隨著桶數量的不同而變化，不過當桶數量不太小時（大于64），計算值會收斂于估計值。原論文中描述了這個結論的推導過程。

這個方法給出的估計值比較精確 —— 在分桶數為m的情況下，平均誤差為1.3/m−−√。因此對于分桶數為1024的情況（所需內存1024*5 = 5120位，或640字節），大約會有4%的平均誤差；每桶5比特的存儲已經足以估計227的數據集，而我們只用的不到1k的內存！

讓我們看一下試驗結果：

>>> [100000/estimate_cardinality([random.random() 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.3/m−−√降低到1.05/m−−√！這意味著在我們上面的例子中，使用640個字節可情況下可以將平均誤差從4%降低到3.2%，而所 需內存并沒有增加。

最后，Flajolet等人在HyperLogLog論文中給出一種不同的平均值，使用調和平均數取代幾何平均數（譯注：原文有誤，此處應該是算數 平均數）。這一改進可以將平均誤差降到1.04/m−−√，而且并沒不需要額外資源。但是這個算法比前面的算法復雜很多，因為對于不同基數的數據集要做不 同的修正。有興趣的讀者可以閱讀原論文。

并行化

這些基數估計算法的一個好處就是非常容易并行化。對于相同分桶數和相同哈希函數的情況，多臺機器節點可以獨立并行的執行這個算法；最后只要將各個節 點計算的同一個桶的最大值做一個簡單的合并就可以得到這個桶最終的值。而且這種并行計算的結果和單機計算結果是完全一致的，所需的額外消耗僅僅是小于1k 的字節在不同節點間的傳輸。

結論

基數估計算法使用很少的資源給出數據集基數的一個良好估計，一般只要使用少于1k的空間存儲狀態。這個方法和數據本身的特征無關，而且可以高效的進 行分布式并行計算。估計結果可以用于很多方面，例如流量監控（多少不同IP訪問過一個服務器）以及數據庫查詢優化（例如我們是否需要排序和合并，或者是否 需要構建哈希表）。

英文原文：Damn Cool Algorithms: Cardinality Estimation

譯文鏈接：http://www.codinglabs.org/html/cardinality-estimation.html