Hashing and Sketching

1 不同元素的个数

问题: 输入一系列(未必不同)的元素$x_1,x_2\cdots,x_n\in \Omega$, 输出不同元素的个数$z=|\{x_1,x_2,\cdots,x_n\}|$

通常算法需要维护字典结构, 需要至少$O(n)$空间, 现在想要更小的空间复杂度
$(\epsilon,\delta)$estimator:
若$Pr[(1-\epsilon)z\le \hat Z\le (1+\epsilon)z]\ge 1-\delta$, 则$\hat Z$是$z$的$(\epsilon, \delta)$估计;
若$\mathbb E[\hat Z]=z$则为无偏估计.

假设有理想的均匀随机哈希函数$h:\Omega \to [0,1]$
- 证明概要: 有$z$个均匀随机的哈希值, 将$[0,1]$分成$z+1$份, 根据对称性, 每个区间的长度期望相同, 因此最小的$h(x_i)$的期望就是$1/(z+1)$
这样估计太不稳定, 因为方差过大

适合数据流模型, 只需要存$k$个值
对于任意$\epsilon,\delta < 1/2$, 若$k\ge \lceil \frac{4}{\epsilon^2\delta}\rceil$, 则$\hat Z$是$z$的$(\epsilon,\delta)$估计
证明思路:
- 若$\bar Y$是$\frac{1}{1+z}$的$(\epsilon/2, \delta)$估计, 则$\hat Z$是$z$的$(\epsilon, \delta)$估计
- $\mathbb E[\bar Y] = \mathbb E[Y_j]=\frac{1}{z+1}$
- $Var[Y_j]\le \mathbb E[Y_j^2] = \frac{1}{(z+1)^2}$, 因此$Var[\bar Y]\le \frac{1}{k(z+1)^2}$
- 根据切比雪夫不等式, $Pr[|\bar Y-\mathbb E[\bar Y|>\frac{\epsilon/2}{z+1}]\le \frac{4}{\epsilon^2}(z+1)^2Var[\bar Y]\le \frac{4}{\epsilon^2k}$
- 因此取$k\ge \lceil \frac{4}{\epsilon^2\delta}\rceil$即可

$h_1,h_2,\cdots,h_k:\Omega\to[cn]$是独立的均匀随机哈希函数
数据结构建立
- 初始化布尔数列$A$的所有$cn$个bits为0
- 对于每一个$x\in S$, 令$A[h_i(x)]=1$, $1\le i\le k$
查询过程:
- 对于任意$x\in \Omega$, 如果对于所有$1\le i\le k$, $A[h_i(x)]=1$, 则回答”是”; 否则回答”否”.

空间: $cn$ bits, 时间: $O(k)$
没有假反例
假正例: $x\not\in S$但是对所有$1\le i\le k$都有$A[h_i(x)]=0$
- $\begin{aligned} Pr[wrong ~ answer ~ 'yes'] = &Pr[\forall 1\le i\le k, A[h_i(x)=1]]\\ &= Pr[A[h1(x)=1]]^k\\ &= (1-Pr[A[h_1(x)]=0])^k\\ &= (1-(1-\frac{1}{cn})^{kn})^k\\ &\approx (1-e^{-k/c})^k \end{aligned}$
- $k$取$c\ln 2$时结果为$(0.6185)^c$

问题: 对于一个序列$x_1,x_2,\cdots,x_n\in \Omega$, 查询$x$出现的次数$f_x$.

$h_1,h_2,\cdots,h_k:\Omega\to[m]$是独立的均匀随机哈希函数
数据结构建立(一个$k\times m$的整数数列$CMS$)
- 初始化布尔数列$CMS$的所有元素为0
- 对于每一个$x_i$, 令$CMS[j][h_j(x_i)]++$, $1\le j\le k$
查询过程:
- 对于任意$x\in \Omega$, 返回$\hat f_x=\min_{1\le j\le k}CMS[j][h_j(x)]$

空间$O(km)$, 每次查询时间$O(k)$
显然$CMS[j][h_j(x)]\ge f_x$, 因此$\hat f_x\ge f_x$
$Pr[|\hat f_x -f_x|\ge \epsilon n]=Pr[\hat f_x-f_x\ge \epsilon n]=\prod_{j=1}^k Pr[CMS[j][h_j(x)]-f_x\ge \epsilon n]$
对于任意$x\in \Omega$和$1\le j\le k$, 有$\mathbb E[CMS[j][h_j(x)]]\le f_x+\frac{n}{m}$ $\begin{aligned} \mathbb E[CMS[j][h_j(x)]] &=f_x+\sum_{y\in\{x_1,x_2,\cdots,x_n\}\setminus \{x\}}f_yPr[h_j(y)=h_j(x)]\\ &=f_x+\frac{1}{m}\sum_{y\in\{x_1,x_2,\cdots,x_n\}\setminus \{x\}}f_x\\ &\le f_x+\frac{1}{m}\sum_{y\in\{x_1,x_2,\cdots,x_n\}}f_x\\ &\le f_x+\frac{n}{m} \end{aligned}$
马尔科夫不等式得$Pr[CMS[j][h_j(x)]-f_x\ge \epsilon n]\le \frac{1}{\epsilon m}$
综上, $Pr[|\hat f_x -f_x|\le \frac{1}{(\epsilon m)^k}$
取$m=\lceil \frac{e}{\epsilon}\rceil$, $k=\lceil \ln \frac{1}{\delta}\rceil$, 则上述概率上界$\frac{1}{(\epsilon m)^k}\le \delta$