高级算法之哈希

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$则为无偏估计.

1.1 哈希估计器

  • 假设有理想的均匀随机哈希函数$h:\Omega \to [0,1]$

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

1.2 Flajolet-Martin算法

  • $h_1,h_2,\cdots,h_k: \Omega\to [0,1]$是k个均匀独立随机哈希函数
  • 扫描一遍所有$x$, 计算$Y_j=\min_{1\le i\le n}h_j(x_i)$, $j=1,2,\cdots,k$
  • 计算$Y_j$平均值$\bar Y$
  • $\hat Z=\frac{1}{\bar Y}-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$即可

1.3 均匀哈希假设UHA

  • 均匀随机函数$h: [N]\to[M]$是可获得的, 并且计算高效

2 集合元素

  • 基础问题: 是否$x\in S$ ? (S的大小为n)
  • 数据的有损失的表达称为sketch

2.1 Bloom filter

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

    • $k$取$c\ln 2$时结果为$(0.6185)^c$

3 频率估计

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

  • 需要一个加法误差而不是乘法误差($Pr[|\hat f_x-f_x|\le \epsilon n]\ge 1-\delta$)

3.1 Count-min sketch

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

  • 对于任意$x\in \Omega$和$1\le j\le k$, 有$\mathbb E[CMS[j][h_j(x)]]\le f_x+\frac{n}{m}$

  • 马尔科夫不等式得$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$