Filters

前言：

本文中和文末设计了若干思考题，可以稍加思考。

Filter 用于解决如下问题：

普通的做法是开一个 uset 直接做，但是这样有若干缺陷：

因为如上原因，我们要引入 Bloom Filter（布隆过滤器）。

思考：平常的哈希表使用 vector 来避免冲突，我们现在允许一定的错误率，能否只用 01 字符串存储信息？要求只有假阳性而不会出现假阴性（即可能 0 回答成 1 而不允许 1 回答成 0）。

考虑如下算法：

但是这样 FP 率比较高。Bloom Filter 采用了如上思想，但是做了些许改进。

如果要取得较优的参数，可以查询 https://hur.st/bloomfilter/。

参数选择在合理范围内都具有可行性。

Bloom Filter 看似简单，事实上已经逼近了信息论的极限，但是仍然有许多方向可以优化。

Before Cuckoo：计数 Bloom Filter

思考：能否给 Bloom Filter 加入计数器使得其支持删除操作？

解答：显然可以，考虑存至多 $k$ 次，则需要 $k$ 倍空间，从赋值变为加减即可。

Cuckoo Filter 基于布谷鸟哈希算法。

布谷鸟哈希是一种特殊的哈希算法。

设立 $h_1(x) , h_2(x) \rightarrow [1 , m]$。

可以设一个踢出阈值动态扩容。

现在思考如下问题：

我们考虑不存储 $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)$。

做法已经呼之欲出：类似拓扑排序，将每个 $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}$。

放个伪代码。

$s(x) \rightarrow [0 , m] , c(x) \rightarrow [0 ,2^k), b(x) \rightarrow [0, 2^r)$ 都是 Hash 函数。

$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$。

这样就完成了插入。同时显然我们可以快速撤销上一次插入，但无法快速删除。

如何查询？考虑构造矩阵 $S$ 使得 $hS = b$，这样查询即可快速判断：只需查询 $h(x)S = b(x)$ 是否成立即可。

解答：这就是一个高斯消元。已经消出了一个上三角矩阵，因此做完了。（稍微说一下，就是倒着确定 $S$ 的每一行即可）。

显然构建出 $S$ 后可以立即抛弃 $h , b$ 矩阵，因此也只是产生临时空间。

取 $r = 4$ 效果不错（哈希位数）。

这张图是真实存储的 $c$ 矩阵（b）。

Homogeneous Ribbon Filters

这样 $b$ 矩阵就是一个全 $0$ 矩阵。

显然有平凡解 $S$ 也为全零矩阵。

但是如果使用这个 $S$，则 FP 率等于 $1$。

如果我们可以随机从解集空间选择一个 $S$，这样 FP 率会较低。而且这完全改善了构建失败的问题。

但是这个过滤器在 $n$ 较小时 FP 率较高，因为解的质量方差很大。所以在 $n < 10^4$ 时不要使用这个过滤器。

思考题：

另外，我新增了一道题目供测试。

可用于测试自己的 Filter 算法。