假設(shè)你有一個(gè)很大的數(shù)據(jù)集，非常非常大，以至于不能全部存入內(nèi)存。這個(gè)數(shù)據(jù)集中有重復(fù)的數(shù)據(jù)，你想找出有多少重復(fù)的數(shù)據(jù)，但數(shù)據(jù)并沒(méi)有排序，由于數(shù)據(jù)量太大所以排序是不切實(shí)際的。你如何來(lái)估計(jì)數(shù)據(jù)集中含有多少無(wú)重復(fù)的數(shù)據(jù)呢？這在許多應(yīng)用中是很有用的，比如數(shù)據(jù)庫(kù)中的計(jì)劃查詢：最好的查詢計(jì)劃不僅僅取決于總共有多少數(shù)據(jù)，它也取決于它含有多少無(wú)重復(fù)的數(shù)據(jù)。

在你繼續(xù)讀下去之前，我會(huì)引導(dǎo)你思考很多，因?yàn)榻裉煳覀円懻摰乃惴m然很簡(jiǎn)單，但極具創(chuàng)意，它不是這么容易就能想出來(lái)的。
一個(gè)簡(jiǎn)單的樸素基數(shù)估計(jì)器

讓我們從一個(gè)簡(jiǎn)單的例子開(kāi)始吧。假定某人以下列方式來(lái)生成數(shù)據(jù):

•     生成 n 個(gè)充分分散的隨機(jī)數(shù)
•     任意地從中選擇一些數(shù)字，使其重復(fù)某次
•     打亂這些數(shù)字

我們?cè)趺垂烙?jì)結(jié)果數(shù)據(jù)集中有多少非重復(fù)的數(shù)字呢？了解到原來(lái)的數(shù)據(jù)集是隨機(jī)數(shù),且充分分散，一個(gè)非常簡(jiǎn)單的方法是：找出最小的數(shù)字。如果最大的可能的數(shù)值是 m，最小的值是 x，我們 可以估計(jì)大概有 m/x 個(gè)非重復(fù)的數(shù)字在數(shù)據(jù)集里面。舉個(gè)例子，如果我們掃描一個(gè)數(shù)字在 0 到 1 之間的數(shù)據(jù)集，發(fā)現(xiàn)最小的數(shù)字是 0.01。我們有理由猜想可能數(shù)據(jù)集里大概有 100 個(gè)非重復(fù)的數(shù)字。如果我們找到一個(gè)更小的最小值的話，可能包含的數(shù)據(jù)個(gè)數(shù)可能就更多了。請(qǐng)注意不管每個(gè)數(shù)字重復(fù)了多少次都沒(méi)關(guān)系，這是很自然的，因?yàn)橹貜?fù)多少次并不會(huì)影響?min?的輸出值.

這個(gè)過(guò)程的優(yōu)點(diǎn)是非常直觀，但同時(shí)它也很不精確。不難舉出一個(gè)反例：一個(gè)只包含少數(shù)幾個(gè)非重復(fù)數(shù)字的數(shù)據(jù)集里面有一個(gè)很小的數(shù)。同樣的一個(gè)含有許多非重復(fù)數(shù)字的數(shù)據(jù)集含有一個(gè)比我們想像中更大的最小值，用這種估計(jì)方法也會(huì)很不精確。最后，很少有數(shù)據(jù)充分分散充分隨機(jī)的數(shù)據(jù)集。但是這個(gè)算法原型給了我們一些靈感使得我們有可能達(dá)到我們的目的，我們需要更精致一些的算法.
基于概率的計(jì)數(shù)

第一處改進(jìn)來(lái)來(lái)自 Flajolet 和 Martin 的論文 Probabilistic Counting Algorithms for Data Base Applications。 進(jìn)一步的改進(jìn)來(lái)自 Durand-Flajolet 的論文 LogLog counting of large cardinalities 和 Flajolet et al 的論文 HyperLogLog：The analysis of a near-optimal cardinality estimation algorithm。從一篇論文到另一篇論文來(lái)觀察想法的產(chǎn)生和改進(jìn)很有趣，但我的方法稍有不同，我會(huì)演示如何從頭開(kāi)始構(gòu)建并改善一個(gè)解決方法，省略了一些原始論文中的算法。有興趣的讀者可以讀一下那三篇論文，論文里面包含了大量的數(shù)學(xué)知識(shí)，我這里不會(huì)詳細(xì)探討.

首先，F(xiàn)lajolet 和 Martin 發(fā)現(xiàn)對(duì)于任意數(shù)據(jù)集，我們總可以給出一個(gè)好的哈希函數(shù)，使得哈希后的數(shù)據(jù)集可以是我們需要的任意一種排列。甚至充分分散的(偽)隨機(jī)數(shù)也是如此。通過(guò)這個(gè)簡(jiǎn)單的靈感，我們可以把我們之前產(chǎn)生的數(shù)據(jù)集轉(zhuǎn)化為我們想要的數(shù)據(jù)集，但是這遠(yuǎn)遠(yuǎn)還不夠.

接下來(lái)，他們發(fā)現(xiàn)存在更好的估計(jì)非重復(fù)數(shù)個(gè)數(shù)的方法。部分方法比記錄最小的哈希值表現(xiàn)得更好。Flajolet 和 Martin 用的估計(jì)方法是計(jì)算哈希后的值的首部的 0 字的個(gè)數(shù)。顯然在一個(gè)隨機(jī)的數(shù)據(jù)集中，平均每 2^k 個(gè)元素就出現(xiàn)一個(gè)長(zhǎng)度為 k 的全為 0 的比特序列。我們要做的就是找出這些序列并記錄最長(zhǎng)的來(lái)估計(jì)非重復(fù)元素的個(gè)數(shù)。然而這仍然不是一個(gè)很棒的估計(jì)器。它最多只能給我們一個(gè) 2 的冪的數(shù)量的估計(jì)。而且不像基于最小值的估計(jì)方法，這個(gè)方法的方差很大。但在另一個(gè)方面，我們的估計(jì)需要的空間非常小：為了記錄最長(zhǎng) 32 比特的前導(dǎo) 0 比特序列，我們只需要一個(gè) 5 比特的數(shù)字就可以了.

附注：Flajolet-Martin 原先的論文在這里繼續(xù)討論了一種基于 bitmap 的過(guò)程來(lái)獲得一個(gè)更精確的估計(jì)。我不會(huì)討論這個(gè)細(xì)節(jié)因?yàn)樗R上就會(huì)在隨后的方法中得到改進(jìn)。更多細(xì)節(jié)對(duì)于有興趣的讀者可以閱讀原論文。

現(xiàn)在我們得到了一個(gè)確實(shí)比較糟糕的比特式估計(jì)方法。我們能做出一些什么改進(jìn)呢？一個(gè)直接的想法是使用多個(gè)獨(dú)立的哈希函數(shù)。如果每個(gè)哈希函數(shù)?輸出它自己的隨機(jī)數(shù)據(jù)集，我們可以記錄最長(zhǎng)的前導(dǎo) 0 比特序列。然后在最后我們就可以對(duì)其求一個(gè)平均值以得到一個(gè)更精確的估計(jì)。

從實(shí)驗(yàn)統(tǒng)計(jì)上來(lái)看這給了我們一個(gè)相當(dāng)好的結(jié)果，但哈希的代價(jià)的是很高的。一個(gè)更好的方式是一個(gè)叫做隨機(jī)平均的方法。相比使用多個(gè)哈希函數(shù)，我們僅僅使用一個(gè)哈希函數(shù)。但是把它的輸出進(jìn)行分割然后使用它的一部分作為桶序號(hào)來(lái)放到許多桶中一個(gè)桶里去。假設(shè)我們需要 1024 個(gè)值，我們可以使用哈希函數(shù)的前 10 個(gè)比特值作為桶的序號(hào)，然后使用剩下的哈希值來(lái)計(jì)算前導(dǎo) 0 比特序列。這個(gè)方法并不會(huì)損失精確度，但是節(jié)省了大量的哈希計(jì)算.

把我們目前學(xué)到的應(yīng)用一下，這里有一個(gè)簡(jiǎn)單的實(shí)現(xiàn)。這和 Durand-Flajolet 的論文中的算法是等價(jià)的，為了實(shí)現(xiàn)方便和清晰所以我計(jì)算的是尾部的 0 比特序列。結(jié)果是完全等價(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

這很漂亮就像我們描述的一樣：我們保持一個(gè)計(jì)算前導(dǎo)(或尾部)0個(gè)數(shù)的數(shù)組，然后在最后對(duì)個(gè)數(shù)求平均值，如果我們的平均值是 x，我們的估計(jì)就是 2^x 乘以桶的個(gè)數(shù)。前面沒(méi)有說(shuō)到 的是這個(gè)魔術(shù)數(shù) 0.79402。數(shù)據(jù)統(tǒng)計(jì)表明我們的程序存在一個(gè)可預(yù)測(cè)的偏差，它會(huì)給出一個(gè)比實(shí)際更大的估計(jì)值。這個(gè)在 Durand-Flajolet 的論文中導(dǎo)出的魔術(shù)常數(shù)是用來(lái)修正這個(gè)偏差的。實(shí)際上這個(gè)數(shù)字隨著使用的桶的個(gè)數(shù)(最大2^64)而發(fā)生變化，但是對(duì)于更多數(shù)目的桶數(shù)，它會(huì)收斂到我們上面用到的算法的估計(jì)數(shù)字。大量更多的信息請(qǐng)看完整的論文，包括那個(gè)魔術(shù)數(shù)是怎么導(dǎo)出的。

這個(gè)程序給了我們一個(gè)非常好的估計(jì)，對(duì)于 m 個(gè)桶來(lái)說(shuō)，平均錯(cuò)誤率大概在 1.3/sqrt(m) 左右。所以1024個(gè)桶時(shí)()，我們大概會(huì)有 4% 的期望錯(cuò)誤率。為了估計(jì)每篇最多 2^27 個(gè)數(shù)據(jù)的數(shù)據(jù)集每個(gè)桶僅需要 5 比特就夠了。少于 1 kb 內(nèi)存，這真的很贊(1024 * 5 = 5120，即 640 字節(jié))!

讓我們?cè)谝恍╇S機(jī)的數(shù)據(jù)上測(cè)試一下它:
 

>>> [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]

結(jié)果不壞，一些估計(jì)超過(guò) 4% 的預(yù)期偏差，但總而言之結(jié)果都很好。如果你自己再嘗試一遍這個(gè)實(shí)驗(yàn)，請(qǐng)注意：Python 內(nèi)建的 hash() 函數(shù)將整數(shù)哈希為它們本身。導(dǎo)致運(yùn)行像 estimate_cardinality(range(10000)，10) 這樣的會(huì)給出偏差很大的結(jié)果，因?yàn)榇藭r(shí)的 hash() 不是一個(gè)好的哈希函數(shù)。當(dāng)然使用上述例子中的隨機(jī)數(shù)是沒(méi)有問(wèn)題的.
改進(jìn)準(zhǔn)確度：SuperLogLog 和 HyperLogLog

雖然我們已經(jīng)得到了一個(gè)非常好的估計(jì)，但它有可能做到更好。Durand 和 Flajolet 發(fā)現(xiàn)極端數(shù)值會(huì)很大地影響估計(jì)結(jié)果的準(zhǔn)確度。通過(guò)在求平均前舍棄一些最大值，準(zhǔn)確度可以得到提高。特別地，舍棄前 30% 大的桶，僅僅計(jì)算 70% 的桶的平均值，精確度可以用 1.30/sqrt(m) 提高到 1.05/sqrt(m)! 這意味著在我們之前的例子中，用 640 字節(jié)的狀態(tài)，平均錯(cuò)誤率從 4% 變成了大約 3.2%。但并沒(méi)增加空間的使用.

最后，F(xiàn)lajolet et al 的論文的貢獻(xiàn)就是使用了一個(gè)不同類(lèi)型的平均數(shù)。使用調(diào)和平均數(shù)而不是幾何平均數(shù)。通過(guò)這么做，我們可以把錯(cuò)誤率降到 1.04/sqrt(m)，同樣不增加需要的空間。當(dāng)然完整的算法要更復(fù)雜一點(diǎn)，因?yàn)樗仨毿拚〉暮痛蟮幕鶖?shù)誤差。有興趣的讀者應(yīng)該，可能你已經(jīng)猜到了，就是去閱讀完整的論文.
并行化

這些方案所共有的整齊性使得它們很容易就能并行化。多臺(tái)機(jī)器可以獨(dú)立地運(yùn)行同樣的哈希函數(shù)同樣數(shù)目的桶。我們?cè)谧詈笾恍枰呀Y(jié)果結(jié)合起來(lái)，取每個(gè)算法實(shí)例中每個(gè)桶最大的值就可以了。這不僅很好實(shí)現(xiàn)，因?yàn)槲覀冏疃嘀恍枰獋鬏敳坏?1kb 的數(shù)據(jù)就可以了，而且和在單臺(tái)機(jī)器上運(yùn)行的結(jié)果是完全一模一樣的.
總結(jié)

就像我們剛剛討論過(guò)的基數(shù)排序算法，使得有可能得到一個(gè)非重復(fù)數(shù)字個(gè)數(shù)的很好的估計(jì)。通常只用不到 1kb 空間。我們可以不依賴數(shù)據(jù)的種類(lèi)而使用它，并且可以分布式地在多臺(tái)機(jī)器上工作，機(jī)器間的協(xié)調(diào)和數(shù)據(jù)的傳輸達(dá)到最小。結(jié)果估計(jì)數(shù)可以用來(lái)做許多事情，比如流量監(jiān)控(多少個(gè)獨(dú)立IP訪問(wèn)過(guò)？)和數(shù)據(jù)庫(kù)查詢優(yōu)化(我們應(yīng)該排序然后歸并呢還是構(gòu)造一個(gè)哈希表呢？)。

最新評(píng)論