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

我建議在繼續(xù)閱讀本文前你可以稍微是思考一下這個(gè)問(wèn)題，因?yàn)榻酉聛?lái)我們要談的算法相當(dāng)有創(chuàng)意，而且實(shí)在是不怎么直觀。

一個(gè)簡(jiǎn)單直觀的基數(shù)估計(jì)方法

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

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

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

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

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

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

[[104049]]

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

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

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

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

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

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

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

根據(jù)上述分析，我們可以給出一個(gè)簡(jiǎn)單的算法實(shí)現(xiàn)。這個(gè)實(shí)現(xiàn)等價(jià)于Durand-Flajolet的論文中提出的LogLog算法；不過(guò)為了方便，這個(gè)實(shí)現(xiàn)中統(tǒng)計(jì)的是0尾綴而不是0前綴；其效果是等價(jià)的。

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 

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

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

讓我們看一下試驗(yàn)結(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] 

不錯(cuò)！雖然有些估計(jì)誤差大于4%的平均誤差，但總體來(lái)說(shuō)效果良好。如果你準(zhǔn)備自己做一下這個(gè)試驗(yàn)，有一點(diǎn)需要注意：Python內(nèi)置的 hash() 方法將整數(shù)哈希為它自己。因此諸如 estimate_cardinality(range(10000), 10) 這種方式得到的結(jié)果不會(huì)很理想，因?yàn)閮?nèi)置 hash() 對(duì)于這種情況并不能生成很好的散列。但是像上面例子中使用隨機(jī)數(shù)會(huì)好很多。

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

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

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

并行化

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

結(jié)論

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

英文原文：Damn Cool Algorithms: Cardinality Estimation

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