温馨提示: 豌豆仅提供国内节点,不提供境外节点,不能用于任何非法用途,不能访问境外网站及跨境联网。

免费领取1万IP!

Probability-Based Data Structure

发布时间:

基于概率的数据结构本质上是通过准确率来换取空间上的效率,这种 tradeoff 相比一般的算法并不多见,非常值得一提。

其实从数学的角度,概率数据结构非常简单而富有美感,感觉有时间我都想看看Probability and Computing: Randomized Algorithms and Probabilistic Analysis[1]了。

集合包含问题

Bloom Filter

在网上看到一位大神 Allen Sun 在 11 年的旧文[2]详细的介绍了布隆过滤器,不过我更多参考了维基百科的内容[3]

我们知道,如果哈希的位数减少,即哈希空间缩小,那么被碰撞的概率就会变大,哈希算法就会越来越不可靠。此时可能发生桶溢出(一般会使用拉链法形成链表)。假设我们并不在意完美的准确率,那么就不需要存储这个链表,只需要一个标志位,但此时正确的概率是

这个标志位,就是布隆过滤器的哈希桶。布隆过滤器的特别之处在于,它的哈希桶是被多个哈希函数共享的,这主要是为了提高准确度。只有在全部的哈希函数都判断正确时,布隆过滤器才会判定为存在。

Probability of false positives

熟悉机器学习的同学一定对 FP(假正例)很熟悉了。布隆过滤器的正确性可以通过一个不存在的元素被误判为存在来估计。而且布隆过滤器的特点之一,就是不存在 FN,因为已经存在的元素,必须被设置标记。为了满足这一点,我们很容易推断出一个必要条件:布隆过滤器不能进行删除操作

假设 k 个哈希函数的结果是相互独立的,位数组(哈希空间)有 m 位,已经插入的元素有 n 个。那么误判率为

这里可能第一个近似比较奇怪,因为在许多文章中都没有提到的是,尽管 k 个哈希函数独立,但对于 k 个位之间不独立。这是一个典型的抽屉问题,即将 n 个球放到 m 个抽屉。当一个球落在某个抽屉之后,它不可能再算入到其他抽屉的分母中。

这个公式成立的前提其实是

所以严格来说误判率应该是

上式的

可以看到,误判率只取决于 n 和 m 的比值,这里设为

因为

这就得到了为什么布隆过滤器中参数会包含

此时误判率为

这说明 k 取大约 m 和 n 比例的 0.7 倍左右时误差最小。换句话说,也可以看到布隆过滤器的理论极限其实还是取决于二者的比值,没有什么奇妙的魔法。如果比例只为 1:1 的话,这个误差率理论上不小于 60%。

k 也可以用

去重问题

去重计数(Count-Distinct Problem),或者说基数估计(Cardinality Estimation),对于数据量较小的情况,可以使用对每个对象(比如商品)维护一个动态查找结构,比如 B 树或者 Bitmap。但不论哪一种在海量数据中都会造成空间开销问题[4]

可以看到,基数估计和前面的集合包含从数学原理上十分接近。但是,集合包含不强调哈希本身空间的大小,也就是哈希码的长度。它的核心在于多个哈希函数之间的误差均摊。而基数估计基本上都是依赖于

Linear Counting

Linear Counting 算法的思想是用哈希桶被填充的数量来对基数 n 进行极大似然估计。显然,对于 m 个桶和 n 个基数(和数据本身大小无关),如果每个元素落在桶中的概率都是均匀的,那么可以得到[5]

其中 u 是最后为 0 的桶的个数。这里的等式其实和前面的布隆过滤器一样,并不是严格相等的。

可以看到这里求的实际上是最终的期望。根据中心极限定理,独立同分布的随机变量可以构成一个正态分布。而正态分布的最大似然估计即取观测值为样本的均值,这可以得到

Linear Counting 的误差和 u 的标准差有关。根据标准差定义:

这里

中间这步看的我有点头疼。我个人觉得你可以直接将这个标准差带入到 n 的公式中(设

最后 Linear Counting 的偏差值为

Linear Counting 和 bitmap 相比,只能得到常数x级别的空间降低。这也是算法中 linear 一词的体现。从公式上我们可以得到一个比较感性的认知:这一算法的估计只依赖于桶的数量。它的取值空间小于 m。这严重限制了算法的可用性。

关于 Linear Counting 算法,我也看到了其他人不错的总结[6]

LogLog

相比于 Linear Counting 进行桶映射,LogLog 摆脱了这个束缚。LogLog 的概率估计思想其实没有太大变化,但是参数变成了桶的位置。因为桶的位置是一种排列关系,它的取值空间远远大于桶的数量。这一算法的开创性工作来自于 Flajolet-Martin 算法[7]

LogLog 算法的基本思想是,统计所有基数得到的哈希值第一个出现1的位,然后求一个最高位。假设每个基数得到的哈希值第一个出现1的位是

为什么是这样计算?因为它相当于伯努利过程中不断投掷硬币直到为正面的次数。当尝试次数足够大时,这个概率总是可以无限降低的。从数学的角度也就是说

当然,如果只依赖于一个最大值,那么偶然性和误差太大了。直观想法当然首先是增加验证次数。不过,这相当于增加了

具体的无偏估计要复杂一些,可以参考原先的论文,或者是我参考的这篇系列文章[8]

具体的误差是

LogLog 算法的空间开销由划分数 m 以及基数 n 决定。从名字就可以知道这个算法的空间开销是

可以看到,LogLog 也是一种非常朴素的估计方法。它可以获得非常好的空间优化,但是在 n 较小时估计的误差较大。

Adaptive Counting

根据名字就可以猜到,这种算法是一种自适应的,结合了 LogLog 和 Linear Counting 的算法。前面可以看到,Linear Counting 算法随着 n 增大渐近的偏差变大,而 LogLog 则相反。这样可以取两个误差的平衡解:

这将得到

所以当空桶率大于这个阈值,选择 Linear Counting 算法;反之则选择 LogLog。

HyperLogLog

虽然引用数不如开天辟地的 FM-Sketch 算法,但是 HyperLogLog[9] 的应用确实极其广泛。HyperLogLog 使用了调和平均数

来弱化离群值(即 0)的影响——注意到之前这里计算的是算术平均数。这可以得到一个比 LogLog 更好的偏差估计

调和平均数可以比喻成一种路径上的速度,是一种变相的算术平均。如果给分子一个有意义的值,比如说把 1 看作是路径,那么调和平均数就是路径上每段平均速度得到的总平均速度[10]。可以看到,调和平均数始终小于算术平均数:

最后,一定要看一下这位大佬做的这个 PPT[11]。因为有许多大神珠玉在前,所以我只是简单的记录了一下大致的思路,配合食用为佳。

References


  1. book.douban.com/subject/205… ↩︎

  2. www.cnblogs.com/allensun/ar… ↩︎

  3. en.wikipedia.org/wiki/Bloom_… ↩︎

  4. blog.codinglabs.org/articles/al… ↩︎

  5. blog.codinglabs.org/articles/al… ↩︎

  6. blog.csdn.net/wbin233/art… ↩︎

  7. blog.codinglabs.org/articles/al… ↩︎

  8. Flajolet, Philippe; Martin, G. Nigel (1985). Probabilistic counting algorithms for data base applications ↩︎

  9. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm ↩︎

  10. www.jqr.com/article/000… ↩︎

  11. www.slideshare.net/KaiZhang130… ↩︎

相关文章


前端也来点算法(TypeScript版) | 2 - 回文数和回文链表 Dart 语言标准流与文件操作 React Hooks 你不来了解下? 用 Mongoose 插件记录Node.js API 日志

上一篇:React 中的状态自动保存(KeepAlive)
下一篇:网络协议的几个概念

咨询·合作