Bloom Filters Count-Min Sketch

本文主要是介绍Bloom Filters Count-Min Sketch，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

今日看了两个基于概率的数据结构（Probabilistic data structures）
Bloom Filters 和 Count-Min Sketch，基本思想相类似。

其实是两个实现简单的算法，但是需要用到一定的数学原理。

但本文仅介绍方法，不介绍数学原理。

Bloom Filters

问给出的数是否在集合 $S$ 中，集合可增可删，且集合中数的取值范围 $w$ 较大，设 $w\le 10^{18}$。

简单版

通过哈希函数 $H$，对于给定的数 $x$，将 $y=H(x)$（比如 $y\le 10^5）$，存在 bitset 中，通过 0/1 来表示是否在 $S$ 中出现，这样可以极大的节省空间。

升级版

根据生日攻击原理，我们可以知道，当 $|S|$ 较大时，会有较大的概率产生冲突。

所以考虑使用多个哈希函数 $H_k$。

则对于集合 $S$ 中的数 $x$， $\forall i\le k,y_i=H_k(x)$，则令 $bitset[y_i]=1$。

若要判断 $x$ 是否在 $S$ 中，则要求 $\forall i\le k,y_i=H_k(x)$，$bitset[y_i]=1$。

此网址下有演示 demo。

可删除

如果想要删除的话，为了避免两个不同的数相互干扰，我们改成计数版本。

即：

则每添加一个数 $x$， $\forall i\le k,y_i=H_k(x)$，则令 $bitset[y_i]+=1$。

如要删除一个数 $x$，则 $\forall i\le k,y_i=H_k(x)$，则令 $bitset[y_i]-=1$。

Count-Min Sketch

问给出的数是否在可重集合 $S$ 中，集合可增可删，且集合中数的取值范围 $w$ 较大，设 $w\le 10^{18}$。

简单版

同 Bloom Filters 类似，通过哈希函数 $H$，对于给定的数 $x$，将 $y=H(x)$（比如 $y\le 10^5）$，存在数组 $A[y]$ 中，通过 $A[y]$ 的值来得出在 $S$ 中出现的次数，这样可以极大的节省空间。

升级版

根据生日攻击原理，同理。

所以考虑使用多个哈希函数 $H_k$。

设使用了 $k$ 个，则我们定义一个二维数组 $A[k][]$。

则对于集合 $S$ 中的数 $x$， $\forall i\le k,y_i=H_k(x)$，则令 $A[i][y_i]++$。

若要求得 $x$ 在 $S$ 中的出现次数，则为

$$\underset{i\le k,y_i=H_i(x)}{\min }A[i][y_i]$$。

此网址下有演示 demo。

这篇关于Bloom Filters Count-Min Sketch的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---