大數據計數原理1+0=1這你都不會算(九)No.64

大數據計數原理1+0=1這你都不會算(一)No.47 <- HashSet

大數據計數原理1+0=1這你都不會算(二)No.50 <- BitMap

大數據計數原理1+0=1這你都不會算(三)No.51 <- BloomFilter

大數據計數原理1+0=1這你都不會算(四)No.52 <- B-Tree

大數據計數原理1+0=1這你都不會算(五)No.55 <- B+Tree

大數據計數原理1+0=1這你都不會算(六)No.57 <- LinearCounting（一）

大數據計數原理1+0=1這你都不會算(七)No.59 <- LinearCounting（二）

大數據計數原理1+0=1這你都不會算(八)No.60 <- RoaringBitMaps

啦啦啦~有小夥伴說我最近怎麼不更新，其實最近真的很忙，而且有很多新的東西要去學，連論文都只能抽時間看。今天這個演算法說實話很難理解，但是確實是一個很好很好巨好的基數估計演算法。叫做LogLogCounting，出自論文《Loglog Counting of Large Cardinalities》，人稱LLC。

這麼舉例子吧，跟你聊聊這個演算法有多節省內存。假如我們有1億數據基數，使用HashSet可能需要2G內存，使用BitMap需要大概12.5M，使用LinearCounting需要1.25M，使用LLC只需要640位元組，連1K都不需要。

我們都知道，基數統計的前提就是hash函數要足夠好。什麼叫足夠好？分布均勻、長度一致、碰撞可忽略。怎麼取？主流加密演算法基本都可以。

好了牛逼吹完了，想了解到這個程度的可以左上角退出了嗷。下面是嚴肅的數學時間，我盡量講得不那麼數學。

首先，這個演算法的第一要義是什麼？靠猜。

比如我們Hash完的串為0100，1000，0010。等，我們發現這些串第一個1出現的位置在第3位上（按1、2、3、4這樣從左往右數），那我們就猜，總共有2^3這麼多個數。主要演算法思路就是上面這樣，取第一個1出現的位置，然後靠猜。

那麼問題來了，我們為什麼可以這樣猜呢？這就需要概率論的知識了。

我們假設字元串"Banana"（簡稱為B），通過hash之後得到了一大堆的01的比特串，因為我們的hash演算法非常好，所以每一個bit位為0和為1的概率就是五五開，都是50%這樣。

那我們就把他當成是薛定諤的貓了，我完全不知道這個bit位有沒有貓，只有謎底揭曉的時候才知道。我們把所有裝著盒子的貓一字排排開，從頭開始找。第一個盒子找不到貓（標記bit位為0）的概率為1/2，第二個盒子就找到貓的概率為1/(2^2)，第k個盒子就找到貓的概率為1/(2^k)。

好，接下來假設我們總共要找n次，也就是有n個B進行hash。

考慮第一個問題。第一個B進行Hash後，在第k個位置第一次找到貓的概率為1-1/(2^k)，那麼明顯，進行n次的結果後，所有的尋找次數加起來，都最多在第k個位置第一次找到貓的概率P( X <= k )= (1-1/(2^k))^n。當n遠大於2^k的時候，P( X <= k )的概率幾乎為0，好了我們找到了一個上限。

接下來我們考慮第二個問題。那麼如果考慮每一次的結果都大於k呢？概率P( X >= k) = 1 - (1-1/(2^k))^n。由極限定理可以得到，當n遠小於2^k的時候，P( X >= k )的概率幾乎為0。

那麼我們就得到說，無論是n遠大於2^k 時，P的概率很小。無論是n遠小於2^k 時，P的概率也很小。那既然這樣，我們就直接拍腦袋取2^k了嘛。

所以LLC的基本思想就是。我們先拍一個大概的數據範圍，也就是統計的上限，比如你的數據量是大概1億，1百億還是1千億，這樣拍一個，然後選hash演算法均勻分配到他們身上。意思就是，如果我們的基數是1千億，那麼我們致至少要有足夠多的bit位空間來保存這上限也就是一千億。在實際進行統計的時候，我們進行n次hash之後，如果第一個找到1的位置是k，那麼就可以估計這個基數是2^k。

基礎演算法到這裡就說完了，我們也說了，我們是靠猜的，那能不能猜得靠譜些？

可以。

我猜幾十次幾百次取平均，應該大概或許能降低這個誤差吧？這就有了分桶的思想，我們只需要每個桶記住自己桶的位置以及桶裡邊最大的k值，就可以了。

我們假設分桶樹為16，也就是2^4。那我們就取hash值的前四個bit來進行分桶，把每個桶的max保留起來即可。為什麼可以這樣保留？因為我們把它界定在某一個桶之後，那它的第一個1肯定是在桶內的，這時候我們就可以對比一下當前桶內的max值，進行合併。然後最終的時候，直接取一下所有桶值得平均即可。

主線就這樣說完了，先消化一下，下一次我們繼續聊聊，如何降低誤差，如何把LogLogCounting 演算法改進成無偏估計，改進完的演算法誤差率究竟在什麼樣的範圍。棒~~掰掰