概率数据结构
- 概率数据结构
概率数据结构
散列 Hashing
生成固定大小的标识符(
hash
)散列碰撞(hash collisions)
: 两个不同的数据块具有相同散列值
加密散列函数
加密散列函数为了保证抗碰撞性, 所以牺牲了一部分性能, 效率低于非加密散列函数: 加密散列速度约540MiB/s, 非加密约2500MiB/s。
消息-摘要算法 (Message–Digest Algorithms) MD5
安全散列算法 (Secure Hash Algorithms) SHA-2(SHA-224, SHA-256, SHA-384, SHA-512等)
RadioGatún: 比SHA-2快
非加密散列函数
Fowler/Noll/Vo (FNV): 基于素数
MurmurHash: 当下最流行的算法, 用于Hadoop, ES, nginx等
CityHash与FarmHash: google开发的算法, 依赖于平台。
散列表
负载因子α
: 使用的键数量n与表总长m的比值, 是散列表填充程度的度量。
散列表解决碰撞问题主要有两种技术:
封闭寻址: 将碰撞元素存储在辅助数据结构中的相同键下, 最简单
开放寻址: 将碰撞元素存储在首位以外的其他位置, 并提供一种寻址方法
成员查询 Membership querying
确定某个元素是否属于该数据集。
不需要确定的匹配, 只需要只到在不在集合中, 所以可以只存储元素的签名
兼顾存储效率和查询速率
用散列表存储, 容易出现散列碰撞, 且对大数据来说存储压力依然大, 所以需要新的替代算法。
布隆过滤器 Bloom Filter
最简单最知名的成员查询解决方案
常用
比特数组
来表示元素集合只支持
添加元素
和测试元素是否属于集合
两种操作散列函数要尽量相互独立且服从均匀分布
用构建过滤器的散列函数计算
y
的散列值: \(j=h_k(y)\)判断如果
BLOOMFILTER[j] != 1
, 则表示元素不存在
如果散列函数\(h_k\)能够在固定时间中算出, 则添加和判断元素的时间为固定常数\(O(k)\), 而不受过滤器长度和元素数目的限制。
高度依赖散列函数, 越均匀, 计算越快的越好。
由于散列碰撞, 判断为不存在的元素一定不存在, 但判断为存在的元素有概率误判。
m
,含k
个散列函数的布隆过滤器BloomFilter
输出: 过滤器中不同元素的个数 伪代码: N = count([ BLOOMFILTER[j]=1 for j in 1:m ])
if N<k then
return 0
elseif N==k then
return 1
elseif N==m then
return m/k
else
return -(m/k)*ln(1-N/m)
end
估算长度算法背后的原理:
布隆过滤器的假阳性率
P_{fp}
可以由公式\(P_{fp} ≈ (1-e^{-kn/m})^k\) 估算,取决于k和m的选择过滤器长度由公式\(m = - n*ln(P_{fp})/(ln2)^2\) 估算
保持误报率不变情况下, 过滤器大小和元素数量呈线性关系: \( m/n = C \), C即为每个元素需要分配的平均存储位数
由假阳性率公式可以推出, 最优k取值为\( k=(m/n)ln2≈0.7C \), 一般选择向下取整的k取值
\(k\) | \(m/n\) | \(P_{fp}\) |
---|---|---|
4 | 6 | 0.0561 |
6 | 8 | 0.0215 |
8 | 12 | 0.00314 |
11 | 16 | 0.000458 |
布隆过滤器不支持删除操作.
计数布隆过滤器 Counting Bloom Filter
一种支持删除操作的布隆过滤器, 引入一个大小为m的计数器数组\({C_j}^m_{j=1}\), 添加元素时, 增加对应的计数器数值, 且当计数器值为1时才更新比特数组:
for i in 1:k
j = h_i(x)
Cj = Cj + 1
if Cj == 1
CountingBloomFilter[j] = 1
end
end
计算散列值
减少对应计数器的值
如果计数器值变为0,则复位对应的比特数组位置
计数布隆过滤器的计数器往往要占用4Bt或更多, 所以比布隆过滤器往往要多4倍以上的空间
商数过滤器 Quotient Filter
布隆过滤器(及其变种)的任何操作都需要多次随机访问,所以不适合存储在硬盘上
商数过滤器就没有这个问题, 其数据局部性更好,只需要连续少量硬盘访问
支持元素删除,可以动态调整大小或者合并
空间和时间性能与布隆过滤器相当
给定数据集\(D={x_1, x_2, ..., x_n}\), 商数过滤器通过一个散列函数,对每个元素存储大小为\(p\)比特的
指纹
,
并利用商法
将每个指纹分割为长度为\(q\)比特的最高有效位(商)和长度为\(r\)比特的最低有效位(余数)。fr = f ÷ 2^r; fq = f % 2^r;
使用一个以商
fq
为索引以余数fr
为值的桶
来存储指纹, 指纹可以重建为:f=fq * 2^r + fr
每个桶包含三个元比特:
is_occupied, is_continuation, is_shifted
, 均初始化为0桶j为某个指纹的规范桶(fq=j)且该指纹存储在桶j中时,
is_occupied
置为1余数不是第一个被映射到该桶的余数时, is_continuation置为1
桶中存储的余数的规范桶为其他桶时, is_shifted置为1