有效估计大型列表中唯一元素的数量

Question

这个问题与水库采样解决的问题有点类似，但又不一样。我认为这也是一个相当有趣的问题。

我有一个大型数据集（通常有数亿个元素），我想估计该数据集中唯一元素的数量。典型数据集中可能有几个到数百万个独特元素。

当然，显而易见的解决方案是维护您遇到的元素的运行哈希集，并在最后对它们进行计数，这将产生准确的结果，但需要我在扫描时携带潜在的大量状态。数据集（即到目前为止遇到的所有唯一元素）。

不幸的是，在我的情况下，这将需要比我可用的更多的 RAM（数据集可能远大于可用的 RAM）。

我想知道是否有一种统计方法可以让我对数据集进行一次遍历并在最后得出估计的唯一元素计数，同时在扫描数据时保持相对少量的状态数据集。

算法的输入是数据集（Java 术语中的迭代器），它将返回估计的唯一对象计数（可能是浮点数）。假设这些对象可以被散列（即，如果您愿意，您可以将它们放入 HashSet 中）。通常它们是字符串或数字。

Answer 1

您可以使用布隆过滤器来获得合理的下限。您只需遍历数据，计算并插入绝对不在集合中的项目。