为什么Count-Min Sketch只能高估不能低估频率

Count-Min Sketch 是一个用于估计事件频率的概率数据结构。它的核心特性是：对于任何元素，它给出的频率估计值 绝不低于 其真实频率，但可能高于真实频率。理解这一点，需要看清它的内部工作机制。

1. 理解 Count-Min Sketch 的基础结构

Count-Min Sketch 由一个简单的计数器数组构成。你可以把它想象成一个表格。

1. 定义一个二维数组，称之为“草图”。它有 d 行，w 列。d 和 w 是预先设定的参数。
2. 选择 d 个不同的哈希函数，分别记为 h_1, h_2, ..., h_d。每个哈希函数都能将一个输入元素（比如一个单词“apple”）映射到一个行内的特定列索引。例如，h_1(“apple”) 可能返回 5，表示指向第1行的第5列。
3. 初始化时，将这个二维数组中的所有计数器都设置为 0。

2. 执行“插入”与“查询”操作

有了结构，接下来是数据如何流入和流出。

插入一个元素（记录一次事件）

当一个元素出现一次（例如，单词“apple”被读到一次），执行以下步骤：

1. 计算所有 d 个哈希函数对该元素的值。得到一组列索引：(h_1(x), h_2(x), ..., h_d(x))。
2. 递增这 d 个位置对应的计数器。具体来说，将第1行 h_1(x) 列的计数器加1，将第2行 h_2(x) 列的计数器也加1，以此类推。

这个过程是同时作用于多行的。一次插入操作，会递增草图中 d 个（不同行）的计数器。

查询一个元素的频率

要查询元素 x 的估计频率时，执行以下步骤：

1. 计算与插入时相同的 d 个哈希值。
2. 读取这 d 个位置对应计数器的当前值。
3. 取这 d 个值中的最小值，作为元素 x 的最终频率估计值。

公式表示为：估计频率 = min{ C[1][h_1(x)], C[2][h_2(x)], ..., C[d][h_d(x)] }，其中 C 代表草图数组。

3. 核心分析：为什么只能高估，不能低估

关键原因就隐藏在 “哈希冲突” 和 “取最小值” 这两个机制中。

1. 哈希冲突导致计数器被“污染”：
   哈希函数并不完美。不同的元素 x 和 y，经过同一个哈希函数 h_i 后，可能得到相同的列索引。例如，h_i(“apple”) = 5 且 h_i(“banana”) = 5。这意味着，第i行的第5列计数器，将同时记录“apple”和“banana”的出现次数。

   当我们插入“apple”一次时，第i行第5列的计数器被递增。但这个递增可能并非完全由“apple”引起——如果“banana”之前也被插入过并共享了同一个计数器，那么这个计数器的值已经包含了“banana”的贡献。

   因此，当我们查询“apple”时，所读取的计数器 C[i][h_i(“apple”)] 的值，至少等于“apple”被插入的次数，但可能因为其他元素的冲突而变得更高。

2. 取最小值操作确保了“至少”：
   估计值取所有 d 个计数器的最小值。考虑以下两种情况：

   • 理想情况（无冲突）：对于查询元素 x，如果它在所有 d 行的哈希映射都是独占的（没有其他元素映射到同一列），那么这 d 个计数器的值都将精确等于 x 的真实频率。最小值就是真实频率。
   • 现实情况（有冲突）：由于冲突，某些计数器的值可能被抬高了。但是，不可能所有 d 个计数器的值都低于 x 的真实频率。因为每当 x 被插入一次，它所映射的全部 d 个计数器都会被递增一次。所以，每个计数器的值都至少记录了 x 的插入次数。

   因此，min{ 所有相关计数器 } 的结果，必然大于或等于 x 的真实频率。它等于真实频率加上由于冲突引入的额外“噪声”。这个“噪声”只会是正数，不可能为负。

4. 直观总结

你可以把 Count-Min Sketch 的查询过程想象成 “求证一件事”：

1. 你去 d 个不同的“信息源”（每一行）询问同一个问题（元素的频率）。
2. 每个信息源给出的答案（计数器值）都可能因为混淆了其他类似问题的信息而夸大其词。
3. 你为了得到最可靠的估计，只相信这些答案中最保守的那一个（取最小值）。
4. 最保守的答案，也绝对不会比事情的真相（真实频率）更低。因为它来自一个至少记录了你所有行为的地方。

Count-Min Sketch 通过牺牲“绝对精确”来换取“空间效率”和“速度”，并用“绝不低估”这一特性，保证了其估计值的可用性。