大數(shù)據(jù)計數(shù)原理1+0=1這你都不會算(六)
照例甩一波鏈接。
大數(shù)據(jù)計數(shù)原理1+0=1這你都不會算(一)
大數(shù)據(jù)計數(shù)原理1+0=1這你都不會算(二)
大數(shù)據(jù)計數(shù)原理1+0=1這你都不會算(三)
大數(shù)據(jù)計數(shù)原理1+0=1這你都不會算(四)
大數(shù)據(jù)計數(shù)原理1+0=1這你都不會算(五)
今天開始進入一個全新的領(lǐng)域，嗯，叫基數(shù)估計。
什么叫基數(shù)估計呢?
基數(shù)是指一個一大堆值集合中，不同的值的個數(shù)。
我們之前講的，都是精確的統(tǒng)計，有一說一有二說二，直接去重統(tǒng)計就可以了。
基數(shù)估計，故名思議，估計，意思就是使用概率論的思想，用更低空間更低時間的成本，以一個很低很低的誤差率來估計數(shù)據(jù)的基數(shù)。
能不能說說人話呢?
好好好，你長得好看說什么都對。
加入一個集合長這樣
{大蕉，小蕉，小蕉，大大蕉，小蕉}
統(tǒng)計思想會這樣說。
啊大蕉，嗯，1個。
小蕉，沒出現(xiàn)過，嗯，2個。
小蕉，出現(xiàn)過了，嗯，2個。
大大蕉，沒出現(xiàn)過，嗯，3個。
小蕉，出現(xiàn)過了，嗯，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.
意思就是，啊傳統(tǒng)的精確統(tǒng)計至少要O(q log q)這么死鬼多時間，我們只需要O(q) ，你不覺得很厲害嗎?然后我們是用 Hash 實現(xiàn)的，嗯，可牛逼了。
怎么做的呢?
我們先創(chuàng)建一個長度為m的數(shù)組，每一個bit都設(shè)置為0，然后搞個Hash算法把這些值的位置所對應(yīng)的0改為1。
比如字符串 “小蕉寫得這么給力你不點個贊嗎”，經(jīng)過 Hash 算法1、Hash 算法2、Hash 算法3，生成了數(shù)字，1、11、21。
這時候又來了一個字符串 “小蕉寫得這么給力你不點個贊”，經(jīng)過 Hash 算法1、Hash 算..
你等等等等等，這不是BitMap嗎?你特么在說啥。
年輕人不要太著急嘛。
我急!這輩子就現(xiàn)在!最!急!
好好好我來了我來了。上面這個數(shù)組比BitMap所需要的數(shù)組小很多很多很多。然后我們假設(shè)最終有u個位置還是0。我們給出一個極大似然估計，估計一下n的估計(下面這個是極大似然估計)就長這樣。
好了我要睡覺了，拜拜。
至于詳細的數(shù)學(xué)推導(dǎo)及誤差分析推導(dǎo)，且聽下回分...
【本文為51CTO專欄作者“大蕉”的原創(chuàng)稿件，轉(zhuǎn)載請通過作者微信公眾號“一名叫大蕉的程序員”獲取授權(quán)】
