HyperLogLog概率统计

由于使用了概率统计，我们必须首先谈谈收益。我们都喜欢丰厚的回报。

先来看一下比较高级的 bitmap。

bitmap 通过位数据存储特定数据的数据结构。每个位的位置可以独立地包含信息，位数据的最小存储单元，因此可以节省很多空间，并且整个位数据也可以加载到内存计算中。

比如：

每一位使用0或1表示是否包含它。

多个统计结果可以轻松合并，只需要对多个结果进行XOR，也可以大大减少存储空间。

即使这样，内存使用率仍然很高，有些我们必须计算10亿条数据。1000000000/8/1024/1024 ≈ 120 M ，如果有1,000个对象，则最多需要 120 000 M money（内存）。

接下来我们看一下 HyperLogLog：

由于它是通过简单的抛硬币实验指导的，因此我们首先来看一下抛硬币的过程。

第一次抛硬币，抛了1次，就出现正面。

$k_1$=1,n=1
第一次伯努利过程。

第二次抛硬币，抛了3次，就出现正面。

$k_2$=3,n=2
第二次伯努利过程。

第三次抛硬币，抛了6次，就出现正面。

$k_3$=6,n=3
第三次伯努利过程。

第n次抛硬币，抛了12次，就出现正面。

$k_n$=12
第n次伯努利过程。
我们可以估计 n=2^12

可以发现此时的误差很大，下面让我们减少误差。

以下是摘自 HyperLogLog: the analysis of a near-optimal
cardinality estimation algorithm的公式

基本步骤：

1. 获取值。
2. 将获取的值转为hash值。
3. 把hash值转为二进制数。
4. 创建m个桶，并初始化桶的值。
5. 二进制数末尾取s位作为索引值.
6. 剩余数从低位到高位寻找第一个1出现位置j。
7. 在j桶的位置放入转化为十进制s位的索引值（如果比原有的值小，则保留原有的最大值）。
8. 取每个桶的调和平均值。
9. 求出基数值。

假设我们有一个值：14,262,337

转化为hash值为：3,838,145,797

转化为二进制数为：1110 0100 1100 0101 0111 0101 0000 0101（是不是和抛硬币正反面差不多）

创建64个桶并初始化：m=64

将后6位作为索引值：000101（十进制：5）

在剩余数从低位到高位找出第一个1出现的位置。

在第5个桶放入3。

如果此时第5个桶内已经包含6，3<6，则第5个桶内的值不做改变，依旧为6.

取调和平均值：将所有数值取倒数并求其算术平均数后，再将此算术平均数取倒数而得，其结果等于数值的个数除以数值倒数的总和。

比如：$x_1$=3; $x_2$=6; n=2;

则：

求基数值：

其中：

我们使用了64个桶，所以我们这里使用 0.709.

带入公式，偏差依旧很大。我们需要对数据进行微调。

摘自HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm。

将 E 值进行调整，情况分成三种：

• 小范围
• 中等范围
• 大范围

当 E $\le$ 5m/2:

使用：

中等范围：

值不变

大范围：