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

假设你有一个很大的数据集，非常非常大，以至于不能全部存入内存。这个数据集中有重复的数据，你想找出有多少重复的数据，但数据并没有排序，由于数据量太大所以排序是不切实际的。你如何来估计数据集中含有多少无重复的数据呢？这在许多应用中是很有用的，比如数据库中的计划查询：最好的查询计划不仅仅取决于总共有多少数据，它也取决于它含有多少无重复的数据。

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

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

我们怎么估计结果数据集中有多少非重复的数字呢？了解到原来的数据集是随机数,且充分分散，一个非常简单的方法是：找出最小的数字。如果最大的可能的数值是 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 发现对于任意数据集，我们总可以给出一个好的哈希函数，使得哈希后的数据集可以是我们需要的任意一种排列。甚至充分分散的(伪)随机数也是如此。通过这个简单的灵感，我们可以把我们之前产生的数据集转化为我们想要的数据集，但是这远远还不够.