概率数据结构简介

在处理大型的数据集时,我们常常进行一些简单的检查,如稀有项(Unique items)的数量、最常见的项,以及数据集中是否存在某些指定的项。通常的做法是使用某种确定性的数据结构,如 HashSet(哈希集) 或 Hashtable(哈希表) 来达此目的。但是当我们所处理的数据集十分巨大时,这样的数据结构完全不可行,因为数据量太大,我们没有足够的存储空间。对于通常需要在一次传递(One pass)中处理数据并执行增量更新的流媒体应用(Streaming application)来说,这就变得更加困难。

概率数据结构(Probabilistic data structures)是一组数据结构,它们对于大数据和流式应用来说非常有用。一般而言,这类数据结构使用哈希函数(Hash function)来随机化并紧凑地表示一个项的集合。忽略掉碰撞(Collision)的情况,但错误可以在一定的阈值下得到很好的控制。与无错方法相比,这些算法使用的内存更少,并且具有常数级的查询时间复杂度。他们通常支持并集(Union)和交集(Intersection)操作,因此可以很容易地使其并行化。

本文将介绍三种常用的概率数据结构:Bloom filter(布隆过滤器),HyperLogLog(基数估计法),以及 Count-Min sketch(最小略图)。

成员关系查询 —— Bloom filter

Bloom filter 是具有 m 个数位的位阵列(Bit array),每一个数位被初始化为 0。要添加一个元素,则先将其流入 k 个哈希函数,以获取 k 个阵列位置,并将这些位置对应的数位设置为 1。查询某元素时,将其流入 k 个哈希函数来获得 k 个阵列位置。如果这些位置中有任何一个 0,则该元素必定不在该集合中。如果这些位全部为 1,那么该元素可能在该集合中。无论元素的大小如何,每个元素仅需要有 9.6 个位,就能使 Bloom filter 具有 1% 的低误报率(False positive rate)。

例如,如果我们将 x,y,z 添加到 Bloom filter 中,并使用 3 个哈希函数(即 k = 3),如上图所示。这三个元素,每一个都在位阵列中有三个位,每个位都设置为 1。当我们在集合中查找 w 时,由于其中一个比特未被设置为 1,Bloom filter 会告诉我们它不在集合中。

Bloom filter 具有以下特性:

  • 当查询的位置都已经设​​置为 1 时,可能出现误报。但是,错误否定(False negative,在此处表示对于 “不在集合中” 的错误判定)是不可能的。
  • 查询时间是 O(k)。
  • 具有相同大小和散列函数的 Bloom filter 的并集和交集操作,可以通过按位 OR 和 AND 操作来实现。
  • 无法从集合中删除元素。

布隆过滤器需要以下几种输入:

m:位阵列的大小

n:预计要插入的元素数量(插入次数)

p:误报率

使用以下公式可以确定哈希函数的最佳数量 k:

给定误报率 p 和预计的插入次数 n,位阵列的长度可以通过下式计算:

通常用于 Bloom filter 的哈希函数应该比具有良好分布和抗碰撞性的加密哈希算法更快。Bloom filter 常用的哈希函数包括 Murmur 哈希函数,fnv 的一系列哈希函数,以及 Jenkins 哈希函数。Murmur 哈希是其中最快的。谷歌在其 Guava 库中实现的 Bloom filter 使用了 MurmurHash3。

基数 —— HyperLogLog

HyperLogLog 是一种流式算法,用于估算极大型数据集中不同元素(基数)的数量。HyperLogLog 计数器可以仅使用 1.5KB 的内存计算出 10 亿个不同的项,同时其精确度为 2%。该算法基于位模式观察(Bit pattern observation),对于随机分布的数字流,若有一个数字 x ,它具有最多的 k 个前导位 0,则流的基数很可能等于 2^k。

对于流中的每个元素 si,使用哈希函数 h(si) si 转换为随机比特串(0 或 1,概率为 1/2):

位模式的概率 P 则如下

0xxxx ...→P = 1/2

01xxx ...→P = 1/4

001xx ...→P = 1/8

当我们看到前缀为 0k 1 ... 时,直觉告诉我们,这很可能有 n≥2^(k+1) 个不同的字符串。通过跟踪出现在数据流中的前缀 0k 1 ...,我们可以估计其基数为 2^p,其中 p 是最大前缀的长度。由于使用单个计数器时方差非常高,为了获得更好的估计,我们使用哈希值的前几位将数据拆分为 m 个子流。计数器分别由 m 个寄存器维护,其中每个寄存器具有 4 字节的倍数大小的存储空间。如果每个子流的标准偏差为 σ,则平均值的标准偏差仅为 σ/√m。这被称为随机平均(Stochastic averaging)。

例如,对于m = 4,

使用前两位(00,01,10,11)将元素分成 m 个流,然后将其丢弃。每个寄存器存储包含最大 0k 1 前缀的其余哈希比特。然后将 m 个寄存器中的值平均起来以获得基数估计。

HyperLogLog 算法使用调和均值(Harmonic mean)来将结果归一化。该算法还可以根据小的值与非常大的值进行调整。由此产生的误差等于 1.04 /√m

当需要估计的基数小于等于 n 时,m 个寄存器中的任一个最多使用 log2(log2(n)) + O(1) 个比特位。

要计算两个 HyperLogLog 计数器的并集,可以先计算出每个计数器中的 m 个寄存器,将不同计数器的寄存器进行比较并取最大值,然后再计算估计的基数。

频率 —— Count-Min Sketch

Count-Min Sketch 是概率子线性空间流算法。它与 Bloom filter 在某种程度上是相似的。它们的主要区别在于,Bloom filter 用位图来表示一个集合,而 Count-Min Sketch 则用位图来表示一个保存了频率分布概况的多重集(Multi-set)。其基本数据结构是一个二维的 (d * w) 计数器阵列,它具有 d 个两两独立的哈希函数 h1 ... hd,它们的值域都在 w 内。给定参数(ε,δ),令 w = [e /ε]d = [ln1 / δ]ε 是我们想要的准确度,δ 是我们达到准确度的确定性(Certainty)。二维数组由 wd 计数组成。要增加计数,则需使用 d 个哈希函数计算哈希位置,并更新这些位置的计数。

项的计数估计值是由 d 个哈希函数所确定的阵列位置处的最小计数值。

Count-Min Sketch 使用的空间是 w * d 个计数器的数组。通过选择合适的 d 和 w 值,可以实现非常小的误差和高概率。

不同错误和概率组合的 Count-Min Sketch 尺寸示例:

ε

1 - δ

w

d

wd

0.1

0.9

28

3

84

0.1

0.99

28

5

140

0.1

0.999

28

7

196

0.01

0.9

272

3

816

0.01

0.99

272

5

1360

0.01

0.999

272

7

1940

0.001

0.999

2719

7

19033

Count-Min Sketch 具有以下特性:

  • 并集可以通过按位的 ADD 操作实现
  • O(k) 的查询时间复杂度
  • 频率越高的项(比如 Heavy hitters,大流量对象),其准确度越高
  • 只会造成重复计算,但不会计算不足(即频率值不会偏低)

Count-Min Sketch 可用于查询单个项的计数或 “Heavy hitters”(可通过保留所有计数的堆结构来获得)。

总结

概率数据结构在现代网络和数据应用程序中已经有了许多应用,这些应用中的数据以流的方式到达,并且需要使用有限的内存进行即时处理。Bloom filter,HyperLogLog 和 Count-Min Sketch 是最为常用的概率数据结构。对于各种流媒体算法、概要数据结构(Synopsis data structure)和优化技术已经有很多相关的研究,这些都值得我们去学习学习。

如果您还没有尝试过这些数据结构,那么一旦您开始使用它们,您会惊奇地发现它们有多么强大。刚开始时,理解它们的概念可能有些吓人,但实际上,要实现它们非常简单。Google Guava 使用 Murmur 哈希来实现了 Bloom filter。Clearspring 的 Java 库 stream-lib,以及 Twitter 的 Scala 库 Algebird 已经实现了所有的这三种数据结构和其他有用的数据结构,您可以通过这些库来使用它们。我已经把相应的链接列在下面。

相关链接:

本文的版权归 StoneDemo 所有,如需转载请联系作者。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C语言及其他语言

【每日一题】问题 1102: 明明的随机数

题目描述 明明想在学校中请一些同学一起做一项问卷调查,为了实验的客观性,他先用计算机生成了N个1到1000之间的随机整数(N≤100),对于其中重复的数字,只...

2869
来自专栏哈雷彗星撞地球

算法之路(一)----求最大子序列

对于IT行业者来说,刚参加工作,还能找点借口,说自己不擅长算法。可是工作三年以上的IT开发者,还说自己不会算法,不会设计模式就说不过去了。所以最近开始撸算法和设...

1153
来自专栏逸鹏说道

码农眼中的数学之~数学基础

写在前面:文章里面的图片公式都是逆天一个个打出来画出来的,公式系列基本上都提供了源码

2117
来自专栏ACM算法日常

海战(线段树)- HDU 4027

这一篇是典型的线段树算法,这个算法在日常工作中可能非常少见,因为可以被常规算法所取代,但是在问题达到一定数量级之后,常规算法是很难搞定类似问题的...

1042
来自专栏聊聊技术

原 初学数模-MATLAB Quick S

4619
来自专栏ACM算法日常

基础算法系列之排序算法-2.冒泡排序

上篇文章给大家讲述了二分查找算法,现在让我们来一起学习另一个基础算法——冒泡排序算法。它是一个排序算法,可以将一个无序的序列排成有序。它将会是我们以后...

853
来自专栏程序生活

卡特兰数简介原理性质应用参考:

简介 卡特兰数又称卡塔兰数,卡特兰数是组合数学中一个常出现在各种计数问题中的数列。 卡塔兰数的一般项公式为: ? 卡特兰公式 其前20项为:1, 1, 2, ...

3724
来自专栏Leetcode名企之路

【Leetcode】54. 螺旋矩阵

给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。 示例 1:

1372
来自专栏程序员宝库

LCS 算法:Javascript 最长公共子序列

作者:司徒正美 链接:https://segmentfault.com/a/1190000012864957 最长公共子序列(Longest Common Su...

60510
来自专栏懒人开发

(1.1)James Stewart Calculus 5th Edition:Four Ways to Represent a Function

一个曲线,在竖直方向,如果对应的一个x值和曲线相交不止一次,就不是一个函数。(其实可以理解成,上面说的,每个 A集合的元素,都有且有一个B集合中的元素和他对应)

1103

扫码关注云+社区

领取腾讯云代金券