Hashing
1.Count Distinct Elements(可以解决莎士比亚文章中出现了多少个不同的词)
问题
Input：一个$x_1,x_2,x_3,…,x_n \in Q$的集合
Ouput：估计这个集合不同元素的个数 $z = |{x_1,x_2,…,x_n}| $
Uniform hash function $h: \Omega \rightarrow [0,1]$
用一个hash函数将x集合根据均匀分布映射到[0,1]的实数区间内。
$h(x_1),…,h(x_n): $z uniform independent values in [0,1]（因为有z个不同的元素，所以可以将这个区间划分成z+1块区域,h(x)表示当前点x映射到[0,1]的实数)
$$
X = min_{1 \le i \le n}{h(x_i)} \\
F(X) = P[X \ge x] = (1-x)^z \\
E[X] = \int_0^1{xP(x)}dx = \int_0^1{F(x)}dx = \frac {1}{z+1}(1-x)^{z+1}|_0^1 = \frac {1}{z+1}
$$
根据期望可知，$\hat Z = 1/min_ih(x_i)-1$，但这样得到的方差太大了，也就是计算的结果分布在标准答案之间不集中，很难将误差率降到$\delta$，尤其是z=1的时候。
方法：可以构建K个独立不同的hash映射，将x集合映射到[0,1]区间上：
Uniform independent hash functions:
$h_1,h_2,…,h_k: \Omega \rightarrow [0,1] \quad Y_j = min_{1 \le i \le n}h_j(x_i)$
average-min : $\bar Y = \frac{1}{k} \sum_{j=1}^k{Y_j}$
Flajolet-Martin estimator: $\hat Z = \frac{1}{\bar Y} - 1$
随即进行k次，因为均是独立的，所以期望的结果是不会改变的，但是方差是一定会降低的。
且我们希望将误差率降到$\delta$下，误差忍受系数$\varepsilon$，就希望求解
$$
Pr[\hat Z \lt (1-\varepsilon)z \space or \space \hat Z \gt (1+\varepsilon)z] < ?
$$
$$
Pr[\hat Z \lt (1-\varepsilon)z \space or \space \hat Z \gt (1+\varepsilon)z] = Pr[|\bar Y - E[\bar Y]| \le \frac{\varepsilon / 2}{z+1}] \\
$$
根据切比雪夫不等式（chebyshev不等式可由Markov’s Inequality证得）可知：
$$
\begin{aligned}
Pr[|\bar Y - E[\bar Y]| \le \frac{\varepsilon / 2}{z+1}] & = \frac{Var[\bar Y]∗(z+1)^2∗4}{\varepsilon^2} \\
Var[Y_i] & = E[\bar Y_i ^ 2] - E[\bar Y_i]^2 \
& = \int_0^1{y^2F^{‘}(Y)dy} - \frac{1}{(z+1)^2} \\
& = \int_0^1{y^2z(1-y)^{z-1}dy} - \frac{1}{(z+1)^2} \\
& = \frac{2}{(z+1)∗(z+2)} - \frac{1}{(z+1)^2} \\
& \le \frac{1}{(z+1)^2} \\
Var[\bar Y] = \frac{1}{k^2} \sum_{i=1}^{k}{Var[Y_i]} & \le \frac{1}{k(z+1)^2}
\end{aligned}
$$
将上述式子结合可得
$$
Pr[|\bar Y - E[\bar Y]| \le \frac{\varepsilon / 2}{z+1}] \le 4/(k \varepsilon^2) \le \delta
$$
所以choose $ k = \frac{4}{\varepsilon^2 \delta} $ .
2.Approximate a Set
问题
Input: a set S of n items $x_1,x_2,…,x_n \in \Omega$
Ouput: Determine whether $x \in S$
问题性质
这个问题的数据是可以以数据流的形式进入的
用bit位表示占用空间的单位
根据信息熵的计算可知精确解决问题要占用的空间至少： $O(nlog|\Omega|)$
对于询问的处理时间上来说：
1.平衡树，占用空间$O(nlog|\Omega|)$，每次查询占用时间$O(logn)$
2.perfect hashing: 占用空间$O(nlog|\Omega|)$，每次查询占用时间O(1)
如果空间占用<信息上？得到的就是一个近似解
在空间占用过大，需要利用近似解解决问题的时候，我们总是希望将错误率控制在$\delta$范围内。
navie解决办法
uniform hash function $h:\Omega \rightarrow [m]$
data structure : an m-bit vector $v \in \{0,1\}^m $
initially v is all-0; 初始将所有位置设置为0
set $v[h(x_i)]=1$ for each $x_i \in S$; 每次进入一个值，就将对应hash的位置设置为0
query x: answer “yes” if v[h(x)]=1; 如果hash到的位置已经被标记了1说明这个x出现在集合中
我们总是考虑出错的状态：
$x \not\in S$ $Pr[v[h(x)]=1] = 1-(1-1/m)^n = 1-e^{-n/m}$
上述式子的解释是对于x来说，hash满足均匀分布，所以它和每一个$x_i$在不同的情况下hash对应的数值概率相同的条件应该也是满足均匀分布的，且x和任何一个$x_i$得到的hash值不同每一个事件都是独立事件
$Pr[h(x) != h(x_i)] = 1-1/m$
$Pr[\bigwedge_i \space (h(x) != h(x_i))] = \prod_{i=1}^n{Pr[h(x) != h(x_i)]} = (1-1/m)^n$
这个错误率太高了
进而发展出Bloom Filters
Bloom Filters解决办法
Uniform independent hash functions
$h_1,h_2,…,h_k: \Omega \rightarrow [m]$
Data structure: an m-bit vector $v \in \{0,1\}^m$
initially v is all-0;
for each $x_i \in S$: set $v[h_j(x_i)]=1$ for all j=1,2,…,k;
Query x: “yes” if $v[h_j(x_i)]=1$ for all j=1,2,…,k;
对于每一个数来说，都经过了k次hash，那么在x不属于集合，但是所有hash结果为1导致判断正确的概率计算如下：
$Pr[h_1(x) != h_j(x_i)] = 1-1/m$
$Pr[\bigwedge_j h_1(x) != h_j(x_i)] \\= Pr[h_1(x) != h_1(x_i)] ∗ Pr[h_1(x) != h_2(x_i)] ∗…∗Pr[h_1(x) != h_k(x_i)] \ = (1-1/m)^k$
$Pr[\bigwedge_i (\bigwedge_j h_1(x) != h_j(x_i))] \\= Pr[\bigwedge_j h_1(x) != h_j(x_i)]^n \ = (1-1/m)^{kn}$
那么x每一个hash的位置判断错误（在当前hash对应到值为1的bit，因为x不属于集合，所以是错的）的概率是$1-(1-1/m)^{kn}$总共有k次独立的hash，所以错误率为
$((1-1/m)^{kn})^k = (1-e^{-kn/m})^k \approx (0.6185)^c$ （这里选定$k=\frac{mln2}{n}$ , $m=cn$)
3.Count-Min Sketch
问题
Data: a sequence $x_1,x_2,…,x_n \in Q$
Query: an item $x \in Q$ , estimate the frenquency $f_x=|{i: x_i = x}|$ of item x within additive error $\varepsilon n$
问题性质
数据是以数据流的形式进入的
$\hat{f_x}$: estimation of frequency $f_x$
$Pr[|\hat {f_x} - f_x| \ge \varepsilon n] \le \delta $
解决方法
uniform independent hash functions
$h_1,h_2,…,h_k : \Omega \rightarrow [m]$
Count-min sketch: CMS[k][m]
initially CMS[][] is all-0;
for each $x_i$ and each $h_j$： $CMS[j][h_j(x_i)]++$;
Query x: return $\hat {f_x} = min_{1 \le j \le k} CMS[j][h_j(x)]$
这个方法很显然得到的$\hat {f_x} >f_x$.
$$
\begin{aligned}
E[CMS[j][h_j(x)]] & = f_x + \sum_{y \in \{x_1,x_2,…,x_n\} \setminus \{x\}} {f_yPr[h(y) = h(x)]} \\
& = f_x+\frac{1}{m} \sum_{y \in \{x_1,x_2,…,x_n\} \setminus \{x\}} {f_y} \\
& \le f_x + \frac{1}{m} \sum_{y \in \{x_1,x_2,…,x_n\}} {f_y} \\
& = f_x + n/m
\end{aligned}
$$
那么这里n/m就是估计偏差(biased estimator)
$$
\begin{aligned}
& Pr[CMS[j][h_j(x)] -f_x \ge \varepsilon n] = \Pr[n/m \ge \varepsilon n] \le 1/(\varepsilon m) \\
& Pr[\forall _j CMS[j][h_j(x)]-f_x \ge \varepsilon n] = (Pr[CMS[j][h_j(x)] -f_x \ge \varepsilon n])^k \le (\varepsilon m)^{-k} \le \delta
\end{aligned}
$$
根据我们设置的误差和可以接受的错误率，我们应该将$m = \left\lceil ln \frac{e}{\varepsilon} \right\rceil$ , $k=\left\lceil ln \frac{1}{\delta} \right\rceil$
- Space cost: $km = O(\frac{1}{\varepsilon}ln \frac{1}{\delta})$
- Time cost for each query: $k = O(ln \frac{1}{\delta})$
4.完美Hash函数
Perfect Hash function，简称PHF，这是一个没有冲突的hash函数，hash函数将N个key值映射到M个数上，M>=N，且保证任意的Key1,key2，都不会存在hash(Key1) = hash(Key2)的情况。完美哈希函数是静态的，就意味着事前必须知道需要哈希哪些数据。同时生成的算法比较复杂，需要很长的时间来建立索引。没有办法实时添加更新。给他的应用范围提了个极大的限制。
