HyperLogLog 算法原理

2019-10-31 本文已影响0人邵红晓

要想了解HyperLogLog ，必须先要了解伯努利实验

作用：能够使用极少的内存，大数据量亿级数据去重复统计uv
伯努利实验
一次伯努利实验，抛硬币不管进行抛掷次数多少次，只要出现一个正面，就称之为为一次伯努利实验
对于这n次伯努利试验中，必然会有一个最大的抛掷次数k
k_max 表示在所有次伯努利实验中，它是抛掷次数最高的
最终结合极大似然估算的方法，发现在n和k_max中存在估算关联：n = 2^(k_max)
结论：可以通过伯努利实验中最大抛掷次数来估算总伯努利实验次数
比特串
hash(id) = 比特串
不同的用户 id，必然拥有不同的比特串。每一个比特串，也必然会至少出现一次 1 的位置。我们类比每一个比特串为一次伯努利试验
不同的用户 id，必然拥有不同的比特串。每一个比特串，也必然会至少出现一次 1 的位置。我们类比每一个比特串为一次伯努利试验。
现在要分轮，也就是分桶。所以我们可以设定，每个比特串的前多少位转为10进制后，其值就对应于所在桶的标号。假设比特串的低两位用来计算桶下标志，此时有一个用户的id的比特串是：1001011000011。它的所在桶下标为：11(2) = 1*2^1 + 1*2^0 = 3，处于第3个桶，即第3轮中。
上面例子中，计算出桶号后，剩下的比特串是：10010110000，从低位到高位看，第一次出现 1 的位置是 5 。也就是说，此时第3个桶，第3轮的试验中，k_max = 5。5 对应的二进制是：101，又因为每个桶有 p 个比特位。当 p>=3 时，便可以将 101 存进去。
模仿上面的流程，多个不同的用户 id，就被分散到不同的桶中去了，且每个桶有其 k_max。然后当要统计出 mian 页面有多少用户点击量的时候，就是一次估算。最终结合所有桶中的 k_max，代入估算公式，便能得出估算值。
注意：如果入了同一个桶，如何更新桶里的值？取值大的那个
分桶
分桶数组是为了消减因偶然性带来的误差，提高预估的准确性
分桶平均的基本原理是将统计数据划分为m个桶，每个桶分别统计各自的k_max，并能得到各自的基数预估值 n ，最终对这些 n 求平均（调和平均数）得到整体的基数估计值。
DV - 就是要求的基数n
const -是修正因子
m - 表示第几轮次实验：进行一轮次实验，只能得到一个k_max，若进行的伯努利试验次数少，估算不准确，
所以采用多轮次实验，得到多个k_max值，然后根据以下公式进行评估得到相对准确的伯努利试验次数，也就是基数
RJ - 表示调和平均数
以下是调和平均数公式，调和平均数可以减轻大数的影响

image.png

image.png

redis 实现源码

// 密集模式添加元素
int hllDenseAdd(uint8_t *registers, unsigned char *ele, size_t elesize) {
    uint8_t oldcount, count;
    long index;

    // 计算该元素第一个1出现的位置
    count = hllPatLen(ele,elesize,&index);
    // 得到第index个桶内的count值
    HLL_DENSE_GET_REGISTER(oldcount,registers,index);
    if (count > oldcount) {
        // 如果比现有的最大值还大，则添加该值到数据部分
        HLL_DENSE_SET_REGISTER(registers,index,count);
        return 1;
    } else {
        // 如果小于现有的最大值，则不做处理，因为不影响基数
        return 0;
    }
}
// 用于计算hash后的值中，第一个出现1的位置
int hllPatLen(unsigned char *ele, size_t elesize, long *regp) {
    uint64_t hash, bit, index;
    int count;
    // 利用MurmurHash64A哈希函数来计算该元素的hash值
    hash = MurmurHash64A(ele,elesize,0xadc83b19ULL);
    // 计算应该放在哪个桶
    index = hash & HLL_P_MASK;
    // 为了保证循环能够终止
    hash |= ((uint64_t)1<<63); 
    bit = HLL_REGISTERS;
    // 存储第一个1出现的位置
    count = 1;
    // 计算count
    while((hash & bit) == 0) {
        count++;
        bit <<= 1;
    }
    *regp = (int) index;
    return count;
}

感谢这两位位大神
https://juejin.im/post/5c7900bf518825407c7eafd0
http://www.rainybowe.com/blog/2017/07/13/%E7%A5%9E%E5%A5%87%E7%9A%84HyperLogLog%E7%AE%97%E6%B3%95/index.html
http://www.rainybowe.com/blog/2017/07/13/%E7%A5%9E%E5%A5%87%E7%9A%84HyperLogLog%E7%AE%97%E6%B3%95/index.html

HyperLogLog 算法原理

猜你喜欢

热点阅读