HyperLogLog算法是如何工作的？

Question

最近我在空闲时间学习不同的算法，其中一个我发现非常有趣的算法是称为HyperLogLog算法，它可以估算列表中有多少个唯一项。

这对我来说特别有趣，因为它让我想起了我使用MySQL时看到的“Cardinality”值（直到最近我总是认为它是计算而非估算）。

因此，我知道如何编写时间复杂度为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中）。

我一直在阅读这篇关于如何在O(n)的时间内且使用最小内存计数列表中重复项的论文。

它解释说，通过哈希和计数位或其他方法，可以估计一个列表中独特项的数量。假设该列表均匀分布，则可以在一定概率内实现估计。

我已经阅读了这篇论文，但似乎无法理解它。能否有人给出更通俗易懂的解释？我知道哈希是什么，但我不明白它们如何在这个HyperLogLog算法中使用。

- K2xL

---

这篇论文 (http://research.google.com/pubs/pub40671.html) 总结了HyperLogLog算法以及一些改进。我认为它比原始论文更易于理解。 - zhanxw

命名上的一点提示：有些人用“set”这个词来描述一个由独特项组成的集合。对于这些人来说，如果你使用术语“list”或“array”，你的问题可能会更加清晰易懂。 - Paddy3118

Answer 1

这个算法的主要技巧是，如果你在观察一串随机整数时，发现一个整数的二进制表示以某个已知前缀开头，那么这串整数流的基数是2^(前缀的长度)的概率较高。

也就是说，在一串随机整数流中，大约50%的数字（以二进制表示）以"1"开头，25%以"01"开头，12.5%以"001"开头。这意味着，如果你观察到一个随机整数流以"001"开头，那么这个流的基数很可能是8。

（前缀"00..1"没有特殊含义。之所以使用这个前缀，只是因为在大多数处理器中，很容易找到二进制数的最高有效位）

当然，如果你只观察一个整数流，这个值错误的可能性很高。这就是为什么该算法将整数流分成"m"个独立的子流，并保留每个子流中已观察到的"00...1"前缀的最大长度。然后，通过计算所有子流的平均值来估计最终值。

这就是该算法的主要思想。还有一些细节需要补充（例如对估计值较低的修正），但这些都在论文中有详细说明。对于糟糕的英语表示抱歉。

- Juan Lopes

---

这个流的基数很可能是8。请问为什么000表示预期的试验次数是2^3？我尝试计算试验次数的数学期望，假设我们至少有一个连续出现3个零的情况，并且没有连续出现4个零的情况... - yura

在阅读这篇文章之前我不是很理解，现在有了这份翻译后，我终于明白了。 - josiah

@yura，我知道这是一个非常旧的评论，但它可能对其他人有用。他说：“也就是说，在一系列随机整数中，(...)12.5% 以“001”开头。” 可能的基数为8，因为12.5%代表整个流的八分之一。 - braunmagrin

这是我读过的关于HLL的最好/必要的解释。 - xgwang

请问能否解释一下，基数如何取决于前缀长度？我可以任意选择数字的比特位数吗？我可以拥有一个 uint16 数字流，但也可以将相同的数字流转换为 uint64 整数流，这种情况下，前缀长度会大幅增加，但基数显然不会改变。 - DimanNe

@DimanNe 注意，我们正在讨论一个随机数字流，通常是通过将哈希函数应用于原始流产生的，虽然不严格随机，但足够好的近似值。在这种情况下，我们假设每个位有50%的机会成为0或1，因此使用uint16或uint64不应对前缀长度的期望值产生太大影响（还假设expected cardinality << 2^(bit length)）。 - Juan Lopes

Answer 2

一个HyperLogLog是一种概率数据结构。它可以计算列表中不同元素的数量。但与直接创建一个集合并将元素添加到集合的简单方法相比，它以近似方式完成此操作。

在了解HyperLogLog算法如何执行此操作之前，必须先了解为什么需要它。直接创建集合的问题在于它消耗O(不同元素)的空间。为什么这里有大O符号而不只是不同元素？这是因为元素的大小可能不同。一个元素可以是1，另一个元素可以是"这是一个很长的字符串"。因此，如果您有一个巨大的列表（或一系列大量元素），它将占用大量内存。

---

概率计数

如何合理地估计独特元素的数量？假设您有一个长度为m的字符串，由等概率的{0,1}组成。它以0开始，以2个0开始，以k个0开始的概率分别是1/2，1/4和1/2^k。这意味着如果您遇到以k个零开头的字符串，则已经大致查看了2^k个元素。因此，这是一个很好的起点。拥有在0和2^k-1之间均匀分布的元素列表，您可以计算二进制表示中最大前缀的零的最大数量，这将给您一个合理的估计。

问题在于假设从0到2^k-1的数字是均匀分布的，这太难实现了（我们遇到的数据大多不是数字，几乎从不均匀分布，并且可以在任何值之间。但使用好的哈希函数，您可以假设输出位是均匀分布的，大多数哈希函数的输出在0和2^k-1之间（SHA1给出的值在0和2^160之间）。到目前为止，我们已经实现了通过仅存储一个大小为log(k)位的数字来估计具有最大基数为k位的唯一元素数量。缺点是我们的估计存在巨大的差异。一个很酷的事情是我们几乎创造了1984年的概率计数论文（它对估计有点聪明，但仍然很接近）。

LogLog

在进一步讨论之前，我们需要了解为什么我们的第一个估计并不那么好。其原因是一个高频率的 0 前缀元素的随机出现可能会破坏一切。改进的方法之一是使用多个哈希函数，对每个哈希函数进行最大计数，最后将它们平均。这是一个很好的想法，可以提高估计的准确性，但是 LogLog 论文 采用了略微不同的方法（可能是因为哈希有点昂贵）。

他们只使用了一个哈希函数，但将其分成两部分。一部分称为桶（桶的总数为2^x），另一部分基本上与我们的哈希函数相同。我很难理解正在发生什么，所以我将举个例子。假设您有两个元素和一个哈希函数，它产生从0到2^10的值，生成了两个值：344和387。您决定有16个桶。所以你有：

0101 011000  bucket 5 will store 1
0110 000011  bucket 6 will store 4

通过增加更多的桶，您可以减少方差（您使用的空间略微增加，但仍然很小）。使用数学技巧，他们能够量化误差（即1.3 / sqrt(桶的数量)）。

HyperLogLog

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

---

我想以一篇最近的论文结束，展示了一个改进版的HyperLogLog算法（直到现在我还没有完全理解它，但也许以后我会改进这个答案）。

- Salvador Dali

---

我理论上假设 k个零 不是一个特殊的事情。你可以寻找 k个一，逻辑是相同的，或者甚至寻找 {0,1} 的 k长度 字符串，但选择其中一个字符串并坚持使用它会更好吗？因为在这种二进制字符串的情况下，它们都有相等的概率 1/2^k。 - user881300

HyperLogLog不会删除最大数值的30％。这是超级对数日志算法的思想，该算法也在LogLog论文中描述。 HyperLogLog算法的主要思想是使用调和平均数对二的幂进行平均，而不是像SuperLogLog和LogLog一样使用几何平均数。 - otmar

Answer 3

直觉是，如果你的输入是一组大量的随机数（例如哈希值），那么它们应该均匀地分布在一个范围内。假设这个范围是10位，用来表示最大值为1024的数。然后观察最小值。假设最小值是10。那么基数的估计值将约为100（10 × 100 ≈ 1024）。

当然，阅读论文可以了解真正的逻辑。

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

- Wai Yip Tung

---

感谢提供那篇酷炫算法博客文章的链接，我已经点赞了。它真的帮助我掌握了这个算法。 - Igor Serebryany