《布隆过滤器与超对数对数基数估计、千字节内存统计百站独立访客与去重订单母典》各章定量结论
经营一百个站点的主事者,常把各站后台的独立访客加在一起当作全网人数,把每张订单号存进越来越长的表里逐条比对,并相信教科书里布隆过滤器的误判率公式是精确的。本书证伪这三个信念。精确去重确实需要线性内存,这有严格证明;但随机化与近似同时接受之后,统计任意多个不同访客只需 3072 字节,标准误 0.0163。示意网络中,各站独立访客相加是真实人数的 2.224 倍。布隆过滤器的经典误判率公式是下界而非精确值:最小反例的真实值是 5/8,公式给出 9/16。书中的站点、访客、订单与流量参数均为示意;全部计算由书中程序生成;本书是非个人化经营建议;访客统计只用匿名化、加密钥哈希的标识,不收集个人身份信息,须遵守所在地个人信息保护法规与站点隐私声明,法规只述大意,以上架前人工复核为准。
DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 5DL-B-294 · English version
- 第 1 章 · 精确去重的内存账:独立访客为什么不能相加
精确去重的内存与人数几乎成正比:一亿访客时信息论下限是 485.841 MB,是一个 3072 字节草图的 158151 倍。这不是工程不够好,而是有严格证明的结论:确定性算法连一成以内的近似都需要线性内存,随机算法要精确也需要线性内存;只有随机化与近似同时接受,内存才能与人数无关。各站独立访客直接相加,在示意网络中高估了 2.224 倍;一百个草图按寄存器取最大值合并,误差是 0.0221,存储是 307200 字节。下一章拆开 H… - 第 2 章 · 超对数对数:首个 1 位、调和平均与 1.04/√m
第二章拆开 HyperLogLog,复算极限常数 1.03896,并说明 m = 16 时常数为 1.106、摘要里 1.5 千字节的例子对应标准误 0.0230。 - 第 3 章 · 两端的修正:线性计数、切换点偏差与哈希位数
第三章处理两端:基数低于 2.5 倍寄存器个数时改用线性计数,切换点有 0.0144 的正偏差;32 位哈希在十亿访客时丢掉 0.1079。 - 第 4 章 · 布隆过滤器:误判率公式、最优探查数与 1.44 倍空间
第四章实测布隆过滤器,说明最优探查数与 1.443 倍的空间因子。 - 第 5 章 · 订单去重:过滤器只分流、不拒单,窗口分代与计数删除
第五章规定过滤器只分流、不拒单:查库量减少 0.987,而凭过滤器拒单三十天会拒错 4916 张真实订单;窗口用两代轮换,删除用计数过滤器,普通过滤器清零会让 0.3944 的有效订单读成没见过。 - 第 6 章 · 百站合并、交集陷阱与寄存器的隐私
第六章合并一百个站点的草图,指出共有比例 0.10 时交集估计的相对误差达 0.421,并说明寄存器不是匿名的:访客稀少时再加一人使草图改变的概率是 0.9935。 - 第 7 章 · 东西方原典考辨:小司徒的比法与拉普拉斯的出生比
第七章考辨《周礼》小司徒的比法与拉普拉斯的出生比,复算拉普拉斯所需的 771469 人清点规模,并指出同样精度今天只需 24576 字节。 - 第 8 章 · 实证闭环:收费站与直答页只存寄存器的周报与预注册审计
第八章给出收费站与直答页只存寄存器的周报流程、基数估计器与预注册审计方案:示范周两页并集估计 35420 人、审计 35818 人,离散检验需要 70 个页日,订单闸门需要 3463 个已知新键。书中以标注框区分已发表的证据、可运行的 Python 计算(20 段程序)、原典与作者的假说。
模型示意算例,非实时报价