空间少错误率低且高效的 hash 技术：Bloom Filter
bsdsdb
·
·
算法·理论
例题
给你 n 个字符串，每个字符串长度为 32，问你是否出现了至少 a 个不同的字符串。
如果正确答案为 `YES`，那么输入数据中实际上会包含至少 $a+\lfloor\frac n{10^5}\rfloor$ 个不同的字符串；如果正确答案为 `NO`，那么输入数据中可能包含 $a-1$ 个不同的字符串。也就是说，题目允许一定的错误率。
如果使用传统的 hash，那么 $5\text{MB}$ 的内存限制使得我们对每个字符串只能存储一个值域在 $10^9$ 左右的 hash 值。使用一个 dp 可以得出这样做的正确率：
::::info[dp 代码及运行结果]
```cpp
f128 dp[11][1000005];
f128 qpow(f128 x, ll y) {
if (!y)
return 1;
else if (y & 1)
return x * qpow(x, y ^ 1);
else
return qpow(x * x, y >> 1);
}
f128 cal(ll n, ll p, ll w) {
dp[0][0] = 1;
f128 a = 1 - f128(1) / p;
#define f(x) qpow(a, x)
for (ll j = 1; j <= n; ++j)
dp[0][j] = dp[0][j - 1] * (1 - f(j));
for (ll i = 1; i <= w; ++i)
for (ll j = 1; j <= n; ++j)
dp[i][j] = dp[i][j - 1] * (1 - f(j)) + dp[i - 1][j - 1] * f(j);
f128 ret = 0;
for (ll i = 0; i <= w; ++i)
ret += dp[i][n];
return ret;
}
```
$$
\mathrm{cal}(10^6,10^9,10)\approx0\\
\mathrm{cal}(10^6-1,10^9,9)\approx0\\
\mathrm{cal}(10^5-1,10^9,0)\approx0
$$
::::
显然这样是不行的，我们需要另外的算法：Bloom Filter。
## 算法
我们开一个 $m$ 大小的 `bitset` $B$，再准备 $k$ 个 hash 函数，输入字符串，返回的值平均分布在 $[0,m)$ 上。令第 $i$ 个 hash 函数为 $h_i(s)$，再定义 $H(s)\coloneqq\{h_i(s):i\le k\}$ 为一个字符串所有 hash 值的集合。如果 $H(s)$ 中的每个元素都在 $B$ 中标成了 $1$，就认为这个字符串出现过了，反之亦然。最后将 $H(s)$ 中的每个元素都在 $B$ 中标上 $1$。
::::align{center}
（转自 Wikipedia）
::::
如图，$w$ 被判为一个新的字符串，因为 $h_3(w)$ 在 $B$ 中没有标记为 $1$。
他的时间复杂度为 $\Omicron(k\sum|s|)$，空间复杂度为 $\Omicron(\frac mw)$。
## 错误率分析
### 什么时候出现错误
如果已经插入 $S$ 中的字符串，需要插入一个新的字符串 $s'\notin S$，那么 $s'$ 被误判为属于 $S$ 等价于 $H(s')\subseteq\bigcup_{s\in S}H(s)$。比如 $H(\texttt a)=\{1,2\},H(\texttt b)=\{3,4\},H(\texttt c)=\{1,3\}$ 时，$\texttt c$ 会被误判为一个出现过的字符串。
这个算法只会将未出现的字符串误判为出现过的，不会将出现过的误判为未出现的。所以当输入数据里面不同的字符串数量小于 $a$ 时，我们的输出 `NO` 永远是正确的。接下来考虑将 $a+\lfloor\frac n{10^5}\rfloor$ 个字符串误判为不超过 $a-1$ 个不同字符串的概率。
### 错误率
先来求插入 $n$ 个不同的字符串后，插入 $n+1$ 个字符串时出现错误的概率。
对于 $B$ 里面的每一位，一个 hash 函数没有访问到他的概率为 $1-\frac1m$，$n$ 个字符串（$kn$ 个 hash 函数）都不覆盖他的概率为 $\left(1-\frac1m\right)^{kn}$，那么第 $n+1$ 个字符串所映射到的 $k$ 个位置曾经被覆盖的概率（错误率）为
$$
f(n,m,k)\coloneqq\left(1-\left(1-\frac1m\right)^{kn}\right)^k
$$
那么，插入 $n$ 个不同字符串的正确率即为 $\prod_{i=0}^{n-1}(1-f(i,m,k))$。
### 如何选取 $k
选取一个全局最优的 k（使正确率之积最大的 k）对我来说太难了，这里只讨论求对固定的 n,m 使得 f(n,m,k) 最小的 k，后面会说明这样是完全够用的。
设 a\coloneqq\left(1-\frac1m\right)^n，那么错误率简化为 f=\left(1-a^k\right)^k，取对数 \ln f=k\ln(1-a^k) 然后考虑他的单调性，也就是导函数的正负性：
\begin{aligned}
\frac\partial{\partial k}\ln f=&(k')\ln(1-a^k)+k(\ln(1-a^k))'\\
=&\ln(1-a^k)+k\cdot\frac1{1-a^k}\cdot(-1)\cdot a^k\ln a\\
=&\ln(1-a^k)-\frac{ka^k\ln a}{1-a^k}
\end{aligned}
设 t\coloneqq a^k\in(0,1) 则
(\ln f)'=\ln(1-t)-\frac{t\ln t}{1-t}
::::warning[注意]{open}
::::
他有根 $t=\frac12$，以及下列极限行为：
- $t\to0^+$ 的时候 $\ln(1-t)\to 0,t\ln t\to0,\frac{t\ln t}{1-t}\to0,(\ln f)'\to0$（$t\ln t$ 的极限可以把它写成 $\frac{\ln t}{t^{-1}}$ 然后用 L'Hopital 法则）；
- $t\to1^-$ 的时候 $\ln(1-t)\to-\infty,\frac{\ln t}{t-1}\to1,\frac{t\ln t}{1-t}\to-1,(\ln f)'\to-\infty$；
下证 $(\ln f)'$ 单峰且最值点在 $\frac12$ 左侧：
::::info[下]
设 $g\coloneqq(\ln f)'=\ln(1-t)-\frac{t\ln t}{1-t}$。讨论 $g$ 的单调性，就要讨论 $g'$ 的正负性。先把 $g'$ 求出来：
$$
\begin{aligned}
(t\ln t)'=&\ln t+1\\
\left(\frac{t\ln t}{t-1}\right)'=&\frac{(t\ln t)'(t-1)-t\ln t(t-1)'}{(t-1)^2}\\
=&\frac{-\ln t+t-1}{(t-1)^2}\\
g'=&\frac1{t-1}+\left(\frac{t\ln t}{t-1}\right)'\\
=&\frac{2t-2-\ln t}{(t-1)^2}
\end{aligned}
$$
$g'$ 的正负性就是分子 $h\coloneqq 2t-2-\ln t$ 在 $(0,1)$ 上的正负性。$\lim_{t\to0^+}h=+\infty,\lim_{t\to1^-}h=0$，以及 $h'$ 在 $\frac12$ 左侧为负右侧为正，$h(\frac12)=\ln 2-1<0$，又因为 $h$ 连续，所以存在恰好一个 $t_0<\frac12$ 使得 $h(t_0)=0$，$h$ 在 $t_0$ 左侧为正右侧为负，$g'$ 也是一样的。所以 $g$ 在 $t_0$ 左侧单增右侧单降，他是单峰的，且最值点 $t_0<\frac12$。
::::
这样一来就有了 $(\ln f)'$ 在 $\frac12$ 左侧为正，右侧为负，因此 $\ln f$ 的最值点在 $t=\frac12$ 处，显然这也是 $f$ 的最值点。
::::info[总结一下]{open}
我们用 $(\ln f)''$ 的分子的正负推出 $(\ln f)''$ 的正负，从而得出 $(\ln f)'$ 的单调性，结合 $(\ln f)'$ 的极限行为得出 $(\ln f)'$ 的正负性，从而推出 $(\ln f)$ 和 $f$ 的最值点。
::::
用 $t=\frac12$ 解出 $k$：
$$
k=\log_at=\frac{\ln t}{\ln a}=-\frac{\ln2}{\ln a}=\boxed{-\frac{\ln2}{n\ln\left(1-\frac1m\right)}}
$$
将 $k$ 代回错误率公式：
$$
\begin{aligned}
f=&\left(1-a^k\right)^k\\
=&\left(1-a^{-\frac{\ln2}{\ln a}}\right)^{-\frac{\ln2}{\ln a}}\\
=&\boxed{\left(1-\left(1-\frac1m\right)^{-\frac{\ln2}{\ln\left(1-\frac1m\right)}}\right)^{-\frac{\ln2}{n\ln\left(1-\frac1m\right)}}}\\
\end{aligned}
$$
### $k$ 与错误率的近似公式
这么一大串记不住怎么办？
根据等式
$$
e^{-1}=\lim_{m\to+\infty}\left(1-\frac1m\right)^m
$$
做出估计
$$
a=\left(1-\frac1m\right)^n\approx e^{-\frac nm}
$$
代入上面的结论
$$
k=-\frac{\ln2}{\ln a}\approx\frac{\ln 2}{\frac nm}=\boxed{\frac mn\ln2}\\
\begin{aligned}
f=&\left(1-a^k\right)^k\\
\approx&\left(1-e^{-\frac nm\cdot\frac mn\ln2}\right)^{\frac mn\ln2}\\
=&\left(1-e^{-\ln2}\right)^{\frac mn\ln2}\\
=&\boxed{\left(\frac1{2^{\ln2}}\right)^{\frac mn}\approx0.6195^{\frac mn}}\\
\end{aligned}
$$
### 在原题中的错误率
在这道毒瘤题里面，当我们令 $m=32\times10^6,k=10$ 时，使用乘法可以得出所有判断都不错的概率约为 $81\%$，再用与之前类似的 dp 可以得出所有不同字符串计数错 $\frac{n}{10^5}$ 个以内的错误率不超过 $10^{-11}$：
::::info[dp 代码及运行结果]
```cpp
f128 dp[11][1000005];
f128 qpow(f128 x, ll y) {
if (!y)
return 1;
else if (y & 1)
return x * qpow(x, y ^ 1);
else
return qpow(x * x, y >> 1);
}
f128 cal(ll n, ll m, ll k, ll w) {
dp[0][0] = 1;
f128 a = qpow(1 - f128(1) / m, k);
#define f(x) qpow(1 - qpow(a, x), k)
for (ll j = 1; j <= n; ++j)
dp[0][j] = dp[0][j - 1] * (1 - f(j));
for (ll i = 1; i <= w; ++i)
for (ll j = 1; j <= n; ++j)
dp[i][j] = dp[i][j - 1] * (1 - f(j)) + dp[i - 1][j - 1] * f(j);
f128 ret = 0;
for (ll i = 0; i <= w; ++i)
ret += dp[i][n];
return ret;
}
```
$$
\mathrm{cal}(10^6,32\times10^6,10,10)\approx0.\,999\,999\,999\,999\,999\,551\\
\mathrm{cal}(10^6-1,32\times10^6,10,9)\approx0.\,999\,999\,999\,999\,975\,383\\
\mathrm{cal}(10^5-1,32\times10^6,10,0)\approx0.\,999\,999\,999\,993\,000\,597
$$
::::
## 拓展性
我们对 hash 函数的要求只有均匀分布。所以前缀 hash 求区间 hash 值是可以做的（例题：求一个字符串里面有多少个本质不同指定长度的子串）。但是他只能用于各种判重，所以 sum hash / xor hash 等等和集合有关的不太用得上。
::::info[广告]
如果你和我一样省选没考上，可以考虑参加罗马尼亚的 [AGM](https://agm-contest.com/)，ICPC 赛制，预选赛和省选差不多时间，几乎没有有罗马尼亚之外的国家参加决赛所以只要你参加了预赛就可以作为国际选手参加暑假为期两天的线下决赛，那里人很好题目难度不高，前十有奖牌前三有奖金，今年这个比赛的 D1T11 就是开头的例题。
~~注意在当地吃饭找中国或日本餐馆，打车拿软件打街边很多黑车~~
::::