Data Structure 随记（1）

目录

Bloom Filters

一句话解释作用：“如何判断一个元素是否在某个集合中？“

Bloom Filters 中文名布隆过滤器，好像以前在某个导论课上有老师提过，但是时过境迁现在已经完全忘了，这几天辅导的时候突然又遇到了这个数据结构，遂记录。 Bloom Filters 的内容大部分参考 UC Berkeley CS170 的 Note10，ref here。

如果键值的分布是未知的，使用一个特定的哈希函数 \(h\) 可能会产生不利 (adverse) 的影响：\(h\) 可能会误判键值之间的关系，使得哈希表的填充并不均匀。这显然不符合我们的预期，所以我们需要提出一些解决方案， Bloom Filters 就是一种可行的方案，利用不同的哈希函数 \(\{h_i\}\) 去映射每个键值。使用多种哈希函数可以在使用简单的哈希函数的同时最小化某些特定的哈希函数（可以理解为设计的很烂的哈希函数）对于哈希表的影响。

哈希表实际上能实现判断某个元素是否存在集合中，那设计 Bloom Filters 的 Motivation 是什么？

Bloom Filters 的设计目的是为了构建一个空间效率高的数据结构去解决“集合成员”的问题。因此，为了最大化空间效率，正确率在一定程度上被牺牲了。如果一个元素不在集合中， Bloom Filters 可能给出一个错误的答案（称为 false positive 假阳），但是如果元素存在集合中， Bloom Filters 一定会给出正确答案（这里我们只考虑 Standard Bloom Filters，即不考虑删除操作）。并且我们可以证明 Bloom Filters 假阳的概率足够低。

前排补充：可以省略的实际应用

Bloom Filters 的一个典型应用是网络缓存。一个 ISP (Internet Service Provider) 可能会保留几层特定的缓存，以加快常用网页的加载速度，特别是对于大型数据对象，如图像和视频。如果一个客户要求一个特定的URL，那么服务器需要迅速确定所要求的网页是否在其缓存中。假阳性虽然不可取，但是如果事实证明被认为在缓存中的页面不在那里，将它从其原始的URL加载，而且最终的 "penalty "并不比一开始就没有缓存差多少，那么假阳性也是可以接受的。

接下来是正式的描述：我们想要表示来自非常大的集合 \(U\) ，包含\(n\)个元素的集合 \(S=\left\{s_1, \ldots, s_n\right\}\)，其中 \(|U |=u>>n\)。（为了更好的理解，你可以将 \(U\) 视为一组 URL，将 \(n\) 视为缓存大小，并将 \(S\) 视为当前缓存中的那些网页的 URL。）我们希望支持插入和成员资格查询（“给定元素 \(x \in U\) 判断 \(x \in S\) ”）且：

  1. 如果答案是否定的，那么 \(x \notin S\)。
  2. 如果答案是肯定的，那么 \(x\) 可能在 \(S\) 中也可能不在 \(S\) 中，但是 \(x\notin S\)（假阳）的概率很低。

插入和成员资格查询操作的时间复杂度应该都为常数 \(\Theta(1)\)。

Bloom Filters 是一个包含 \(m\) 位的位向量 \(B\)，具有 \(k\) 个独立的哈希函数 \(h_1, \ldots, h_k\)，哈希函数用于将 \(U\) 中的每个值键映射到集合 \(R_m=\{0,1 , \ldots, m-1\}\)。 我们假设每个哈希函数 \(h_i\) 以相同的概率将随机选择的键值 \(x \in U\) 映射到 \(R_m\) 的每个元素。 由于哈希函数是独立的，因此向量 \(\left(h_1(x), \ldots, h_k(x)\right)\) 同样可能是来自的元素的 \(m^k k\) 元组中的任何一个 \(R_m\)。 最初，\(B\) 的所有 \(m\) 位都设置为 0 。

  • 将 \(x\) 插入 \(S\)。 计算 \(h_1(x), \ldots, h_k(x)\) 并设置 \(B\left[h_1(x)\right]=B\left[h_2(x)\right]=\cdots=\) \(B\left [h_k(x)\right]=1\)。
  • 查询 \(x\) 是否属于 \(S\)。计算 \(h_1(x), \ldots, h_k(x)\) ，如果 \(B\left[h_1(x)\right]=B\left[h_2(x)\right]=\cdots=\) \(B\left [h_k(x)\right]=1\) 那么答案是肯定的，否则是否定的。

Bloom Filters 很受工程师的欢迎，因为它用很少的工作就能实现“可证明”的良好性能（见参考文献的分析）：简单的哈希函数，简单的算法（没有碰撞处理等），有效地利用空间。Bloom Filters 的主要缺点是很难用 \(S\) 中的键值存储额外的信息。

Example

这是一个小例子，仅用来说明 Bloom Filters 如何工作的，以及对应假阳性的可能。

其唯一目的是说明假阳性的可能性。选择\(m=5\)（比特数）和\(k=2\)（哈希函数的数量）。

\[\begin{aligned}
& h_1(x)=x \bmod 5 \\
& h_2(x)=(2 x+3) \bmod 5
\end{aligned}
\]

我们首先初始化 Bloom filter \(B[1 . .5]\)，然后插入元素 \(9\) 和 \(11\)：

\[\begin{array}{l|cc|c|c|c|c|c|}
& h_1(x) & h_2(x) & & & B & & \\ \hline
\text{Initialize}: & & & 0 & 0 & 0 & 0 & 0 \\ \hline
\mathrm{Insert}\; 9: & 4 & 1 & 0 & \color{Salmon}{1} & 0 & 0 & \color{Salmon}{1} \\ \hline
\mathrm{Insert}\; 11: & 1 & 0 & \color{Salmon}{1} & 1 & 0 & 0 & 1 \\ \hline
\end{array}
\]

现在我们尝试进行两次 Query 操作：

\[\begin{array}{lccl}
& h_1(x) & h_2(x) & \text{Answer} \\
\mathrm{Query}\; 15: & 0 & 3 & \text{No, not in $B$ (correct answer)} \\
\mathrm{Query}\; 16: & 1 & 0 & \text{Yes, in $B$ (wrong answer: false positive)} \\
\end{array}
\]

注意⚠️：\(16\) 从没有插入到 Bloom Filters 中。

数学分析

见课件。