宣威市住房和城乡建设局网站下载中心,广西城乡建设名网站,一个合格的网站设计,专业建设信息化网站资源文章目录BloomFilter简单介绍BloomFilter中的数学知识fpp(误判率/假阳性)的计算k的最小值公式总结编程语言实现golang的实现[已知n, p求m和k](https://github.com/bits-and-blooms/bloom/blob/master/bloom.go#L133)参考BloomFilter简单介绍
BloomFilter我们可能经常听到也在使…
文章目录BloomFilter简单介绍BloomFilter中的数学知识fpp(误判率/假阳性)的计算k的最小值公式总结编程语言实现golang的实现[已知n, p求m和k](https://github.com/bits-and-blooms/bloom/blob/master/bloom.go#L133)参考BloomFilter简单介绍
BloomFilter我们可能经常听到也在使用, 它的特点是如果判断结果为不存在, 则一定不存在; 如果判断为存在, 则可能存在. 如下图示例说明当我们判断z元素存在时, 其实是不存在的, 即存在有概率性.
如上图, 长为m16的二进制向量, 初始全为0; k3(即添加一个元素需要将3个bit设置为1), 对n3个元素进行添加操作.
BloomFilter几个关键量定义: m: 二进制向量大小(多少个二进制位) n: 要存放的元素个数 k: 哈希函数的个数, 或者说每添加一个元素都要进行k次计算 fpp或者简写为p: 误判率(false positive rate), 即 使用bloomfilter判断为存在时, 但实际不存在的概率
BloomFilter中的数学知识
fpp(误判率/假阳性)的计算
BloomFilter主要的数学原理是: 在某一范围内(1xm)1xm)1xm)(x为整数, m通常是很大的, 如106级别10^6级别106级别), 任意选取两个整数i,j,i和j可重复选取i, j, i和j可重复选取i,j,i和j可重复选取, 则其相等的概率是非常小的: mm21m\dfrac{m}{m^2}\dfrac{1}{m}m2mm1
我们假定hash计算是均匀的, 即每次hash会随机地将m位中的一位设置为1. 那么:
一次hash计算(如h1(x)h1(x)h1(x))后, 任一位被 置为1 的概率为: 1m\dfrac{1}{m}m1一次hash计算(如h1(x)h1(x)h1(x))后, 任一位 还是0(即未被置为1) 的概率为: 1−1m1 - \dfrac{1}{m}1−m1添加一个元素(如bloomFilter.Add(x), 即执行k次hash)后, 任一位还是0的概率为: (1−1m)k(1 - \dfrac{1}{m})^k(1−m1)k添加n个元素后(如上图中的n3个元素:x,y,z), 任一位还是0的概率为: (1−1m)kn(1 - \dfrac{1}{m})^{kn}(1−m1)kn , 任一位为1的概率为 1−(1−1m)kn1- (1 - \dfrac{1}{m})^{kn}1−(1−m1)kn如果将1个新的元素添加到已存在n个元素的BloomFilter中则任一位已经为1的概率与上面相同为1−(1−1m)kn1- (1 - \dfrac{1}{m})^{kn}1−(1−m1)kn . 那么添加这个新元素时, k个比特都为1(相当于新元素和已有元素已经分不清了)的概率(此即为新插入元素的误识别率)为 p[1−(1−1m)kn]kp [1- (1 - \dfrac{1}{m})^{kn}]^{k} p[1−(1−m1)kn]k
通常来说, m是一个非常大的数(1MiB内存就有220×8≈800万2^{20}\times{8}\approx 800万220×8≈800万个bit), 并且我们有: limx→∞(1x)1xe{ \lim\limits_{x \to \infin} (1x)^{\frac{1}{x}} e}x→∞lim(1x)x1e 那么在工程实践中, 可以认为p的近似值为: p[1−(1−1m)kn]k[1−(1−1m)−m×−knm]k≈(1−e−knm)k(当m很大时,将−1m看作x)\begin{aligned} p [1- (1 - \dfrac{1}{m})^{kn}]^{k} \\ [1- (1 - \dfrac{1}{m})^{-m\times\frac{-kn}{m}}]^{k} \\ \approx (1-e^{-\frac{kn}{m}})^{k} \enspace (当m很大时, 将 -\dfrac{1}{m}看 作x) \end{aligned} p[1−(1−m1)kn]k[1−(1−m1)−m×m−kn]k≈(1−e−mkn)k(当m很大时,将−m1看作x)
k的最小值
计算过程参考: https://cs.stackexchange.com/questions/132088/how-is-the-optimal-number-of-hashes-is-derived-in-bloom-filter
已经遗忘的知识:
求导公式: (lnx)′1x(\ln{x})^{} \dfrac{1}{x}(lnx)′x1求导公式: (enx)′nenx(\bold{e}^{nx})^{} n\bold{e}^{nx}(enx)′nenx
在某些情况下, 我们对n, m, 的值可以给一个估算值, 以此来获得最小的p(即尽可能准确判断), 那么k就是一个变量了, 问题就变为求 (1−e−knm)k(1-e^{-\frac{kn}{m}})^{k}(1−e−mkn)k的最小值. 令f(k)(1−e−knm)kf(k)(1-e^{-\frac{kn}{m}})^{k}f(k)(1−e−mkn)k, 那么 两边取对数有:lnf(k)ln(1−e−knm)kkln(1−e−knm)设g(k)kln(1−e−knm),那么:g′(k)ln(1−e−knm)knme−knm1−e−knm令xe−knm,x∈(0,1),那么有h(x)ln(1−x)−x1−xlnx(注意k用−mnlnx替换)(1−x)ln(1−x)−xlnx1−x(x∈0,1)\begin{aligned} 两边取对数有: \\ \ln f(k)\ln (1-e^{-\frac{kn}{m}})^{k} k \ln(1-e^{-\frac{kn}{m}}) \\ 设 g(k) k\ln{(1-e^{-\frac{kn}{m}})}, 那么:\\ g{}(k) \ln{(1-e^{-\frac{kn}{m}})} k\dfrac{\frac{n}{m}e^{-\frac{kn}{m}}}{1-e^{-\frac{kn}{m}}} \enspace \\ 令 x e^{-\frac{kn}{m}}, x \in(0, 1), 那么有 \\ h(x) \ln(1-x) - \dfrac{x}{1-x} \ln x \enspace (注意k用-\dfrac{m}{n}lnx替换) \\ \enspace \enspace \enspace \enspace \dfrac{(1-x) \ln(1-x)-x \ln x}{1-x} \enspace (x\in{0, 1}) \end{aligned} 两边取对数有:lnf(k)ln(1−e−mkn)kkln(1−e−mkn)设g(k)kln(1−e−mkn),那么:g′(k)ln(1−e−mkn)k1−e−mknmne−mkn令xe−mkn,x∈(0,1),那么有h(x)ln(1−x)−1−xxlnx(注意k用−nmlnx替换)1−x(1−x)ln(1−x)−xlnx(x∈0,1)
对 h(x)(1−x)ln(1−x)−xlnx1−x(x∈0,1)h(x) \dfrac{(1-x)\ln(1-x)-x \ln x}{1-x} \enspace (x\in{0, 1})h(x)1−x(1−x)ln(1−x)−xlnx(x∈0,1), 不难看出:
当x12时,h(x)0x\dfrac{1}{2}时, h(x)0x21时,h(x)0当x12时,h(x)0x\dfrac{1}{2}时,h(x)0x21时,h(x)0当x12时,h(x)0x\dfrac{1}{2}时,h(x)0x21时,h(x)0
站在巨人的肩膀上, 我们可以直接在这里看: 显然在x∈(0,1)范围内,当x0.5时,h(x)最小x\in(0, 1)范围内, 当x0.5时, h(x)最小x∈(0,1)范围内,当x0.5时,h(x)最小, 此时kmnln2k\dfrac{m}{n}ln2knmln2 也就是说: 当kmnln2k \dfrac{m}{n}ln2knmln2时(想象k非常接近0), xe−knmx e^{-\frac{kn}{m}}xe−mkn会非常接近1, 此时x12x\dfrac{1}{2}x21, h(x)0h(x)0h(x)0 ⇒ f(k)在变小; 当kmnln2k \dfrac{m}{n}ln2knmln2时(想象k非常接近0), xe−knmx e^{-\frac{kn}{m}}xe−mkn会非常接近0, 此时x12x\dfrac{1}{2}x21, h(x)0h(x)0h(x)0 ⇒ f(k)在变大; 所以kmnln2k\dfrac{m}{n}ln2knmln2时会使得f(k)f(k)f(k)最小, 即此时p最小.
公式总结
误判率公式: p[1−(1−1m)kn]kp [1- (1 - \dfrac{1}{m})^{kn}]^{k}p[1−(1−m1)kn]k误判率近似公式(当m很大时): p≈(1−e−knm)kp \approx (1-e^{-\frac{kn}{m}})^{k}p≈(1−e−mkn)k已知m, n, k的最小值(近似)为: kmnln2≈0.7mnk\dfrac{m}{n}\ln{2} \approx 0.7\dfrac{m}{n}knmln2≈0.7nm已知n, p, 且k取最小时, m−nlnp(ln2)2m-\dfrac{n\ln{p}}{(ln2)^{2}}m−(ln2)2nlnp
编程语言实现
golang的实现
https://github.com/bits-and-blooms/bloom
已知n, p求m和k
func EstimateParameters(n uint, p float64) (m uint, k uint) {m uint(math.Ceil(-1 * float64(n) * math.Log(p) / math.Pow(math.Log(2), 2)))k uint(math.Ceil(math.Log(2) * float64(m) / float64(n)))return
}参考
https://en.wikipedia.org/wiki/Bloom_filterhttps://cs.stackexchange.com/questions/132088/how-is-the-optimal-number-of-hashes-is-derived-in-bloom-filter
(完)
