rk3588's 小破站 - 2026年4月
type: channel
link: http://8.162.1.103/index.php/2026/04/
description: 今天要写些什么？
items: [CMS][HLL]大规模数据流的概率性摘要结构算法

[CMS][HLL]大规模数据流的概率性摘要结构算法
type: item
date: 2026-04-04T01:29:00+08:00
description: 基数计数通常用来统计一个集合中不重复的元素个数，例如统计某个网站的UV，或者用户搜索网站的关键词数量。数据分析、网络监控及数据库优化等领域都会涉及到基数计数的需求。笔者实验了几种典型的流式摘要结构，包括用于频次估计的 Count-Min Sketch 以及用于基数估计的 HyperLogLog 和滑动窗口 HyperLogLog 算法以及它们的前身，但是笔者毕竟不是专做算法这块的，所以难免有纰漏欢迎评论指出。Count-Min Sketch（CMS）CMS的核心结构是一个d行w列的二维数组，每一行都有一个独立哈希函数，主要有两个操作：update（element, count）：对于每一行i计算此元素的哈希值，哈希值对w取模得到列数j，并将第i行、第j列的计数器值增加countestimate（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和PCSAFM算法可以说是现代所有基数估计算法的源头，基本原理是：对每个元素 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}}$…