大数据计数原理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 算法改进成无偏估计，改进完的算法误差率究竟在什么样的范围。棒~~掰掰