用Python制作简单的朴素基数估计器的教程

在你继续读下去之前，我会引导你思考很多，因为今天我们要讨论的算法虽然很简单，但极具创意，它不是这么容易就能想出来的。
一个简单的朴素基数估计器

让我们从一个简单的例子开始吧。假定某人以下列方式来生成数据:

• 生成 n 个充分分散的随机数
• 任意地从中选择一些数字，使其重复某次
• 打乱这些数字

我们怎么估计结果数据集中有多少非重复的数字呢？了解到原来的数据集是随机数,且充分分散，一个非常简单的方法是：找出最小的数字。如果最大的可能的数值是 m，最小的值是 x，我们 可以估计大概有 m/x 个非重复的数字在数据集里面。举个例子，如果我们扫描一个数字在 0 到 1 之间的数据集，发现最小的数字是 0.01。我们有理由猜想可能数据集里大概有 100 个非重复的数字。如果我们找到一个更小的最小值的话，可能包含的数据个数可能就更多了。请注意不管每个数字重复了多少次都没关系，这是很自然的，因为重复多少次并不会影响?min?的输出值.

这个过程的优点是非常直观，但同时它也很不精确。不难举出一个反例：一个只包含少数几个非重复数字的数据集里面有一个很小的数。同样的一个含有许多非重复数字的数据集含有一个比我们想像中更大的最小值，用这种估计方法也会很不精确。最后，很少有数据充分分散充分随机的数据集。但是这个算法原型给了我们一些灵感使得我们有可能达到我们的目的，我们需要更精致一些的算法.
基于概率的计数

第一处改进来来自 Flajolet 和 Martin 的论文 Probabilistic Counting Algorithms for Data Base Applications。 进一步的改进来自 Durand-Flajolet 的论文 LogLog counting of large cardinalities 和 Flajolet et al 的论文 HyperLogLog：The analysis of a near-optimal cardinality estimation algorithm。从一篇论文到另一篇论文来观察想法的产生和改进很有趣，但我的方法稍有不同，我会演示如何从头开始构建并改善一个解决方法，省略了一些原始论文中的算法。有兴趣的读者可以读一下那三篇论文，论文里面包含了大量的数学知识，我这里不会详细探讨.

首先，Flajolet 和 Martin 发现对于任意数据集，我们总可以给出一个好的哈希函数，使得哈希后的数据集可以是我们需要的任意一种排列。甚至充分分散的(伪)随机数也是如此。通过这个简单的灵感，我们可以把我们之前产生的数据集转化为我们想要的数据集，但是这远远还不够.

接下来，他们发现存在更好的估计非重复数个数的方法。部分方法比记录最小的哈希值表现得更好。Flajolet 和 Martin 用的估计方法是计算哈希后的值的首部的 0 字的个数。显然在一个随机的数据集中，平均每 2^k 个元素就出现一个长度为 k 的全为 0 的比特序列。我们要做的就是找出这些序列并记录最长的来估计非重复元素的个数。然而这仍然不是一个很棒的估计器。它最多只能给我们一个 2 的幂的数量的估计。而且不像基于最小值的估计方法，这个方法的方差很大。但在另一个方面，我们的估计需要的空间非常小：为了记录最长 32 比特的前导 0 比特序列，我们只需要一个 5 比特的数字就可以了.

附注：Flajolet-Martin 原先的论文在这里继续讨论了一种基于 bitmap 的过程来获得一个更精确的估计。我不会讨论这个细节因为它马上就会在随后的方法中得到改进。更多细节对于有兴趣的读者可以阅读原论文。

现在我们得到了一个确实比较糟糕的比特式估计方法。我们能做出一些什么改进呢？一个直接的想法是使用多个独立的哈希函数。如果每个哈希函数?输出它自己的随机数据集，我们可以记录最长的前导 0 比特序列。然后在最后我们就可以对其求一个平均值以得到一个更精确的估计。

从实验统计上来看这给了我们一个相当好的结果，但哈希的代价的是很高的。一个更好的方式是一个叫做随机平均的方法。相比使用多个哈希函数，我们仅仅使用一个哈希函数。但是把它的输出进行分割然后使用它的一部分作为桶序号来放到许多桶中一个桶里去。假设我们需要 1024 个值，我们可以使用哈希函数的前 10 个比特值作为桶的序号，然后使用剩下的哈希值来计算前导 0 比特序列。这个方法并不会损失精确度，但是节省了大量的哈希计算.

把我们目前学到的应用一下，这里有一个简单的实现。这和 Durand-Flajolet 的论文中的算法是等价的，为了实现方便和清晰所以我计算的是尾部的 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

>>> [100000/estimate_cardinality([random.random() for i in range(100000)]，10) for j in range(10)]
[0.9825616152548807，0.9905752876839672，0.979241749110407，1.050662616357679，0.937090578752079，0.9878968276629505，0.9812323203117748，1.0456960262467019，0.9415413413873975，0.9608567203911741]