Flajolet–Martin 与 HyperLogLog

形式陈述 ​

哈希模型与稀有位串 ​

本页选择不同元素计数理路Distinct Elements 问题Distinct elements · F0 estimation统计频率向量支持集大小，并在流式版本中规定近似误差、失败概率与更新模型。的单位插入版本。固定输入流，并在理想分析中让不同键的哈希值是相互独立的均匀无限位串；同一键每次返回同一位串。仅有通用哈希理路通用哈希Universal hashing · Universal hash family从函数族随机选择哈希函数，使任意预先固定的不同键对以至多 1/m 的概率碰撞。的两键碰撞上界，还不足以推出下面的 rank 分布和基数估计定理。

令 $\rho$ 为首个 1 的位置，从 1 开始编号。对整数 $r\ge 1$，

前一个事件只要求前 $r-1$ 位为零，后一个还要求第 $r$ 位为一。对 $D\ge 1$ 个不同键，若 $R$ 是最大 rank，则

因此 $R$ 的典型量级接近 ${\log }_{2}D$，但单个长零串只能提供随机信号。

FM 位图与 HLL 寄存器 ​

Flajolet–Martin 用位图记录已经出现的 ranks，再由首个未出现的 rank 构造估计，并用重复或分组降低波动。HyperLogLog（HLL）选择 $m=2^p$ 个寄存器：哈希前 $p$ 位只决定桶号 $j$，剩余位才计算 $\rho$，更新 $M_j\leftarrow max(M_j,\rho )$。以下选择常用的零初态实现 $M_j=0$，原始估计为

理论定理采用精确归一化

固定 $m=2^p\ge 16$，沿键宇宙足够大的实例族让基数 $D\to \mathrm{\infty }$，原论文 Theorem 1 给出

这里 $|{\delta }_{1,m}(D)|<5\times {10}^{-5}$、$|{\delta }_{2,m}(D)|<5\times {10}^{-4}$；它们是对数尺度上的微小振荡项，并非被 $o_D(1)$ 吸收的消失项。主要标准差系数例如 ${\beta }_{16}\approx 1.106$、${\beta }_{128}\approx 1.046$；另沿二次幂寄存器数令 $m\to \mathrm{\infty }$，才有 ${\beta }_m\to \sqrt{3\ln 2-1}\approx 1.039$。常见的约 $1.04/\sqrt{m}$ 是对这个主要项的简写，不是任意有限 $D$ 的置信保证。

Theorem 1 的原始表示把未见桶设为 $-\mathrm{\infty }$，有空桶时估计为零。对每个固定 $m$，零初态与它具有相同的大 $D$ 渐近式：两者只在仍有空桶时不同；对 $m$ 个“第 $j$ 桶为空”事件应用并集界理路并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。，该事件概率至多 $m(1-1/m{)}^D$，且零初态估计在该事件上至多为 ${\alpha }_m{m}^2$，所以前两阶矩的差指数衰减。

实现中的校准还要另外区分。原论文 Figure 3 采用舍入值 $a_{16}=0.673$、$a_{32}=0.697$、$a_{64}=0.709$，以及 $m\ge 128$ 时的近似式 $a_m=0.7213/(1+1.079/m)$。用 $a_m$ 替换精确 ${\alpha }_m$ 会把同一原始估计乘以固定因子 $c_m=a_m/{\alpha }_m$；相对偏差因而增加 $c_m-1$，原振荡项与标准差也乘以 $c_m$。这项校准偏差不会仅因 $D$ 增大而消失，不能与初始化差异混为一谈。