关于「实证闭环:收费站与直答页只存寄存器的周报与预注册审计」,《布隆过滤器与基数估计》给出的定量结论是什么?

结论:第八章给出收费站与直答页只存寄存器的周报流程、基数估计器与预注册审计方案:示范周两页并集估计 35420 人、审计 35818 人,离散检验需要 70 个页日,订单闸门需要 3463 个已知新键。书中以标注框区分已发表的证据、可运行的 Python 计算(20 段程序)、原典与作者的假说。

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

English version

对照数据表

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

day T est T audit A est A audit
13267 3231 4150 4210
24583 4577 4071 4004
33822 3832 3123 3113
42785 2774 5875 5830
55607 5562 2873 2922
64736 4789 4574 4507
74115 4155 5759 5807
week T 21137 (audit 21281), week A 18298 (audit 18563)
week union 35420 (audit 35818)
week overlap 4014 (audit 4026), share 0.113, FLAG: unreliable
daily SE 0.0163; overlap shares below 0.2 are flagged
stored14 sketches x 3072 bytes = 43008 bytes, no identifiers
查看完整验算程序
# Chapter 8. p81: one week of unique visitors on two pages, registers
# only. Illustrative traffic: page T (a tollbooth page) draws from a pool
# of 40,000 people, page A (a direct-answer page) from 25,000, with
# 10,000 in both pools; 2,500 to 6,000 people a day per page, 1 to 3
# hits each. Identifiers are hashed with a key that lives for one
# weekly window only; each page keeps one m = 4096 sketch per day
# (3,072 bytes). Weekly figures are register-wise maxima. Exact sets
# exist here only as the audit column; the daily pipeline keeps none.
# Counts under 50 would be shown as "<50" (none occur here).
import hashlib
import math
import random

rng = random.Random(20261113)
M, B, DAYS = 4096, 12, 7
ALPHA = 0.7213 / (1.0 + 1.079 / M)
WINDOW_KEY = b"b294-demo-window-label"
POOLS = {"T": range(0, 40000), "A": range(30000, 55000)}


def h64(text):
    d = hashlib.blake2b(text.encode(), digest_size=8, key=WINDOW_KEY)
    return int.from_bytes(d.digest(), "big")


def add(regs, x):
    j = x >> (64 - B)
    rho = (64 - B) - (x & ((1 << (64 - B)) - 1)).bit_length() + 1
    if rho > regs[j]:
        regs[j] = rho


def estimate(regs):
    e = ALPHA * M * M / math.fsum(2.0 ** -r for r in regs)
    v = regs.count(0)
    if e <= 2.5 * M and v > 0:
        return M * math.log(M / v)
    return e


def shown(x):
    return "<50" if x < 50 else "%.0f" % x


daily = {p: [] for p in POOLS}
audit = {p: [] for p in POOLS}
print("day   T est  T audit   A est  A audit")
for day in range(1, DAYS + 1):
    row = []
    for page, pool in POOLS.items():
        regs, seen = [0] * M, set()
        for person in rng.sample(pool, rng.randint(2500, 6000)):
            x = h64("visitor-%06d" % person)
            for _ in range(rng.randint(1, 3)):
                add(regs, x)
            seen.add(person)
        daily[page].append(regs)
        audit[page].append(seen)
        row += [shown(estimate(regs)), len(seen)]
    print("%3d %7s %8d %7s %8d" % (day, row[0], row[1], row[2], row[3]))
week = {p: [max(c) for c in zip(*daily[p])] for p in POOLS}
exact = {p: set().union(*audit[p]) for p in POOLS}
both = [max(a, b) for a, b in zip(week["T"], week["A"])]
eu = estimate(both)
inter = estimate(week["T"]) + estimate(week["A"]) - eu
ex_i = len(exact["T"] & exact["A"])
print("week T %.0f (audit %d), week A %.0f (audit %d)"
      % (estimate(week["T"]), len(exact["T"]), estimate(week["A"]),
         len(exact["A"])))
print("week union %.0f (audit %d)" % (eu, len(exact["T"] | exact["A"])))
flag = "FLAG: unreliable" if inter / eu < 0.2 else "ok"
print("week overlap %.0f (audit %d), share %.3f, %s"
      % (inter, ex_i, inter / eu, flag))
print("daily SE %.4f; overlap shares below 0.2 are flagged"
      % (1.04 / math.sqrt(M)))
print("stored: %d sketches x %d bytes = %d bytes, no identifiers"
      % (2 * DAYS, M * 6 // 8, 2 * DAYS * M * 6 // 8))

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《布隆过滤器与超对数对数基数估计、千字节内存统计百站独立访客与去重订单母典》第 8 章「实证闭环:收费站与直答页只存寄存器的周报与预注册审计」(版本 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}
}

本书其他章节结论