有效估算大型列表中唯一元素的数量
这个问题有点类似于油藏采样解决的问题，但不一样。 我认为它也是一个相当有趣的问题。
我有一个很大的数据集（通常是数以亿计的元素），我想估计这个数据集中唯一元素的数量。 在典型的数据集中，可能存在几个到数百万个独特元素。
当然，显而易见的解决方案是维护一个正在运行的元素的哈希集合，并在最后对它们进行计数，这将产生一个确切的结果，但是需要我随身携带一个潜在的大量状态，数据集（即到目前为止遇到的所有独特元素）。
不幸的是，在我的情况下，这需要更多的RAM，而不是可用的RAM（没有什么数据集可能远远大于可用RAM）。
我想知道是否有一个统计方法可以让我单次通过数据集，并在最后提出一个估计的独特元素数，同时保持相对较少的状态，同时扫描数据集。
算法的输入将是数据集（Java中的迭代器），它将返回估计的唯一对象计数（可能是浮点数）。 假定这些对象可以被散列（也就是说，如果你愿意，你可以把它们放在一个HashSet中）。 通常他们将是字符串或数字。
您可以使用Bloom Filter来获得合理的下限。 您只需要传递数据，计算并插入绝对不在集合中的项目。
这个问题在文献中已得到很好的解决。 对各种方法的一个很好的回顾是http://www.edbt.org/Proceedings/2008-Nantes/papers/p618-Metwally.pdf。 最简单的方法（对于非常高的精度要求最紧凑）称为线性计数。 您可以像布洛姆过滤器那样将元素散列到位向量中的位置（除了只需要一个散列函数），但最后可以通过公式D = -total_bits * ln（unset_bits / total_bits）估计不同元素的数量。 。 详情在文件中。
如果你有一个你信任的散列函数，那么你可以维护一个散列集，就像你准确的解决方案一样，但是抛出散列值超出一定范围的项。 例如，使用32位散列，但只保留散列的前两位为0的项目。然后在末尾乘以适当的因子以近似唯一元素的总数。
链接地址: http://www.djcxy.com/p/61369.html上一篇: Efficiently estimating the number of unique elements in a large list
下一篇: Image download which protocol to be considered HTTp vs FTp