最近我在业余时间学习了不同的算法，我发现了一个非常有趣的算法，叫做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)，使用了大量的内存(存储在表中的值)。
我一直在阅读这篇关于如何在O(n)时间内使用最小内存计算列表中的重复项的论文。
它解释说，通过哈希和计数位或其他东西，人们可以在一定的概率内估计(假设列表是均匀分布的)列表中唯一项的数量。
我看了报纸，但我似乎不懂。谁能给个更外行的解释?我知道哈希是什么，但我不明白它们是如何在这个HyperLogLog算法中使用的。
该算法背后的主要技巧是，如果你观察一个随机整数流，看到一个二进制表示以某个已知前缀开始的整数，则该流的基数更有可能是前缀的2^(大小)。
也就是说，在一个随机的整数流中，~50%的数字(二进制)以“1”开头，25%以“01”开头，12,5%以“001”开头。这意味着如果你观察一个随机流并看到一个“001”，那么这个流的基数为8的概率更高。
(前缀“00..”“1”没有特殊含义。它的存在只是因为在大多数处理器中很容易找到二进制数的最高位)
当然，如果只观察到一个整数，这个值出错的可能性就很大。这就是为什么该算法将流划分为“m”个独立的子流，并保持所见“00…每个子流的1”前缀。然后，通过取每个子流的平均值来估计最终值。
这就是这个算法的主要思想。有一些细节缺失(例如，对低估计值的修正)，但这些都写得很好。对不起，我的英语很糟糕。
该算法背后的主要技巧是，如果你观察一个随机整数流，看到一个二进制表示以某个已知前缀开始的整数，则该流的基数更有可能是前缀的2^(大小)。
也就是说，在一个随机的整数流中，~50%的数字(二进制)以“1”开头，25%以“01”开头，12,5%以“001”开头。这意味着如果你观察一个随机流并看到一个“001”，那么这个流的基数为8的概率更高。
(前缀“00..”“1”没有特殊含义。它的存在只是因为在大多数处理器中很容易找到二进制数的最高位)
当然，如果只观察到一个整数，这个值出错的可能性就很大。这就是为什么该算法将流划分为“m”个独立的子流，并保持所见“00…每个子流的1”前缀。然后，通过取每个子流的平均值来估计最终值。
这就是这个算法的主要思想。有一些细节缺失(例如，对低估计值的修正)，但这些都写得很好。对不起，我的英语很糟糕。
HyperLogLog是一种概率数据结构。它计算列表中不同元素的数量。但与直接的方法(拥有一个集合并向集合中添加元素)相比，它以近似的方式进行此操作。
在了解HyperLogLog算法是如何做到这一点之前，我们必须理解为什么需要它。直截了当的方法的问题是它消耗了O(不同元素)的空间。为什么这里有一个大O符号而不是不同的元素?这是因为元素可以有不同的大小。一个元素可以是1，另一个元素是这个大字符串。因此，如果你有一个巨大的列表(或一个巨大的元素流)，它将占用大量内存。
概率计算
How can one get a reasonable estimate of a number of unique elements? Assume that you have a string of length m which consists of {0, 1} with equal probability. What is the probability that it will start with 0, with 2 zeros, with k zeros? It is 1/2, 1/4 and 1/2^k. This means that if you have encountered a string starting with k zeros, you have approximately looked through 2^k elements. So this is a good starting point. Having a list of elements that are evenly distributed between 0 and 2^k - 1 you can count the maximum number of the biggest prefix of zeros in binary representation and this will give you a reasonable estimate.
The problem is that the assumption of having evenly distributed numbers from 0 t 2^k-1 is too hard to achieve (the data we encountered is mostly not numbers, almost never evenly distributed, and can be between any values. But using a good hashing function you can assume that the output bits would be evenly distributed and most hashing function have outputs between 0 and 2^k - 1 (SHA1 give you values between 0 and 2^160). So what we have achieved so far is that we can estimate the number of unique elements with the maximum cardinality of k bits by storing only one number of size log(k) bits. The downside is that we have a huge variance in our estimate. A cool thing that we almost created 1984's probabilistic counting paper (it is a little bit smarter with the estimate, but still we are close).
重对数
在进一步讨论之前，我们必须理解为什么我们的第一个估计不是那么好。其背后的原因是高频0前缀元素的随机出现会破坏所有内容。改进它的一种方法是使用许多哈希函数，为每个哈希函数计算max，最后将它们平均出来。这是一个很好的想法，它将改进估计，但是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/根号下(桶数))。
超级日志日志
HyperLogLog并没有引入任何新的想法，但主要是使用大量的数学来改进之前的估计。研究人员发现，如果你从桶中移除30%的最大数字，你的估计会显著提高。他们还使用另一种算法对数字求平均。这篇论文数学很重。
我想用最近的一篇论文来结束，这篇论文展示了hyperLogLog算法的改进版本(到目前为止我还没有时间完全理解它，但也许以后我会改进这个答案)。
