第 297 题：实现近似算法的Count-Min Sketch，频率估计的误差界。
题目
实现近似算法的Count-Min Sketch，频率估计的误差界。
完整讲解
一、Count-Min Sketch（CMS）
- 用途：用亚线性空间估计流中元素的频率（或计数），允许一定误差。多用于大流量的近似计数（如 item 曝光、关键词频）。
二、结构与更新
- 结构：$d \times w$ 的二维计数器表，$d$ 个哈希函数 $h_1,\ldots,h_d$，每个把 key 映射到 $[w]$。对每个 (key, count) 的更新：对每行 $i$，$C[i][h_i(key)] \mathrel{+}= \text{count}$。即每个 key 在每行贡献一个桶。
- 查询：$\hat{f}(key) = \min_i C[i][h_i(key)]$。取 $d$ 行中对应桶的最小值作为频率估计。因其他 key 会碰撞进同一桶，单行会高估；取 min 可减小高估（在无负更新时）。
三、误差界
- 理论：设真实频率为 $f$，流总计数为 $N$，则 $\hat{f} - f \le \frac{N}{w}$ 以高概率（每行）；取 min 后期望误差与 $d$ 相关，通常 $\hat{f} \ge f$ 且 $\mathbb{E}[\hat{f} - f] \le \frac{N}{w}$ 量级。增大 $w$ 降误差，增大 $d$ 降方差。
- 参数：$w = O(\varepsilon^{-1})$，$d = O(\ln(1/\delta))$ 可得到 $(\varepsilon, \delta)$ 保证。实现时 $w$ 取 2 的幂便于取模；哈希函数需两两独立或实用哈希族。
四、扩展
- 支持负更新需 Count-Min Sketch 的变体（如 Count-Mean-Min）；中位数代替 min 可减小偏差。推荐中可用于曝光/点击的近似计数、热点检测等。
面试要点
- 能说清 CMS 的结构（$d\times w$ 表、$d$ 个 hash）、更新与查询（取 min）的流程。
- 能给出误差的直观或形式化界（与 $N/w$、$d$ 的关系）；能说明 $w,d$ 的选取与空间权衡。
记忆要点
- Count-Min Sketch：$d\times w$ 计数器，每 key 每行 hash 到一个桶并累加；查询取 $d$ 个桶的 min。
- 误差：$\hat{f}\ge f$，误差量级约 $N/w$；$w$ 大降误差，$d$ 大降方差。