关于「超对数对数:首个 1 位、调和平均与 1.04/√m」,《布隆过滤器与基数估计》给出的定量结论是什么?

结论:第二章拆开 HyperLogLog,复算极限常数 1.03896,并说明 m = 16 时常数为 1.106、摘要里 1.5 千字节的例子对应标准误 0.0230。

数据口径:示意网络中,各站独立访客相加是真实人数的 2.224 倍。 书中的站点、访客、订单与流量参数均为示意;全部计算由书中程序生成;本书是非个人化经营建议;访客统计只用匿名化、加密钥哈希的标识,不收集个人身份信息,须遵守所在地个人信息保护法规与站点隐私声明,法规只述大意,以上架前人工复核为准。

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 1.03896, 1.106, 16

beta_inf = sqrt(3 ln 2 - 1)1.03896
alpha_inf1 / (2 ln 2) = 0.72135
m bias emp.SE SE*sqrt(m) paper in1s in2s in3s
16 -0.00300.2814 1.126 1.106 0.684 0.952 0.987
64 -0.00140.1304 1.043 1.054 0.686 0.955 0.994
256 -0.00020.0658 1.053 1.04 0.674 0.952 0.998
1024 -0.00020.0323 1.034 1.04 0.686 0.958 0.997
4096 -0.00010.0165 1.059 1.04 0.666 0.954 0.997
paper: within 1, 2, 3 sigma in about 0.65, 0.95, 0.99 of cases
查看完整验算程序
# Chapter 2. p22: the 1.04 / sqrt(m) law checked by 4,000 sketches per m.
# Poisson model (as in the analysis of Flajolet et al. 2007): with an
# ideal hash and Poisson(n) distinct items, the items of one register
# are Poisson(lam = n / m) and P(register <= r) = exp(-lam * 2^-r), so a
# register is drawn exactly by inverting that law. n = 1,000,000; the
# Poisson spread of n itself adds a relative 0.001, negligible here.
# Raw estimator E = alpha_m m^2 / sum 2^-M_j (no range correction is
# needed at n >> m). Paper constants: beta_16 = 1.106, beta_32 = 1.070,
# beta_64 = 1.054, beta_128 = 1.046, beta_inf = sqrt(3 ln 2 - 1);
# alpha_inf = 1 / (2 ln 2).
import math
import random

rng = random.Random(20261113)
N, T = 1000000, 4000
BETA = {16: 1.106, 64: 1.054}


def alpha(m):
    table = {16: 0.673, 32: 0.697, 64: 0.709}
    return table.get(m, 0.7213 / (1.0 + 1.079 / m))


def draw(lam):
    u = rng.random()
    while u == 0.0:
        u = rng.random()
    x = lam / -math.log(u)
    return 0 if x <= 1.0 else math.ceil(math.log2(x))


def sketch_estimate(m):
    lam = N / m
    regs = [draw(lam) for _ in range(m)]
    return alpha(m) * m * m / math.fsum(2.0 ** -r for r in regs)


print("beta_inf = sqrt(3 ln 2 - 1) = %.5f" % math.sqrt(3 * math.log(2) - 1))
print("alpha_inf = 1 / (2 ln 2)    = %.5f" % (0.5 / math.log(2)))
print("   m    bias   emp.SE  SE*sqrt(m)  paper  in1s  in2s  in3s")
for m in (16, 64, 256, 1024, 4096):
    rel = [sketch_estimate(m) / N - 1.0 for _ in range(T)]
    mu = math.fsum(rel) / T
    sd = math.sqrt(math.fsum((r - mu) ** 2 for r in rel) / (T - 1))
    s = 1.04 / math.sqrt(m)
    cover = [len([r for r in rel if abs(r) <= k * s]) / T
             for k in (1, 2, 3)]
    paper = "%.3f" % BETA[m] if m in BETA else " 1.04"
    print("%4d %7.4f %8.4f %11.3f %6s %5.3f %5.3f %5.3f"
          % (m, mu, sd, sd * math.sqrt(m), paper,
             cover[0], cover[1], cover[2]))
print("paper: within 1, 2, 3 sigma in about 0.65, 0.95, 0.99 of cases")

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《布隆过滤器与超对数对数基数估计、千字节内存统计百站独立访客与去重订单母典》第 2 章「超对数对数:首个 1 位、调和平均与 1.04/√m」(版本 1.0.0). 5D Library. DOI 待发布

DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 5DL-B-294 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026294,
  author    = {Fan, Yafu},
  title     = {Bloom Filters and HyperLogLog Cardinality Estimation: Counting Unique Visitors and Deduplicating Orders across a Hundred Sites in Kilobytes},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

本书其他章节结论