HyperLogLog算法如何工作？-Java 学习之路

144

我最近在闲暇时间学习了不同的算法，而我遇到的一个看起来非常有趣的算法称为HyperLogLog算法 - 它估计列表中有多少独特的项目 .

这对我来说特别有意思，因为它让我回到了我的MySQL时代，当我看到“基数”值时（我总是假设它直到最近计算得不是估计的） .

所以我知道如何在O（n）中编写一个算法来计算数组中有多少个唯一项 . 我用JavaScript写了这个：

function countUniqueAlgo1(arr) {
    var Table = {};
    var numUnique = 0;
    var numDataPoints = arr.length;
    for (var j = 0; j < numDataPoints; j++) {
        var val = arr[j];
        if (Table[val] != null) {
            continue;
        }
        Table[val] = 1;
        numUnique++;
    }
    return numUnique;
}

但问题是我的算法，而O（n），使用了大量的内存（在 Table 中存储值） .

我一直在阅读this paper关于如何在O（n）时间内使用最小内存来计算列表中的重复项 .

它解释了通过散列和计数比特或某事物可以在一定概率内（假设列表均匀分布）估计列表中的唯一项目的数量 .

我读过这篇论文，但我似乎无法理解它 . 有人能给出更多非专业人士的解释吗？我知道什么是哈希，但我不明白它们如何在这个HyperLogLog算法中使用 .

3 回答

85

这个算法背后的主要技巧是，如果你观察一个随机整数流，看一个二进制表示以某个已知前缀开始的整数，那么流的基数是2 ^（前缀的大小）的可能性更高 . .

也就是说，在随机的整数流中，约50％的数字（二进制）以“1”开头，25％以“01”开头，12.5％以“001”开头 . 这意味着如果您观察到随机流并看到“001”，则此流的基数为8的可能性更高 .

（前缀“00..1”没有特殊含义 . 只是因为在大多数处理器中很容易找到二进制数中最重要的位）

当然，如果你只观察一个整数，那么这个值错误的可能性很高 . 这就是为什么算法将流划分为“m”个独立子流并保持每个子流的似乎“00 ... 1”前缀的最大长度 . 然后，通过取每个子流的平均值来估计最终值 .

这是该算法的主要思想 . 有一些缺失的细节（例如，低估计值的修正），但这一切都写得很好 . 抱歉可怕的英语 .

回复于 2024-05-04T23:34:35+08:00
131
HyperLogLog是probabilistic data structure . 它计算列表中不同元素的数量 . 但是与直接的方式相比（具有集合并向集合添加元素），它以近似的方式执行此操作 .

在查看HyperLogLog算法如何做到这一点之前，必须先了解为什么需要它 . 直接方式的问题是它消耗了 O(distinct elements) 的空间 . 为什么这里有一个很大的O符号而不仅仅是不同的元素？这是因为元素可以具有不同的大小 . 一个元素可以是 1 另一个元素 "is this big string" . 因此，如果你有一个巨大的列表（或大量的元素流），它将需要大量的内存 .

Probabilistic Counting

如何才能对一些独特元素进行合理估计？假设你有一个长度为 m 的字符串，它由 {0, 1} 组成，概率相等 . 从0开始的概率是多少，有2个零，有k个零？它是 1/2 ， 1/4 和 1/2^k . 这意味着如果您遇到了一个包含 k 零的字符串，那么您已经大致查看了 2^k 个元素 . 所以这是一个很好的起点 . 拥有在 0 和 2^k - 1 之间均匀分布的元素列表，您可以计算二进制表示中最大的零前缀的最大数量，这将为您提供合理的估计 .

问题是，从 0 t 2^k-1 获得均匀分布的数字的假设太难实现（我们遇到的数据通常不是数字，几乎从不均匀分布，并且可以在任何值之间 . 但是使用good hashing function你可以假设输出位将均匀分布，大多数散列函数的输出介于 0 和 2^k - 1 之间（SHA1给出 0 和 2^160 之间的值） . 所以我们到目前为止所获得的是我们可以估计具有最大基数的唯一元素的数量 . k 位只存储一个大小的 log(k) 位 . 缺点是我们的估计差异很大 . 我们几乎创造了一个很酷的东西_纸张（估计有点聪明，但我们仍然很接近） .

LogLog

在进一步讨论之前，我们必须理解为什么我们的第一次估计并不那么好 . 其背后的原因是随机出现的高频0前缀元素会破坏一切 . 改进它的一种方法是使用许多散列函数，对每个散列函数计数max，最后将它们平均 . 这是一个很好的主意改进估计，但LogLog paper采用了略微不同的方法（可能是因为散列有点贵） .

他们使用了一个哈希，但将其分为两部分 . 一个被称为桶（桶的总数是 2^x ）而另一个 - 基本上与我们的哈希相同 . 我很难得到正在发生的事情，所以我将举一个例子 . 假设你有两个元素和你的哈希函数，它给出了 0 到 2^10 的值，产生了2个值： 344 和 387 . 你决定有16个水桶 . 所以你有了：
```
0101 011000  bucket 5 will store 1
0110 000011  bucket 6 will store 4
```
通过使用更多桶，可以减少方差（使用稍多的空间，但它仍然很小） . 使用数学技能，他们能够量化错误（即 1.3/sqrt(number of buckets) ） .

HyperLogLog

HyperLogLog没有引入任何新的想法，但主要是使用大量的数学来改进以前的估计 . 研究人员发现，如果从桶中删除30％的最大数字，则可以显着提高估算值 . 他们还使用另一种算法来平均数字 . 这篇论文很重要 .

我想完成最近的一篇论文，其中显示了improved version of hyperLogLog algorithm（到目前为止，我没有时间完全理解它，但也许以后我会改进这个答案） .
回复于 2024-05-04T23:34:35+08:00
18

直觉是如果你的输入是一组大的随机数（例如散列值），它们应该在一个范围内均匀分布 . 假设范围最多为10位，表示最大值为1024.然后观察最小值 . 假设它是10.然后基数估计约为100（10×100×1024） .

当然，阅读论文的真实逻辑 .

可以在此处找到示例代码的另一个很好的解释：
Damn Cool Algorithms: Cardinality Estimation - Nick's Blog

回复于 2024-05-04T23:34:35+08:00

HyperLogLog算法如何工作？

3 回答

相关问题