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

在你繼續(xù)讀下去之前，我會引導(dǎo)你思考很多，因為今天我們要討論的算法雖然很簡單，但極具創(chuàng)意，它不是這么容易就能想出來的。
一個簡單的樸素基數(shù)估計器

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

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

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

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

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

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

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

附注：Flajolet-Martin 原先的論文在這里繼續(xù)討論了一種基于 bitmap 的過程來獲得一個更精確的估計。我不會討論這個細(xì)節(jié)因為它馬上就會在隨后的方法中得到改進(jìn)。更多細(xì)節(jié)對于有興趣的讀者可以閱讀原論文。

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

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

把我們目前學(xué)到的應(yīng)用一下，這里有一個簡單的實現(xiàn)。這和 Durand-Flajolet 的論文中的算法是等價的，為了實現(xiàn)方便和清晰所以我計算的是尾部的 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

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

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

讓我們在一些隨機(jī)的數(shù)據(jù)上測試一下它:
 

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

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

最后，F(xiàn)lajolet et al 的論文的貢獻(xiàn)就是使用了一個不同類型的平均數(shù)。使用調(diào)和平均數(shù)而不是幾何平均數(shù)。通過這么做，我們可以把錯誤率降到 1.04/sqrt(m)，同樣不增加需要的空間。當(dāng)然完整的算法要更復(fù)雜一點，因為它必須修正小的和大的基數(shù)誤差。有興趣的讀者應(yīng)該，可能你已經(jīng)猜到了，就是去閱讀完整的論文.
并行化

這些方案所共有的整齊性使得它們很容易就能并行化。多臺機(jī)器可以獨(dú)立地運(yùn)行同樣的哈希函數(shù)同樣數(shù)目的桶。我們在最后只需要把結(jié)果結(jié)合起來，取每個算法實例中每個桶最大的值就可以了。這不僅很好實現(xiàn)，因為我們最多只需要傳輸不到 1kb 的數(shù)據(jù)就可以了，而且和在單臺機(jī)器上運(yùn)行的結(jié)果是完全一模一樣的.
總結(jié)

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

最新評論