上一篇文章介紹的Linear Counting算法相較于直接映射bitmap的方法能大大節(jié)省內(nèi)存（大約只需后者1/10的內(nèi)存），但畢竟只是一個(gè)常系數(shù)級(jí)的降低，空間復(fù)雜度仍然為O(Nmax)O(Nmax)。而本文要介紹的LogLog Counting卻只有O(log2(log2(Nmax)))O(log2(log2(Nmax)))。例如，假設(shè)基數(shù)的上限為1億，原始bitmap方法需要12.5M內(nèi)存，而LogLog Counting只需不到1K內(nèi)存（640字節(jié)）就可以在標(biāo)準(zhǔn)誤差不超過4%的精度下對基數(shù)進(jìn)行估計(jì)，效果可謂十分驚人。

本文將介紹LogLog Counting。

---

簡介

LogLog Counting（以下簡稱LLC）出自論文“Loglog Counting of Large Cardinalities”。LLC的空間復(fù)雜度僅有O(log2(log2(Nmax)))O(log2(log2(Nmax)))，使得通過KB級(jí)內(nèi)存估計(jì)數(shù)億級(jí)別的基數(shù)成為可能，因此目前在處理大數(shù)據(jù)的基數(shù)計(jì)算問題時(shí)，所采用算法基本為LLC或其幾個(gè)變種。下面來具體看一下這個(gè)算法。

基本算法

均勻隨機(jī)化

與LC一樣，在使用LLC之前需要選取一個(gè)哈希函數(shù)H應(yīng)用于所有元素，然后對哈希值進(jìn)行基數(shù)估計(jì)。H必須滿足如下條件（定性的）：

1、H的結(jié)果具有很好的均勻性，也就是說無論原始集合元素的值分布如何，其哈希結(jié)果的值幾乎服從均勻分布（完全服從均勻分布是不可能的，D. Knuth已經(jīng)證明不可能通過一個(gè)哈希函數(shù)將一組不服從均勻分布的數(shù)據(jù)映射為絕對均勻分布，但是很多哈希函數(shù)可以生成幾乎服從均勻分布的結(jié)果，這里我們忽略這種理論上的差異，認(rèn)為哈希結(jié)果就是服從均勻分布）。

2、H的碰撞幾乎可以忽略不計(jì)。也就是說我們認(rèn)為對于不同的原始值，其哈希結(jié)果相同的概率非常小以至于可以忽略不計(jì)。

3、H的哈希結(jié)果是固定長度的。

以上對哈希函數(shù)的要求是隨機(jī)化和后續(xù)概率分析的基礎(chǔ)。后面的分析均認(rèn)為是針對哈希后的均勻分布數(shù)據(jù)進(jìn)行。

思想來源

下面非正式的從直觀角度描述LLC算法的思想來源。

設(shè)a為待估集合（哈希后）中的一個(gè)元素，由上面對H的定義可知，a可以看做一個(gè)長度固定的比特串（也就是a的二進(jìn)制表示），設(shè)H哈希后的結(jié)果長度為L比特，我們將這L個(gè)比特位從左到右分別編號(hào)為1、2、…、L：

又因?yàn)閍是從服從均與分布的樣本空間中隨機(jī)抽取的一個(gè)樣本，因此a每個(gè)比特位服從如下分布且相互獨(dú)立。

下面解釋為什么可以這樣估計(jì)。注意如下事實(shí)：

由于比特串每個(gè)比特都獨(dú)立且服從0-1分布，因此從左到右掃描上述某個(gè)比特串尋找第一個(gè)“1”的過程從統(tǒng)計(jì)學(xué)角度看是一個(gè)伯努利過程，例如，可以等價(jià)看作不斷投擲一個(gè)硬幣（每次投擲正反面概率皆為0.5），直到得到一個(gè)正面的過程。在一次這樣的過程中，投擲一次就得到正面的概率為

分桶平均

上述分析給出了LLC的基本思想，不過如果直接使用上面的單一估計(jì)量進(jìn)行基數(shù)估計(jì)會(huì)由于偶然性而存在較大誤差。因此，LLC采用了分桶平均的思想來消減誤差。具體來說，就是將哈希空間平均分成m份，每份稱之為一個(gè)桶（bucket）。對于每一個(gè)元素，其哈希值的前k比特作為桶編號(hào)，

偏差修正

上述經(jīng)過分桶平均后的估計(jì)量看似已經(jīng)很不錯(cuò)了，不過通過數(shù)學(xué)分析可以知道這并不是基數(shù)n的無偏估計(jì)。因此需要修正成無偏估計(jì)。這部分的具體數(shù)學(xué)分析在“Loglog Counting of Large Cardinalities”中，過程過于艱澀這里不再具體詳述，有興趣的朋友可以參考原論文。這里只簡要提一下分析框架：

首先上文已經(jīng)得出：

誤差分析

不加證明給出如下結(jié)論：

算法應(yīng)用

誤差控制

在應(yīng)用LLC時(shí)，主要需要考慮的是分桶數(shù)m，而這個(gè)m主要取決于誤差。根據(jù)上面的誤差分析，如果要將誤差控制在?之內(nèi)，則：

內(nèi)存使用分析

合并

與LC不同，LLC的合并是以桶為單位而不是bit為單位，由于LLC只需記錄桶的ρmax，因此合并時(shí)取相同桶編號(hào)數(shù)值最大者為合并后此桶的數(shù)值即可。

小結(jié)

本文主要介紹了LogLog Counting算法，相比LC其最大的優(yōu)勢就是內(nèi)存使用極少。不過LLC也有自己的問題，就是當(dāng)n不是特別大時(shí)，其估計(jì)誤差過大，因此目前實(shí)際使用的基數(shù)估計(jì)算法都是基于LLC改進(jìn)的算法，這些改進(jìn)算法通過一定手段抑制原始LLC在n較小時(shí)偏差過大的問題。后面要介紹的HyperLogLog Counting和Adaptive Counting就是這類改進(jìn)算法。

總結(jié)

以上是生活随笔為你收集整理的解读Cardinality Estimation算法（第三部分：LogLog Counting）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。