196

我最近在业余时间学习了不同的算法，我遇到的一个看起来很有趣的算法叫做 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）。

我一直在阅读这篇论文，了解如何在O ( n ) 时间内计算列表中的重复项并使用最少的内存。

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

我已经阅读了论文，但我似乎无法理解它。谁能给一个更外行的解释？我知道哈希是什么，但我不明白它们是如何在这个 HyperLogLog 算法中使用的。

4

3 回答 3

182

这个算法背后的主要技巧是，如果你观察一个随机整数流，看到一个二进制表示以某个已知前缀开头的整数，那么流的基数很有可能是 2^(前缀的大小) .

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

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

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

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

于 2012-10-04T19:19:54.930 回答
127

HyperLogLog 是一种概率数据结构。它计算列表中不同元素的数量。但与直接的方式（拥有一个集合并向集合中添加元素）相比，它以一种近似的方式执行此操作。

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

概率计数

怎样才能对许多独特的元素进行合理的估计？假设您有一个长度为 的字符串m，由{0, 1}等概率组成。它以 0、2 个零、k 个零开始的概率是多少？它是1/2和。这意味着，如果您遇到一个带有零的字符串，您已经大致浏览了元素。所以这是一个很好的起点。拥有一个均匀分布的元素列表，您可以计算二进制表示中最大零前缀的最大数量，这将为您提供合理的估计。1/41/2^kk2^k02^k - 1

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

日志日志

在进一步进行之前，我们必须了解为什么我们的第一个估计不是那么好。其背后的原因是高频 0 前缀元素的随机出现会破坏一切。改进它的一种方法是使用许多散列函数，为每个散列函数计算最大值，最后将它们平均。这是一个绝妙的想法，可以改进估计，但LogLog 论文使用了一种略有不同的方法（可能是因为散列有点昂贵）。

他们使用一个哈希，但将其分为两部分。一个叫桶（桶的总数是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没有引入任何新的想法，但大多使用大量的数学来改进之前的估计。研究人员发现，如果你从桶中删除 30% 的最大数字，你会显着提高估计值。他们还使用了另一种算法来平均数字。这篇论文数学很重。

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

于 2016-02-05T08:42:59.317 回答
26

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

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

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

于 2012-09-11T17:45:37.737 回答