基数计数通常用来统计一个集合中不重复的元素个数，例如统计某个网站的UV，或者用户搜索网站的关键词数量。数据分析、网络监控及数据库优化等领域都会涉及到基数计数的需求。笔者实验了几种典型的流式摘要结构，包括用于频次估计的 Count-Min Sketch 以及用于基数估计的 HyperLogLog 和滑动窗口 HyperLogLog 算法以及它们的前身，但是笔者毕竟不是专做算法这块的，所以难免有纰漏欢迎评论指出。
Count-Min Sketch（CMS）
CMS的核心结构是一个d行w列的二维数组，每一行都有一个独立哈希函数，主要有两个操作：
- update（element, count）：对于每一行i计算此元素的哈希值，哈希值对w取模得到列数j，并将第i行、第j列的计数器值增加count
- estimate（element）：对于每一行i计算要查询元素的哈希值，找到对应列数的计数器值。在所有d个读取到的值中，取最小值作为该元素频率的估算值
Count-MinSketch 的频次估计具有单侧偏误的特性，由于每个桶 Ci 累加了所有映射至该位置元素的真实频次，任意单一哈希路径的估计值均满足
$$ C[i][ℎ_i(e)] ≥ f_e$$
即估计值只会比真实值高
定义指示变量 I_i,x,表示元素 x 是否在第 i 行与元素 e 发生冲突，则估计误差可以表示为：
$$ \hat{f}_e-f_e=\min_{1\leq i\leq d}\left\{\sum_{x\neq e}f_xI_{i,x}\right\} $$
单个哈希桶冲突带来的期望误差为
$$ \mathrm{E}[\sum f_xI_{i,x}]=(\parallel S\parallel_1-f_e)/w\leq\parallel S\parallel_1/w $$
通过设置宽度 w=⌈e/ϵ⌉ 并利用 d 个独立哈希函数取最小值，使得在 1−δ 的置信概率下有
$$ P\left(\sum f_x I_{i,x} \geq \epsilon \parallel S \parallel_1\right) \leq \frac{E\left(\sum f_x I_{i,x}\right)}{(e/w) \parallel S \parallel_1} \leq \frac{1}{e} $$
若令
$$ P\left(\hat{f}_e \geq f_e + \epsilon \parallel S \parallel_1\right) \leq \delta $$
$$ \left(\frac{1}{e}\right)^d \leq \delta $$
就可以解出d = ⌈ln(1/δ)⌉，在实际应用中可以根据δ来设置合理的d
空间复杂度为$O(w∗d)=O(\frac{1}{ϵ}ln(\frac{1}{δ}))$
Linear Counting（LC）
使用一个长度为 m 的比特数组，对每个元素，用哈希函数映射到 [0, m-1] 范围，将对应位置 1。统计数组中有多少位为 0，记作 u。基数估计：
$$ E(u)=mp_0=m(1-1/m)^n=me^{-n/m} $$
所以
$$ lnu=lnm-n/m即n=mln\frac{m}{u} $$
LC在空间复杂度方面并不算优秀，实际上LC的空间复杂度与简单bitmap方法是一样的，都是O（N）
Flajolet-Martin和PCSA
FM算法可以说是现代所有基数估计算法的源头，基本原理是：
对每个元素 x，计算哈希值 h(x)，得到一个二进制串，记录尾0个数，把桶里该个数的位置置1，，我们定义ρ(y)是桶里连续出现的尾0个数的最大值，比如桶里出现尾0个数有1、2、3、6，ρ(y)就是3。再根据n重伯努利实验：
$$ P(ρ(y)=k)=2^{−k} $$
令事件发生期望为1，得到基数估计值
$$ ñ =2^{ρ(y)}/ φ $$
实际中，为了减小误差提高精度，通常会采用单哈希分组平均法,也就是PCSA 算法,核心思想是通过哈希值对m取模得到m个组，每个组都可以独立估计n/m的值，对之前的ρ(y)（现在的Ri）取算术平均用于最终估计，从而提升了精度
$$ ñ = m ∗ 2^{(R1 + R2 + ... + Rm)/m }/ φ $$
空间复杂度$O(mlog_2n)$
LogLog Counting （LLC）
原理类似PCSA，对每个元素 x，计算哈希值 h(x)，得到一个二进制串,将哈希值的前几位作为桶索引，剩下的位数用于计算 ρ,即前导0位数（和PCSA的尾0本质一样）。每个桶里记录最大值，最后对桶记录的值做算术平均
$$ n=\alpha_m *m*2^{\frac{1}{m}\sum M[j]} $$
不加证明给出算法的标准误差：$\frac{1.30}{\sqrt{m}}$
故应用时如果要将误差控制在$\epsilon$之内，则需要
$$ m>(1.30/\epsilon)^2 $$
空间复杂度只有$O(mlog_2(log_2N))$
HyperLogLog （HLL）
类似LLC，估计基数时改用调和平均
调和平均一大优点就是天然压制离群值，这样一些极端情况里某个桶恰好遇到一个哈希值有很多前导零的元素时，异常大的M[j]对应极小的$2^{-M[j]}$，对求和几乎没有贡献
$$ H=\frac{m}{\sum 2^{-M[j]}} $$
$$ n=\alpha_m m^2(\sum 2^{-M[j]})^{-1} $$
其中
$$ \alpha_m=(m\int_0^\infty (log_2\frac{2+u}{1+u})^mdu)^{-1} $$
但是大概不会有人去算这玩意，工程上我们使用
| m（寄存器/桶数） | $\alpha_m$ |
|---|---|
| 16 | 0.673 |
| 32 | 0.697 |
| 64 | 0.709 |
| 128及以上 | $\frac{0.7213}{1+1.079/m}$ |
不加证明给出算法的标准误差：$\frac{1.04}{\sqrt{m}}$
因此在存储空间相同的情况下，HLL比LLC具有更高的精度
HyperLogLog++ （HLL++）
Google在2013年对HLL做了进一步优化，主要改进是针对不同基数大小做了平滑切换逻辑：
小基数时：引入稀疏表示，精确计数
中基数时：经验偏差的插值修正
大基数时：用 64 位哈希替代 32 位哈希
Sliding HyperLogLog （SHLL）
在hll上层增加了一个时间管理与过期机制，存储时为每个寄存器附加时间信息，插入时把该桶更新，查询时全局桶更新
附：
LLC与HLL直观过程，感兴趣的可以去试一试
