HyperLogLog算法Java实现

860

HyperLogLog（HLL）算法经常在数据库中被用来统计某一字段的基数即Distinct Value（DV），可以使用固定大小的字节计算任意大小的DV。基数就是指一个集合中不同值的数目，比如[1,2,3,8]的基数就是4，[1,2,3,8,2]的基数还是4，因为2重复了。实际场景中，HLL常用于统计网站或者APP的UV。

Maven

<dependency>
        <groupId>net.agkn</groupId>
        <artifactId>hll</artifactId>
        <version>1.6.0</version>
</dependency>

@Test
    public void testSimpleUse(){
        final int seed = 123456;
        HashFunction hash = Hashing.murmur3_128(seed);
        // data on which to calculate distinct count
        final Integer[] data = new Integer[]{1, 1, 2, 3, 4, 5, 6, 6,
                6, 7, 7, 7, 7, 8, 10};
        final HLL hll = new HLL(13, 5); //number of bucket and bits per bucket
        for (int item : data) {
            final long value = hash.newHasher().putInt(item).hash().asLong();
            hll.addRaw(value);
        }
        System.out.println("Distinct count="+ hll.cardinality());
}

HLL原理来自硬币投掷，这个要从伯努利试验说起，伯努利实验说的是抛硬币的事情。一次伯努利实验相当于抛硬币，不管抛多少次只要出现一个正面，就称为一次伯努利实验。

设想成一次不断投硬币的过程，非正面即反面（每一面的概率为0.5）。在这个过程中，投掷次数大于k的概率是0.5^k（连续投掷出k个反面），在一次过程中，投掷次数小于k的概率是(1-0.5)^k。因此，在n次投掷过程中，投掷次数均小于k的概率是 P(x<=k)=(1–0.5^k)^n，P(x>=k)=1–(1–0.5^k)^n。从以上公式，可以看出，当n<=k)的概率，接近为0。而当n>>k时，P(x<=k)的概率接近为0。所以，当n>>k时，没有一次投掷次数大于k的概率几乎为0。将一次过程，理解成一个比特子串，反面为0，正面为1，投掷次数k对应第一个1出现的位置，当统计子串足够多时，其最大的第一个1的位置为j，那么当n>>2^j时，P(x<=k)接近为0，当n<<2^j时，P(x>=0)也趋向为0。也就是说，在得到x=k的前提下，我们可以认为n=2^j。再通俗点说明：假设我们为一个数据集合生成一个8位的哈希串，那么我们得到00000111的概率是很低的，也就是说，我们生成大量连续的0的概率是很低的。生成连续5个0的概率是1/32，那么我们得到这个串时，可以估算，这个数据集的基数是32。当试验次数很小的时候，这种估算方法的误差会很大，为了解决这个问题 HLL 引入了分桶算法和调和平均数来使这个算法更接近真实情况。分桶算法是指把原来的数据平均分为 m 份，在每段中求平均数在乘以 m，以此来消减因偶然性带来的误差，提高预估的准确性，简单来说就是把一份数据分为多份，把一轮计算，分为多轮计算。而调和平均数指的是使用平均数的优化算法，而非直接使用平均数。综合以上情况，在 Redis 中使用 HLL 插入数据，相当于把存储的值经过 hash 之后，再将 hash 值转换为二进制，存入到不同的桶中，这样就可以用很小的空间存储很多的数据，统计时再去相应的位置进行对比很快就能得出结论，这就是 HLL 算法的基本原理，想要更深入的了解算法及其推理过程，可以去看HLL原版论文。

HLL用于高性能的基数（去重）统计功能，它的缺点就是存在极低的误差率。HLL 具有以下几个特点：能够使用极少的内存来统计巨量的数据，它只需要 12K 空间就能统计 2^64 的数据；统计存在一定的误差，误差率整体较低，标准误差为 0.81%；误差可以被设置辅助计算因子进行降低。

以Redis中HyperLogLog为例，HLL基础命令有3个，分别是：

1、添加元素 pfadd key “x1” “x2″，相关语法是

pfadd key element [element ...]

此命令支持添加一个或多个元素至 HLL 结构中。

2、统计不重复的元素个数pfcount key，相关语法是

pfcount key [key ...]

此命令支持统计一个或多个 HLL 结构。

3、合并一个或者多个HLL至新结构，相关语法是

pfmerge destkey sourcekey [sourcekey ...]

当我们需要合并两个或多个同类页面的访问数据时，可以使用 pfmerge 来操作。

接下来使用 Java 代码来实现 HLL 的三个基础功能，代码如下：

import redis.clients.jedis.Jedis;

public class HyperLogLogExample {
    public static void main(String[] args) {
        Jedis jedis = new Jedis("127.0.0.1", 6379);
        // 添加元素
        jedis.pfadd("k", "redis", "sql");
        jedis.pfadd("k", "redis");
        // 统计元素
        long count = jedis.pfcount("k");
        // 打印统计元素
        System.out.println("k：" + count);
        // 合并 HLL
        jedis.pfmerge("k2", "k");
        // 打印新 HLL
        System.out.println("k2：" + jedis.pfcount("k2"));
    }
}

执行结果是：

k：2
k2：2

评分

欢迎为Ta评分

HyperLogLog算法Java实现

Java专区