algorithm - 为什么在hyperloglog算法的前导零计数中加1

Question

如果哈希的位模式中有 k 个前导零，为什么估计大小被认为是 2 ^k+1？不应该是^2k吗？k 前导零的概率应该是 1/(2 ^k )，因此大小应该是 2 ^k

在我的代码中，当我使用 k+1 而不是 k 时，我总是得到正确的大小估计。但我无法理解这背后的逻辑。

Answer 1

您正在寻找的直觉是该算法依赖于在哈希开头看到整个位模式的概率（k 个零，后跟一个 1），而不仅仅是零。

更困难的部分是从那里开始估计 2 ^k+1的基数。不幸的是，这一点的正式证明并不简单。事实上，大部分介绍该方法的原始论文（Flajolet 和 Martin，Probabilistic counting Algorithms for Data Base Applications，http://algo.inria.fr/flajolet/Publications/FlMa85.pdf）致力于证明用它计算的估计是一个很好的估计。随后的论文（LogLog 和 HyperLogLog 论文）对改进的估计有类似的证明。

希望有帮助！

Answer 2

k 前导零表示前 k 位是零，后跟一位。（否则，我们将有超过 k 个前导零位。）因此，k 个前导零实际上由长度为 (k+1) 的位序列表征，其概率为 1/2^(k+1)。

Answer 3

根据概率论，你是对的！在观察到具有 k 个前导零的值之前，您会期望进行 2 ^{k次观察（平均而言）。}

您的估计值是应有的两倍的原因可能是因为您的随机函数（或散列函数）返回的有符号 int 始终为正且始终存在前导零。这应该使您看到具有 k 个前导零的值的机会大约增加一倍。这就是为什么当您使用 2 ^k+1而不是 2 ^k时会得到正确答案的原因。