1

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

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

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

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

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

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

4

3 回答 3

4

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

于 2009-12-30T16:33:08.673 回答
2

这个问题在文献中得到了很好的解决；对各种方法的一个很好的回顾是http://www.edbt.org/Proceedings/2008-Nantes/papers/p618-Metwally.pdf。最简单的方法（对于非常高精度的要求也是最紧凑的）称为线性计数。您可以像使用 Bloom 过滤器一样将元素散列到位向量中的位置（除了只需要一个散列函数），但最后您通过公式 D = -total_bits * ln(unset_bits/total_bits) 估计不同元素的数量. 详细信息在论文中。

于 2012-03-14T00:40:04.217 回答
1

如果您有一个您信任的散列函数，那么您可以像为精确解决方案一样维护一个散列集，但丢弃散列值超出某个小范围的任何项目。例如，使用 32 位散列，但只保留散列的前两位为 0 的项目。然后在最后乘以适当的因子以近似唯一元素的总数。

于 2009-12-30T16:35:15.493 回答