Flajolet–Martin 与 HyperLogLog

极值信号 ​

把不同元素计数公理库Distinct Elements 问题Distinct elements · F0 estimation统计频率向量支持集大小，并在流式版本中规定近似误差、失败概率与更新模型。中的每个元素均匀哈希为无限近似位串，令 $\rho (x)$ 为首个 1 的位置。单个元素满足 $\text{Pr}[\rho \ge r]=2^{-r}$；若不同元素数为 $D$，最大 rank $R$ 大约在 ${\log }_{2}D$ 附近，因此 $2^R$ 可估基数。重复元素哈希相同，不改变最大值。

FM 与 HLL ​

Flajolet–Martin 可用 bitmap 记录见过的 ranks，再由首个空位估计；单一极值方差较大，需多哈希/分组。HyperLogLog 用哈希前 $p$ 位选择 $m=2^p$ 个桶，剩余位的 rank 更新寄存器 $M_j$。原始估计形如

$$\hat{D}={\alpha }_m{m}^2{\left(\sum _{j=1}^m{2}^{-M_j}\right)}^{-1},$$

调和聚合抑制少数异常大寄存器，相对标准误差约 $1.04/\sqrt{m}$。

罕见事件图像 ​

出现 rank 20 意味着观察到概率约 $2^{-20}$ 的前缀事件，暗示独立不同元素规模约百万；它不是确定下界，因为少量元素也可能偶然产生长零串。多个桶提供许多近独立局部实验，才让估计稳定。

合并与边界 ​

两个 HLL 若使用相同哈希、桶数和 rank 定义，可逐寄存器取 max 得并集摘要。哈希偏差、对抗输入、少基数和哈希空间饱和都会产生系统误差；实际 HLL++ 使用小范围修正与偏差校准，常数须匹配版本。结果是概率估计，不是置信区间或确定上下界。

重复项与寄存器空间 ​

同一元素重复到达总产生相同桶与 rank，寄存器 max 不变，所以摘要天然估 distinct 而非流长度。每个寄存器只需存到哈希位宽的 rank，位数为 $O(\log \log U)$；总空间约 $m\log \log U$ 位加哈希种子。

小基数时许多寄存器仍为零，linear counting 修正利用零寄存器比例；大基数接近哈希空间时碰撞饱和。直接在所有范围都用原始调和公式会产生已知偏差。

寄存器状态的数值轨迹 ​

取 $p=2$ 时有四个寄存器，初态 [0,0,0,0]。若不同元素的 (桶号,rank) 依次为 (0,1),(2,3),(0,4),(2,2)，状态依次变为 [1,0,0,0]、[1,0,3,0]、[4,0,3,0]，最后一次不再改变。这个轨迹同时展示 max 更新、空桶和较小 rank 被吸收。

哈希位的拆分必须固定：前 $p$ 位只选桶，剩余位才计算 rank。若把同一批前缀位既用于桶号又计入前导零，桶选择与寄存器值产生相关性，标准误差分析不再适用。

寄存器可按固定小位宽紧凑打包，但更新某一字段时要掩码写回，避免进位污染相邻字段。由高精度摘要降采样到较小 $p$ 需要重新映射桶并修正 rank；它不是简单截断寄存器数组。

参考资料

• Philippe Flajolet, G. Nigel Martin, Probabilistic Counting Algorithms for Data Base Applications, JCSS, 1985.
• Philippe Flajolet et al., HyperLogLog: The Analysis of a Near-Optimal Cardinality Estimation Algorithm, AOFA, 2007.