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

照例甩一波鏈接。

大數據計數原理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個。

小蕉，沒出現過，嗯，2個。

小蕉，出現過了，嗯，2個。

大大蕉，沒出現過，嗯，3個。

小蕉，出現過了，嗯，3個。

概率論思想會這樣說。

我夜觀天象，掐指一算，公子是個喜脈。

呸呸呸。掐值一算，有99%的概率是3個。

但是又有小夥伴開始說了，我特么把手都快掐出血了，也不知道你吖是怎麼估算的。

年輕人不要太著急嘛。

我們今天幾乎所有演算法的啟蒙。Linear Counting（LC）

來自於1900年一個叫 KY · Whang 的大濕的一篇名叫《A linear-time probabilistic counting algorithm for database applications》的論文。

This algorithm has O(q) time complexity, where q is the number of values including duplicates, and produces an estimation with an arbitrary accuracy prespecified by the user using only a small amount of space. Traditionally, accurate counts of unique values were obtained by sorting, which has O(q log q) time complexity. Our technique, called linear counting, is based on hashing.

意思就是，啊傳統的精確統計至少要O(q log q)這麼死鬼多時間，我們只需要O(q) ，你不覺得很厲害嗎？然後我們是用 Hash 實現的，嗯，可牛逼了。

怎麼做的呢？

我們先創建一個長度為m的數組，每一個bit都設置為0，然後搞個Hash演算法把這些值的位置所對應的0改為1。

比如字元串 「小蕉寫得這麼給力你不點個贊嗎」，經過 Hash 演算法1、Hash 演算法2、Hash 演算法3，生成了數字，1、11、21。

這時候又來了一個字元串 「小蕉寫得這麼給力你不點個贊」，經過 Hash 演算法1、Hash 算..

你等等等等等，這不是BitMap嗎？你特么在說啥。

年輕人不要太著急嘛。

我急！這輩子就現在！最！急！

好好好我來了我來了。上面這個數組比BitMap所需要的數組小很多很多很多。然後我們假設最終有u個位置還是0。我們給出一個極大似然估計，估計一下n的估計（下面這個是極大似然估計）就長這樣。

好了我要睡覺了，拜拜。

至於詳細的數學推導及誤差分析推導，且聽下回分...

推薦閱讀：