如何快速估计巨大 dataset 中unique 元素的数目

在大数据年代,很多简单的经典问题都会因为数据量巨大而变得十分具有挑战。绝大多数传统的精确算法将不再适用,因为对于TB量级的数据量,即使是O(N)的空间复杂度都会让内存不够使用;而当空间严重受限的情况下,传统算法的时间复杂度往往也会因此而暴涨。

Count Unique Items

比如一个简单问题:快速统计一个1TB 64 位整数序列中unique元素的个数。

对于统计unique 元素的个数,我们一般可以有两种方法来做:

  1. 将序列排序,再通过线性遍历来统计已排序序列中unique元素个数。时间复杂度是 O(nlog(n)),空间复杂度会根据排序算法来确定。
  2. 遍历序列,使用一个hashtable 来保存所有访问过的元素。使用一个counter 来记录遍历中unique元素的数目。时间复杂度是O(n),空间复杂度也是O(n)。

这两个方法在数据规模较小时,效率都还是不错的,尤其是第一个方法,空间开销较小,尤为实用。但是当数据规模增长到1TB时,它们都暴露出了问题

如果题目要求的是精确统计,也许我们别无它法,只能寄希望于通过引入计算机集群,以及分布式算法来提高以上算法的效率。但在实际应用中,此类统计往往并不对精度有100%的要求(而且有时往往也不可能达到100%的精度),我们可以通过一些统计的算法来估计结果,从而大大提高效率。这种非精确要求的统计,其应用到处可见。比如一个web server 通过一年来所有IP的访问记录来得到大概有多少unique的访问者;铁路部门通过多年来所有的买票记录得到大概有多少不同的乘客乘坐火车,等等。

Hyper Log Log

在此,如果你对统计算法有着精度太低或者算法过于复杂之类的偏见的话,那么我想在下面我将介绍的这个的算法必将让你大跌眼镜。它可以统计巨大序列并轻松得到一个误差小于1%的估计结果,而它的开销竟然是通过一次对数据的线性遍历以及1KB左右的内存消耗(常数大小)。它就是著名的hyperloglog算法。

hyperloglog是一个几乎能被称为魔法的算法,因为它简单地让人难以置信:

将序列中的元素转化成二进制数,并找出前导零最长的元素的前导零个数 n。(前导零指的是M位二进制数最高位中第一个1出现前0的个数。比如当M=16时,数据5414的二进制表达为0001010100100110,其前导零的数目n=3)最后可以得到unique 的元素的个数可以被估计成 C * 2^n ,C 是一个给定的常数。然后,就没有然后了。算法很简单,结果很神奇,你信吗?

好吧,其实我刚才还是有所隐瞒的。如果你希望hyperloglog算法拥有99%的精确度,其对输入数据是有要求的。所有的输入数据在二进制表达中要均匀随机地分布在 区间[0, 2^N) 里面,比如从0 到 2^32 的一个32位整数。我们当然不能要求输入数据by nature 就是如此均匀随机分布的,但是我们可以通过高强度加密hash算法,将输入数据均匀地hash到32位整数的区间。

总结一下,我们的算法是将输入数据序列X 通过hash 函数得到新的数列 H = hash(X)。 对于这个序列H,我们找出其中前导零最大的一个数中前导零的个数,通过公式 C * 2^n 得到结果。

当然,如果只是将所有输入使用一个hash 函数来经行一次统计,还是会存在偶然因素来影响精度。hyperloglog算法将会通过将输入数据分成m段,并且分别统计每一段的数目,最后在通过求平均的算法来减少偶然因素造成的误差。

在此时你可能会很困惑,为什么输入数据会跟2的“最大前导零”次幂相关呢?其实, 就直观上理解这个算法也是很简单的。我们知道每一个随机数里的每一位都是随机的,随机数前n位同时为0发生的概率是1/2^n,从而反过来说,如果要让这个事情发生,往往我们抽取不同样本的数目的期望会达到2^n。

我们再举一个生活中的例子。比如我让你在家扔硬币,并记录下连续硬币正面向上的最大次数。如果第二天你告诉我正面连续向上最长有连续5次,那么我想你昨天应该没扔几次,但是如果你告诉我最长正面向上连续有15次,那我们可以想象你应该是扔了一天的硬币了。Hyperloglog 就是通过这个方法来估算数目的。

博客推送