HyperLogLog算法是如何工作的？

Question

我最近在业余时间学习了不同的算法，我遇到的一个看起来非常有趣的算法叫做超级日志算法——它估计一个列表中有多少独特的项目。

这对我来说特别有趣，因为它让我回到了我的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），但使用了大量内存（将值存储在表中）。

我一直在读这篇关于如何在O（n）时间内使用最小内存计算列表中的重复项的文章。

它解释说，通过散列和计数位或某种方法，人们可以在一定概率内（假设列表是均匀分布的）估计列表中唯一项的数量。

我读过报纸，但似乎不明白。有人能给一个更外行的解释吗？我知道散列是什么，但我不明白在这个HyperLogLog算法中它们是如何使用的。




Answer 1

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

阅读这篇论文，了解真正的逻辑。

另一个很好的示例代码解释可以在这里找到：
该死的酷算法：基数估计-Nick的博客

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之间，您可以计算二进制表示中最大前缀零的最大数量，这将为您提供一个合理的估计。

问题在于，从0t2^k-1中均匀分布数字的假设太难实现（我们遇到的数据大多不是数字，几乎从不均匀分布，可以在任何值之间。但是使用一个好的哈希函数，您可以假设输出位将均匀分布，并且大多数哈希函数的输出介于0和2^k-1（SHA1为您提供介于0和2^160）之间的值。因此，到目前为止，我们所取得的成果是，我们可以通过仅存储一个大小log（k）来估计最大基数为k位的唯一元素的数量bits。缺点是我们的估计值存在巨大差异。我们几乎创造了1984年的概率计数纸，这是一件很酷的事情（估计值稍微聪明一点，但我们仍然很接近）。

日志

在进一步研究之前，我们必须理解为什么我们的第一个估计值没有那么高。其背后的原因是，一次随机出现的高频0前缀元素可能会破坏一切。一种改进的方法是使用许多散列函数，计算每个散列函数的最大值，最后求出它们的平均值。这是一个很好的想法，它将改进估计，但是日志文件使用了稍微不同的方法（可能是因为哈希有点昂贵）。

他们使用一个散列，但把它分成两部分。一个叫做桶（桶的总数是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没有引入任何新的想法，但主要使用大量数学来改进先前的估计。研究人员发现，如果你把桶中最大数字的30%去掉，你就能显著提高估计值。他们还使用了另一种算法来平均数字。这篇论文数学性很强。

我想以最近的一篇论文结束，这篇论文展示了hyperLogLog算法的改进版本（到目前为止，我还没有时间完全理解它，但也许稍后我会改进这个答案）。

Answer 3

此算法背后的主要技巧是，如果您观察一个随机整数流，看到一个二进制表示以某个已知前缀开头的整数，则该流的基数为2^（前缀大小）的可能性更高。

也就是说，在一个随机的整数流中，大约50%的数字（二进制）以“1”开头，25%以“01”开头，12,5%以“001”开头。这意味着，如果您观察一个随机流并看到一个“001”，则该流的基数为8的可能性更高。

（前缀“00..1”没有特殊含义。它之所以存在，是因为在大多数处理器中，在二进制数中很容易找到最高有效位）

当然，如果只观察一个整数，则该值出错的几率很高。这就是为什么该算法将流划分为“m”个独立的子流，并保持每个子流的“00…1”前缀的最大长度。然后，通过取每个子流的平均值来估计最终值。

这就是这个算法的主要思想。有一些细节缺失（例如，对低估计值的修正），但在论文中都写得很好。对不起，英语太糟糕了。