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

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

一個簡單直觀的基數(shù)估計方法

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

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

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

3、打亂這些數(shù)字的順序，得到一個數(shù)據(jù)集

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

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

[[104049]]

基數(shù)估計的概率算法

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

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

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

值得一提的是，F(xiàn)lajolet-Martin在最初的論文里通過一種基于bitmap的過程去提高估計算法的準(zhǔn)確度。關(guān)于這點我就不再詳述了，因為這種方法已經(jīng)被后續(xù)論文中更好的方法所取代；對這個細節(jié)有興趣的讀者可以去閱讀原始論文。

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

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

根據(jù)上述分析，我們可以給出一個簡單的算法實現(xiàn)。這個實現(xiàn)等價于Durand-Flajolet的論文中提出的LogLog算法；不過為了方便，這個實現(xiàn)中統(tǒng)計的是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 

這段代碼實現(xiàn)了我們上面討論的估計算法：我們計算每個桶的0前綴（或尾綴）的最長長度；然后計算這些長度的平均數(shù)；假設(shè)平均數(shù)是x，桶數(shù)量是m，則 最終的估計值是2x×m。其中一個沒提過的地方是魔法數(shù)字0.79402。統(tǒng)計分析顯示這種預(yù)測方法存在一個可預(yù)測的偏差；這個魔法數(shù)字是對這個偏差的修 正。實際經(jīng)驗表明計算值隨著桶數(shù)量的不同而變化，不過當(dāng)桶數(shù)量不太小時（大于64），計算值會收斂于估計值。原論文中描述了這個結(jié)論的推導(dǎo)過程。

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

讓我們看一下試驗結(jié)果：

>>> [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%的平均誤差，但總體來說效果良好。如果你準(zhǔn)備自己做一下這個試驗，有一點需要注意：Python內(nèi)置的 hash() 方法將整數(shù)哈希為它自己。因此諸如 estimate_cardinality(range(10000), 10) 這種方式得到的結(jié)果不會很理想，因為內(nèi)置 hash() 對于這種情況并不能生成很好的散列。但是像上面例子中使用隨機數(shù)會好很多。

提升準(zhǔn)確度：SuperLogLog和HyperLogLog

雖然我們已經(jīng)有了一個不錯的估計算法，但是我們還能進一步提升算法的準(zhǔn)確度。Durand和Flajolet發(fā)現(xiàn)離群點會大大降低估計準(zhǔn)確度；如果 在計算平均值前丟棄一些特別大的離群值，則可以提高精確度。特別的，通過丟棄最大的30%的桶的值，只使用較小的70%的桶的值來進行平均值計算，則平均 誤差可以從1.3/m−−√降低到1.05/m−−√！這意味著在我們上面的例子中，使用640個字節(jié)可情況下可以將平均誤差從4%降低到3.2%，而所 需內(nèi)存并沒有增加。

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

并行化

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

結(jié)論

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

英文原文：Damn Cool Algorithms: Cardinality Estimation

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