翻译自《Damn Cool Algorithms: Cardinality Estimation》，原文链接：http://blog.notdot.net/2012/09/Dam-Cool-Algorithms-Cardinality-Estimation

译注：给定一个数据集，求解数据集的基数（Cardinality，也译作“势”，表示一个数据集中不同数据项的数量）是非常普遍的一个需求。许多业务需求最终可以归结为基数求解，如网站访问分析中的UV（访客数，指一段时间内访问网站的不同用户的数量）。由于数据集基数是不可聚集指标（两个数据集总的基数无法通过分别的基数简单计算），因此如果要得到N个数据集任意组合的基数，需要2N次数据集去重计算，是一个复杂度非常高的计算过程。当数据量较小时，可以采取bitmap“按位或”方法获得较高的计算速度；而当数据量很大时，一般会采取概率算法对基数进行估计。这篇文章是对基数估计算法的一个非常好的概览。

以下为译文

--------------------

假如你有一个巨大的含有重复数据项数据集，这个数据集过于庞大以至于无法全部放到内存中处理。现在你想知道这个数据集里有多少不同的元素，但是数据集没有排好序，而且对如此大的一个数据集进行排序和计数几乎是不可行的。你要如何估计数据集中有多少不同的数据项？很多应用场景都涉及这个问题，例如设计数据库的查询策略：一个良好的数据库查询策略不但和总的数据量有关，同时也依赖于数据中不同数据项的数量。

我建议在继续阅读本文前你可以稍微是思考一下这个问题，因为接下来我们要谈的算法相当有创意，而且实在是不怎么直观。

一个简单直观的基数估计方法

让我们从一个简单直观的例子开始吧。假设你通过如下步骤生成了一个数据集：

1、随机生成n个服从均匀分布的数字

2、随便重复其中一些数字，重复的数字和重复次数都不确定

3、打乱这些数字的顺序，得到一个数据集

我们要如何估计这个数据集中有多少不同的数字呢？因为知道这些数字是服从均匀分布的随机数字，一个比较简单的可行方案是：找出数据集中最小的数字。假如m是数值上限，x是找到的最小的数，则m/x是基数的一个估计。例如，我们扫描一个包含0到1之间数字组成的数据集，其中最小的数是0.01，则一个比较合理的推断是数据集中大约有100个不同的元素，否则我们应该预期能找到一个更小的数。注意这个估计值和重复次数无关：就如最小值重复多少次都不改变最小值的数值。

这个估计方法的优点是十分直观，但是准确度一般。例如，一个只有很少不同数值的数据集却拥有很小的最小值；类似的一个有很多不同值的数据集可能最小值并不小。最后一点，其实只有很少的数据集符合随机均匀分布这一前提。尽管如此，这个原型算法仍然是了解基数估计思想的一个途径；后面我们会了解一些更加精巧的算法。

基数估计的概率算法

最早研究高精度基数估计的论文是Flajolet和Martin的Probabilistic Counting Algorithms for Data Base Applications，后来Flajolet又发表了LogLog counting of large cardinalities和HyperLogLog: The analysis of a near-optimal cardinality estimation algorithm两篇论文对算法进行了进一步改进。通过逐篇阅读这些论文来了解算法的发展和细节固然有趣，不过在这篇文章中我会忽略一些算法的理论细节，把精力主要放在如何通过论文中的算法解决问题。有兴趣的读者可以读一下这三篇论文；本文不会介绍其中的数学细节。

Flajolet和Martin最早发现通过一个良好的哈希函数，可以将任意数据集映射成服从均匀分布的（伪）随机值。根据这一事实，可以将任意数据集变换为均匀分布的随机数集合，然后就可以使用上面的方法进行估计了，不过只是这样是远远不够的。

接下来，他们陆续发现一些其它的基数估计方法，而其中一些方法的效果优于之前提到的方法。Flajolet和Martin计算了哈希值的二进制表示的0前缀，结果发现在随机数集合中，通过计算每一个元素的二进制表示的0前缀，设k为最长的0前缀的长度，则平均来说集合中大约有2k个不同的元素；我们可以用这个方法估计基数。但是，这仍然不是很理想的估计方法，因为和基于最小值的估计一样，这个方法的方差很大。不过另一方面，这个估计方法比较节省资源：对于32位的哈希值来说，只需要5比特去存储0前缀的长度。

值得一提的是，Flajolet-Martin在最初的论文里通过一种基于bitmap的过程去提高估计算法的准确度。关于这点我就不再详述了，因为这种方法已经被后续论文中更好的方法所取代；对这个细节有兴趣的读者可以去阅读原始论文。

到目前为止，我们这种基于位模式的估计算法给出的结果仍然不够理想。如何进行改进呢？一个直观的改进方法就是使用多个相互独立的哈希函数：通过计算每个哈希函数所产生的最长0前缀，然后取其平均值可以提高算法的精度。

实践表明从统计意义来说这种方法确实可以提高估计的准确度，但是计算哈希值的消耗比较大。另一个更高效的方法就是随机平均（stochastic averaging）。这种方法不是使用多个哈希函数，而是使用一个哈希函数，但是将哈希值的区间按位切分成多个桶（bucket）。例如我们希望取1024个数进行平均，那么我们可以取哈希值的前10比特作为桶编号，然后计算剩下部分的0前缀长度。这种方法的准确度和多哈希函数方法相当，但是比计算多个哈希效率高很多。

根据上述分析，我们可以给出一个简单的算法实现。这个实现等价于Durand-Flajolet的论文中提出的LogLog算法；不过为了方便，这个实现中统计的是0尾缀而不是0前缀；其效果是等价的。

def trailing_zeroes(num):

 """Counts the number of trailing 0 bits in num."""

 if num == 0:

   return 32 # Assumes 32 bit integer inputs!

 p = 0

 while (num >> p) & 1 == 0:

   p += 1

 return p

def estimate_cardinality(values, k):

 """Estimates the number of unique elements in the input set values.

 Arguments:

   values: An iterator of hashable elements to estimate the cardinality of.

   k: The number of bits of hash to use as a bucket number; there will be 2**k buckets.

 """

 num_buckets = 2 ** k

 max_zeroes = [0] * num_buckets

 for value in values:

   h = hash(value)

   bucket = h & (num_buckets - 1) # Mask out the k least significant bits as bucket ID

   bucket_hash = h >> k

   max_zeroes[bucket] = max(max_zeroes[bucket], trailing_zeroes(bucket_hash))

 return 2 ** (float(sum(max_zeroes)) / num_buckets) * num_buckets * 0.79402

这段代码实现了我们上面讨论的估计算法：我们计算每个桶的0前缀（或尾缀）的最长长度；然后计算这些长度的平均数；假设平均数是x，桶数量是m，则最终的估计值是

2x×m。其中一个没提过的地方是魔法数字0.79402。统计分析显示这种预测方法存在一个可预测的偏差；这个魔法数字是对这个偏差的修正。实际经验表明计算值随着桶数量的不同而变化，不过当桶数量不太小时（大于64），计算值会收敛于估计值。原论文中描述了这个结论的推导过程。

这个方法给出的估计值比较精确 —— 在分桶数为m的情况下，平均误差为1.3/m−−√。因此对于分桶数为1024的情况（所需内存1024*5 = 5120位，或640字节），大约会有4%的平均误差；每桶5比特的存储已经足以估计227的数据集，而我们只用的不到1k的内存！

让我们看一下试验结果：