Filters
SafariMo
·
·
算法·理论
前言：
本文中和文末设计了若干思考题，可以稍加思考。
Filter 用于解决如下问题：
普通的做法是开一个 uset 直接做，但是这样有若干缺陷：
因为如上原因，我们要引入 Bloom Filter（布隆过滤器）。
思考：平常的哈希表使用 vector 来避免冲突，我们现在允许一定的错误率，能否只用 01 字符串存储信息？要求只有假阳性而不会出现假阴性（即可能 0 回答成 1 而不允许 1 回答成 0）。
考虑如下算法：
- 设计哈希函数 h(x) \rightarrow [1 , m]。
- 对于一个插入操作，a_{h(x)} = 1。
- 对于一个查询操作，查询 a_{h(x)} 的值。
但是这样 FP 率比较高。Bloom Filter 采用了如上思想，但是做了些许改进。
- 设计哈希函数 h_1(x) \sim h_k(x) \rightarrow [1 , m]。
- 对于一个插入操作，\forall i \in [1 , k], a_{h_i(x)} = 1。
- 对于一个查询操作，查询 \operatorname{and}_{i = 1}^k a_{h_k(x)} 的值。
如果要取得较优的参数，可以查询 https://hur.st/bloomfilter/。
参数选择在合理范围内都具有可行性。
Bloom Filter 看似简单，事实上已经逼近了信息论的极限，但是仍然有许多方向可以优化。
- 增加删除操作（Cuckoo Filter）。
- 优化空间性能（Xor Filter）。
- 杜绝错误（4-coloring Filter），但是有额外限制。
Before Cuckoo：计数 Bloom Filter
思考：能否给 Bloom Filter 加入计数器使得其支持删除操作？
解答：显然可以，考虑存至多 k 次，则需要 k 倍空间，从赋值变为加减即可。
Cuckoo Filter 基于布谷鸟哈希算法。
布谷鸟哈希是一种特殊的哈希算法。
设立 h_1(x) , h_2(x) \rightarrow [1 , m]。
- 如果 h_1(x) , h_2(x) 上没有巢穴直接随机放在 h_1(x) 或 h_2(x) 上。
- 如果 h_1(x) , h_2(x) 上只有一个巢穴直接放在空的巢穴上。
- 如果都不为空，则随机踢出一个元素，踢出的元素再重新计算哈希找到相应的位置。
可以设一个踢出阈值动态扩容。
现在思考如下问题：
- 直接建立 Cuckoo 哈希表是不可取的，这样做比普通哈希没有优势。思考空间复杂度瓶颈在哪里？
- 提示：如果使用 k 个 01 bit，随机哈希可达到 2^{-k} 的错误率。
- 如何在不存储 x 的情况下计算 Hash 值？
- 提示：考虑优化哈希函数。
我们考虑不存储 x 的真实值，但是这样我们就无法在迁巢时计算第二个哈希函数的真实值。
- 考虑改变：让两个 Hash 函数不再独立！
- 令 h_3(x) \rightarrow [1 , m]，f(x) \rightarrow [0, 2^k)
- 考虑让 h_2(x) = h_3(f(x)) \operatorname{xor} h_1(x)。
我们将键值变为 f(x)，如果我们仅存储 f(x)，我们也可以通过 \operatorname{xor} 的方式找到另一个哈希值。
查询的时候判断 h_1(x) , h_2(x) 下标是否有一个 = f(x) 的即可。
4-Coloring Filter 相对而言知名度较低，下文将介绍其核心思想。
这个 Filter 虽然效率最高但是有一个额外限制：必须提前给定所有输入，也就是你必须知道 S \cup Q，其中 Q 表示所有询问构成的集合，你也可以理解为每个元素有一个 \{0 , 1\} 权值然后若干次询问权值。
思考：设计 h_1(x) , h_2(x) \rightarrow [1 , m]，考虑根据 \{0 , 1\} 权值建图。
我们令 S_0 表示权值为 0 构成的 (h_1(x) , h_2(x)) 集合，S_1 表示权值为 1 构成的 (h_1(x) , h_2(x)) 集合。
我们钦定 |S_0| \leq |S_1|，否则可以交换。
考虑给图着色，让 S_0 中的所有边代表两个节点同色，S_1 代表异色。
如果找到一个合法的图着色方案，可以 \mathcal O(1) 回答询问，并且必然正确。
但是冲突是难免的（当 m 约等于 n 时），理由是并查集缩点后异色边链接同一个连通块，我们在启发式合并之后尽可能找到一组冲突数量尽可能少的解，剩余的再使用 hash_table/umap。
Xor Filter 的主要思想是设计三个哈希函数 h_1(x) , h_2(x), h_3(x) \rightarrow [1 , m]，和指纹 f(x) \rightarrow [0, 2^k) 并求出一组解 T 使得对于任意 x \in S，都有 T_{h_1(x)} \operatorname{xor} T_{h_2(x)} \operatorname{xor} T_{h_3(x)} = f(x)。
- 思考：如何构造 T？
- 提示：如果我们让 c_{h_1(x)} , c_{h_2(x)} , c_{h_3(x)} 都增加 1，即 c 是计数器。如果存在 c 值恰好为 1 的 j，无论其他 T_i 分布，我们可以仅改变该位的 T 使得条件成立。
做法已经呼之欲出：类似拓扑排序，将每个 c 值为 1 的点剔除，找到他的 h_1(x), h_2(x) ,h_3(x)，删除标记后我们将 (idx , j) 压入栈中。
最后弹出栈时修改 T_{idx} 使其满足条件即可。
这个算法需要离线处理，即先处理插入再回答询问。
如果仍然认为不够清晰，可以查阅伪代码:
事实上取 m = 1.23n + \mathcal O(1) 最优。
Ribbon Filter
Ribbon Filter 在概念上可视为 Xor Filter 的泛化。
下文中的矩阵乘法都是加乘矩阵（在 01 意义下），即 c_{i, j} = \operatorname{xor} a_{i , k} \operatorname{and} b_{k , j}。
放个伪代码。
**$c(x)$ 是定长二进制整数**，这样避免了 xor 时补位。记得低位补 $0$。
我们考虑令 $h(x) = 0^{s(x)} + c(x) + 0^{w - s(x) - |c(x)|}$，$+$ 表示字符串拼接，$0^{x}$ 表示 $x$ 个 $0$。这样每次相当于看 $h(x)$ 有多少个前缀 $0$，记为 $p$。
如果第 $p$ 行为空，则直接插入：$h_p = x , b_p = b(x)$。
否则让 $h(x) \leftarrow h(x) \operatorname{xor} h_p$，$b(x) \leftarrow b(x) \operatorname{xor} b_p$。
- tip：如果 $h(x)$ 归零说明构建失败（除非 $b(x) = 0$，此时说明了这个限制重复）
这样就完成了插入。同时显然我们可以快速撤销上一次插入，但无法快速删除。
- 为什么直接 xor 是对的：显然在同一行的元素 $s(x)$ 相同，又因为 $|c(x)|$ 定长，因此是对的。
如何查询？考虑构造矩阵 $S$ 使得 $hS = b$，这样查询即可快速判断：只需查询 $h(x)S = b(x)$ 是否成立即可。
- 思考：为什么查询是正确的？
- 解答：插入是一个消元的过程。
- 思考：如何构造 $S$。
- 提示：考察消元后 $h$ 矩阵的性质。
解答：这就是一个高斯消元。已经消出了一个上三角矩阵，因此做完了。（稍微说一下，就是倒着确定 $S$ 的每一行即可）。
显然构建出 $ S$ 后可以立即抛弃 $h , b$ 矩阵，因此也只是产生临时空间。
取 $r = 4$ 效果不错（哈希位数）。
RibbonFilter%E7%90%86%E8%AE%BA%E5%88%86%E6%9E%90//image-20240204164054237.png)
这张图是真实存储的 $c$ 矩阵（b）。
Homogeneous Ribbon Filters
- 考虑丢弃指纹函数 $b(x)$ 会怎么样。
这样 $b$ 矩阵就是一个全 $0$ 矩阵。
显然有平凡解 $S$ 也为全零矩阵。
但是如果使用这个 $S$，则 FP 率等于 $1$。
如果我们可以随机从解集空间选择一个 $S$，这样 FP 率会较低。而且这完全改善了构建失败的问题。
但是这个过滤器在 $n$ 较小时 FP 率较高，因为解的质量方差很大。所以在 $n < 10^4$ 时不要使用这个过滤器。
- 思考：给定 01（xor-and）矩阵 $x$，如何在所有 $xy$ 是全 $0$ 的解 $y$ 中随机选取一个？
- 解答：给每个自由变量赋值为 $[0 , 1]$ 中的随机权值即可。
思考题：
- 给定 FP 率 $p$ 和插入元素个数 $n$，计算最少使用的空间数量（信息论下界）。
- 计算 Bloom Filter 的 FP 率，（给定 $n , m , k$）。
- 解释 Cuckoo Filter 中 $h_3$ 的作用。
- 如何改造 4-Coloring Filter 使其支持在线插入和删除。
- 如何在 Homogeneous Ribbon Filters 使用 FP 率换时间？
另外，我新增了一道题目供测试。
- U640209 Filter Test
可用于测试自己的 Filter 算法。