随机计数算法 probabilistic counting

一个著名的问题，给定一个数据集，一共有n个元素，其中完全不同的元素个数为m，怎么求出m？
如果要准确的计算，那么复杂度是nlog(n)的，因为我们首先要对n个元素排序，然后去重。
那么，我们如果n特别大，比如在搜索引擎的算法中，n可能有上亿，这个时候我们也不需要求出准确的m，只要给一个比较准确的m，满足一定的误差要求。这时就可以用一种随机计数的方法。
这个算法主要流程如下：
1.生成一个p个元素的数组 Bitmap[p], Bitmap[i] = 0
2.对数据集中的每个元素，求出他的hash值, h = hash(data[i]) mod p; Bitmap[h] = 1
3.最终，我们令Bitmap中0元素所占的比例为V, 那么一个m的估计就是
m = -p ln(V)

这个算法已经提出了很久。在计算图的全源最短路径时有也很多应用。

下面几篇文章是这个领域的一些重要文章

1.Probabilistic counting algorithms for data base applications
2.A linear-time probabilistic counting algorithm for database applications