如何在HyperLogLog算法的工作？(How does the HyperLogLog algo

我一直在学习在我的业余时间不同的算法，最近，和一个我碰到这似乎是很有趣的被称为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算法中使用。

Answer 1:

该算法背后的主要伎俩是，如果你观察随机整数流，看哪个二进制表示有一些已知的前缀开头的整数，有较高的机会，流的基数是2 ^（前缀的大小）。

即，在整数的随机流，〜的数字（二进制）的50％以“1”开始，25％与“01”开始，12.5％以“001”开头。这意味着，如果你观察一个随机流，并看到一个“001”，有较高的机会，这个流具有8基数。

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

当然，如果你观察到只有一个整数，这个值是错误的几率就很高。这就是为什么算法将在“M”独立子流，并保持每个子一看到“00 ...... 1”字头的最大长度。然后，估计通过利用每个子的平均值最终值。

这是该算法的主要思想。有一些失落的细节（校正，以较低的估计值，例如），但是这一切都很好写在纸上。很抱歉的可怕的英语。

Answer 2:

甲HyperLogLog是概率数据结构。据统计列表中的不同元素的数量。但相较于做（具有一组和将元素添加到所述一组）的一个简单的方法它这样做以近似的方式。

望HyperLogLog算法如何做此之前，人们必须明白，为什么你需要它。用一个简单的方法的问题是，它消耗O(distinct elements)的空间。为什么有一个大O符号在这里，而不是仅仅不同的元素？这是因为元素可以是不同的尺寸。一个元素可以是1另一个元素"is this big string" 。所以，如果你有一个巨大的名单（或元素的一个巨大的数据流），它会占用大量内存。

概率计数

怎样才能获得一些独特的元素中的一个合理的估计？假定有长度的字符串m它由{0, 1}以相等的概率。什么是，它会从0开始，用2个0，其中k个零的概率？它是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 ）。所以，我们迄今取得的是，我们可估计与最大基数的独特元素的数量k通过存储的大小只有一个数字比特log(k)位。缺点是，我们在我们的估计了巨大的变化。我们几乎创造一个很酷的事情1984年的概率计数纸（它与估计聪明一点点，但我们仍然是关闭）。

双对数

进一步移动之前，我们必须明白，为什么我们的第一个估计不是很大。其背后的原因是，高频0前缀元件的一个随机事件可以破坏一切。以提高它的方法之一是使用许多散列函数，数最多为每个哈希函数，并在前端的平均出来。这是一个极好的主意，这将提高估值，但双对数纸使用略有不同的方法（可能是因为散列是一种昂贵的）。

他们用一个哈希值，但把它分成两个部分。一个被称为桶（桶的总数为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％，你显著改进估计。他们还用另一种算法的平均数字。本文是数学重。

我想最近的一份报告，其中显示了一个完成hyperLogLog算法的改进版本（到现在为止，我没有时间充分理解它，但也许以后我会改进这个答案）。

Answer 3:

直觉是，如果你的输入是一大组随机数（例如散列值），他们应该在一定范围内均匀分布。比方说，范围可达10位代表价值高达1024然后观察到的最小值。比方说，这是10。然后基数将估计为约100（10×100≈1024）。

阅读本文的过程中的真实逻辑。

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

文章来源: How does the HyperLogLog algorithm work?