美文网首页
HyperLogLog 算法原理

HyperLogLog 算法原理

作者: 邵红晓 | 来源:发表于2019-10-31 20:59 被阅读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 算法原理

          本文链接:https://www.haomeiwen.com/subject/gkitbctx.html