HyperLogLogalgorithm如何工作?

我最近在业余时间已经学习了不同的algorithm,而我遇到的一个看起来非常有趣的algorithm叫做HyperLogLogalgorithm – 它估计列表中有多less独特的项目。

这对我来说特别有意思,因为当我看到“基数”值(直到最近我一直认为它是不计算的)时,才使我回到了MySQL日子。

所以我知道如何在On )中编写一个algorithm来计算一个数组中有多less个独特的项目。 我用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; } 

但问题是,我的algorithm,而On ),使用大量的内存( Table存储的值)。

我一直在阅读这篇文章,关于如何计算On )时间列表中的重复项,并使用最less的内存。

它解释了通过散列和计数位,或者可以以一定概率(假设列表均匀分布)估计列表中的唯一项目的数目。

我读过这篇文章,但我似乎无法理解。 有人可以给更多的非专业人士的解释吗? 我知道哈希是什么,但我不明白它们在HyperLogLogalgorithm中是如何使用的。

这个algorithm背后的主要技巧是,如果你观察一个随机整数stream,看到一个二进制表示以一个已知的前缀开始的整数,那么stream的基数有2 ^(前缀的大小) 。

也就是说,在整数的随机stream中,约50%(二进制)的数字以“1”开始,25%以“01”开始,12.5%以“001”开始。 这意味着如果你观察到一个随机stream并且看到一个“001”,那么这个stream的基数就是8。

(前缀“00..1”没有特殊含义,只是因为在大多数处理器中很容易find二进制数中最重要的位)

当然,如果只观察一个整数,那么这个值错误的概率就很高。 这就是为什么algorithm将stream划分为“m”个独立子stream,并保持每个子stream的最大长度似乎为“00 … 1”的前缀。 然后,通过取每个子stream的平均值来估计最终值。

这是这个algorithm的主要思想。 这里有一些缺失的细节(例如对低估值的修正),但是在论文中都写得很好。 对不起,可怕的英语。

HyperLogLog是一个概率数据结构 。 它计算列表中不同元素的数量。 但是与直接的做法相比(有一个集合和添加元素的集合),它以一个近似的方式做到这一点。

在查看HyperLogLogalgorithm如何实现这一点之前,必须先了解为什么需要它。 直接的问题是消耗空间的O(distinct elements) 。 为什么这里有一个很大的O符号,而不是仅仅是独特的元素? 这是因为元素可以具有不同的大小。 一个元素可以是另一个元素"is this big string" 。 所以如果你有一个巨大的列表(或者一个巨大的元素stream),它将需要很多的内存。


概率计数

如何才能得到一个独特的元素的合理估计? 假设你有一个长度为m的串,它由{0, 1}以相等的概率组成。 它以0开始的概率是多less,有两个零,k个零? 它是1/2^k 1/2 1/41/2 1/2^k 。 这意味着如果你遇到了一个有k零的string,你大概已经查看了2^k元素。 所以这是一个很好的起点。 有一个均匀分布在02^k - 1之间的元素列表,你可以计算二进制表示中最大的零前缀的最大数目,这将给你一个合理的估计。

问题是假设从0 t 2^k-1有均匀分布的数字是很难实现的(我们遇到的数据大多不是数字,几乎从来没有均匀分布,可以在任何值之间,但是使用一个好的散列函数可以假设输出比特将是均匀分布的,大多数散列函数的输出在02^k - 1 ( SHA1给出的值在02^160之间),所以我们到目前为止所取得的是我们可以通过只存储一个大小为log(k)位来估计具有最大基数为k位的唯一元素的数量,而不利之处在于我们的估计有很大的变化,一个很酷的事情,我们几乎创build了1984年的概率计数论文(估计有点聪明,但我们仍然接近)。

双对数

在进一步深入之前,我们必须明白为什么我们的初步估计不是那么好。 其背后的原因是随机出现的高频0字元素可能会破坏一切。 改进它的一种方法是使用许多散列函数,对每个散列函数计算最大值,最后将其平均。 这是一个很好的主意,它可以改善估计,但是LogLog文件使用了一个稍微不同的方法(可能是因为哈希是昂贵的)。

他们使用了一个散列,但将其分为两部分。 一个被称为一个桶(桶的总数是2^x ),另一个 – 基本上和我们的哈希相同。 我很难得到正在发生的事情,所以我会举一个例子。 假设你有两个元素,你的散列函数给出的值从02^10产生2个值: 344387 。 你决定有16个桶。 所以你有了:

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

通过有更多的桶,你减less了方差(你使用稍微更多的空间,但它仍然很小)。 使用math技能,他们能够量化错误( 1.3/sqrt(number of buckets) )。

HyperLogLog

HyperLogLog没有引入任何新的想法,但大多数使用大量的math来改善以前的估计。 研究人员发现,如果从桶中删除30%的最大数字,则可以显着提高估算值。 他们还使用另一种algorithm来平均数字。 这篇论文math很重。


我想用最近的一篇论文来完成,它显示了hyperLogLogalgorithm的改进版本 (到目前为止我没有时间去完全理解它,但也许以后我会改进这个答案)。

直觉是,如果你的input是一个大的随机数(例如哈希值),他们应该均匀分布的范围。 假设范围高达10位,表示值高达1024.然后观察最小值。 假设它是10.然后基数估计是大约100(10×100≈1024)。

阅读论文的真正逻辑当然。

示例代码的另一个很好的解释可以在这里find:
该死的algorithm:基数估计 – 尼克的博客