一个简单直观的基数估计方法
让我们从一个简单直观的例子开始吧假设你通过如下步骤生成了一个数据集
随机生成n个服从均匀分布的数字
随便重复其中一些数字重复的数字和重复次数都不确定
打乱这些数字的顺序得到一个数据集
我们要如何估计这个数据集中有多少不同的数字呢？因为知道这些数字是服从均匀分布的随机数字一个比较简单的可行方案是找出数据集中最小的数字 假如m是数值上限x是找到的最小的数则m/x是基数的一个估计例如我们扫描一个包含到之间数字组成的数据集其中最小的数是则一个 比较合理的推断是数据集中大约有个不同的元素否则我们应该预期能找到一个更小的数注意这个估计值和重复次数无关就如最小值重复多少次都不改变 最小值的数值
这个估计方法的优点是十分直观但是准确度一般例如一个只有很少不同数值的数据集却拥有很小的最小值类似的一个有很多不同值的数据集可能最小 值并不小最后一点其实只有很少的数据集符合随机均匀分布这一前提尽管如此这个原型算法仍然是了解基数估计思想的一个途径后面我们会了解一些更加 精巧的算法
基数估计的概率算法
最早研究高精度基数估计的论文是Flajolet和Martin的Probabilistic Counting Algorithms for Data Base Applications后来Flajolet又发表了LogLog counting of large cardinalities和HyperLogLog: The analysis of a nearoptimal cardinality estimation algorithm两篇论文对算法进行了进一步改进通过逐篇阅读这些论文来了解算法的发展和细节固然有趣不过在这篇文章中我会忽略一些算法的理论细节把精力主要放在如何通过论文中的算法解决问题有兴趣的读者可以读一下这三篇论文本文不会介绍其中的数学细节
Flajolet和Martin最早发现通过一个良好的哈希函数可以将任意数据集映射成服从均匀分布的（伪）随机值根据这一事实可以将任意数据集变换为均匀分布的随机数集合然后就可以使用上面的方法进行估计了不过只是这样是远远不够的
接下来他们陆续发现一些其它的基数估计方法而其中一些方法的效果优于之前提到的方法Flajolet和Martin计算了哈希值的二进制表示 的前缀结果发现在随机数集合中通过计算每一个元素的二进制表示的前缀设k为最长的前缀的长度则平均来说集合中大约有k个不同的元素我们 可以用这个方法估计基数但是这仍然不是很理想的估计方法因为和基于最小值的估计一样这个方法的方差很大不过另一方面这个估计方法比较节省资 源对于位的哈希值来说只需要比特去存储前缀的长度
值得一提的是FlajoletMartin在最初的论文里通过一种基于bitmap的过程去提高估计算法的准确度关于这点我就不再详述了因为这种方法已经被后续论文中更好的方法所取代对这个细节有兴趣的读者可以去阅读原始论文
到目前为止我们这种基于位模式的估计算法给出的结果仍然不够理想如何进行改进呢？一个直观的改进方法就是使用多个相互独立的哈希函数通过计算每个哈希函数所产生的最长前缀然后取其平均值可以提高算法的精度
实践表明从统计意义来说这种方法确实可以提高估计的准确度但是计算哈希值的消耗比较大另一个更高效的方法就是随机平均（stochastic averaging）这种方法不是使用多个哈希函数而是使用一个哈希函数但是将哈希值的区间按位切分成多个桶（bucket）例如我们希望取 个数进行平均那么我们可以取哈希值的前比特作为桶编号然后计算剩下部分的前缀长度这种方法的准确度和多哈希函数方法相当但是比计算 多个哈希效率高很多
根据上述分析我们可以给出一个简单的算法实现这个实现等价于DurandFlajolet的论文中提出的LogLog算法不过为了方便这个实现中统计的是尾缀而不是前缀其效果是等价的
def trailing_zeroes(num):
Counts the number of trailing bits in num
if num == :
return # Assumes bit integer inputs!
p =
while (num >> p) & == :
p +=
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 **k buckets
num_buckets = ** k
max_zeroes = [] * num_buckets
for value in values:
h = hash(value)
bucket = h & (num_buckets ) # 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 ** (float(sum(max_zeroes)) / num_buckets) * num_buckets *
这段代码实现了我们上面讨论的估计算法我们计算每个桶的前缀（或尾缀）的最长长度然后计算这些长度的平均数假设平均数是x桶数量是m则 最终的估计值是x×m其中一个没提过的地方是魔法数字统计分析显示这种预测方法存在一个可预测的偏差这个魔法数字是对这个偏差的修 正实际经验表明计算值随着桶数量的不同而变化不过当桶数量不太小时（大于）计算值会收敛于估计值原论文中描述了这个结论的推导过程
这个方法给出的估计值比较精确 —— 在分桶数为m的情况下平均误差为/m√因此对于分桶数为的情况（所需内存* = 位或字节）大约会有%的平均误差每桶比特的存储已经足以估计的数据集而我们只用的不到k的内存！
让我们看一下试验结果
>>> [/estimate_cardinality([randomrandom() for i in range()] ) for j in range()] [ ] 不错！虽然有些估计误差大于%的平均误差但总体来说效果良好如果你准备自己做一下这个试验有一点需要注意Python内置的 hash() 方法将整数哈希为它自己因此诸如 estimate_cardinality(range() ) 这种方式得到的结果不会很理想因为内置 hash() 对于这种情况并不能生成很好的散列但是像上面例子中使用随机数会好很多
提升准确度SuperLogLog和HyperLogLog
虽然我们已经有了一个不错的估计算法但是我们还能进一步提升算法的准确度Durand和Flajolet发现离群点会大大降低估计准确度如果 在计算平均值前丢弃一些特别大的离群值则可以提高精确度特别的通过丢弃最大的%的桶的值只使用较小的%的桶的值来进行平均值计算则平均 误差可以从/m降低到/m！这意味着在我们上面的例子中使用个字节可情况下可以将平均误差从%降低到%而所 需内存并没有增加
最后Flajolet等人在HyperLogLog论文中给出一种不同的平均值使用调和平均数取代几何平均数（译注原文有误此处应该是算数 平均数）这一改进可以将平均误差降到/m而且并没不需要额外资源但是这个算法比前面的算法复杂很多因为对于不同基数的数据集要做不 同的修正有兴趣的读者可以阅读原论文
并行化
这些基数估计算法的一个好处就是非常容易并行化对于相同分桶数和相同哈希函数的情况多台机器节点可以独立并行的执行这个算法最后只要将各个节 点计算的同一个桶的最大值做一个简单的合并就可以得到这个桶最终的值而且这种并行计算的结果和单机计算结果是完全一致的所需的额外消耗仅仅是小于k 的字节在不同节点间的传输
结论
基数估计算法使用很少的资源给出数据集基数的一个良好估计一般只要使用少于k的空间存储状态这个方法和数据本身的特征无关而且可以高效的进 行分布式并行计算估计结果可以用于很多方面例如流量监控（多少不同IP访问过一个服务器）以及数据库查询优化（例如我们是否需要排序和合并或者是否 需要构建哈希表）
