内容简介:系统中的所有数据以block 存放: 每个block里:2个block中可能包含大量的重复文件, 这时我们需要找出这2个block, 将其合并, 以节省空间.问题: 如何高效的(在时间上和空间上) 找出具有大量重复文件的block对.
问题
系统中的所有数据以block 存放: 每个block里:
n l
2个block中可能包含大量的重复文件, 这时我们需要找出这2个block, 将其合并, 以节省空间.
问题: 如何高效的(在时间上和空间上) 找出具有大量重复文件的block对.
问题包含2个部分:
- 创建数据结构保存在block中, 作为 签名
- 在需要时对比2个block的签名以得出 相似度
常规方法
1. 文件列表
因为block内的文件名是 排序 的, 可以直接对比2个block各自的文件列表, 走一遍归并, 这样,
创建签名的开销:
-
时间和空间开销:
O(n x l)
, 每个block需要存储: 5G 数据: 1000万 x 512
计算相似度的开销:
-
总的时间复杂度是
O(n x l)
, 需要读取 5G x 2的数据
这种方法可以非常准确的得出重复文件数量. 但空间开销和时间开销都比较大.
2. hash-bitmap
另外一个直接的, 近似的方案是使用hash-bitmap:
创建签名:
对每个block, 将所有文件名做1次hash,
例如: int(sha1(fn)) % b
,
这里b 是bitmap的大小, 如果取b=64 * 10^6, 这个hash 表是比较稀疏的(n/b=0.16),
冲突率也就比较低, 大约有7%的冲突率, 参考:hash-collision
计算相似度:
然后再对比2个block的时候, 可以通过将2个bitmap取 AND
操作,
找到存在于2个block中的bit有几个, 来确定重复的文件数.
这种方法是粗略的估计:
-
其一是hash时, 在同一个block中, 2个fn的hash可能落到1个bit上, 导致不准确.
-
其二是2个block中把不同的fn也可能hash到1个bit上, 导致估算时增加重复文件的统计.
创建签名的开销:
-
空间复杂度:
O(n)
, 实际存储空间开销是 8MB, 因为不同的block的bitmap大小必须一致, 所以要取最大可能的大小. -
时间复杂度是
O(n x l)
计算相似度的开销:
-
时间复杂度是
O(n/64)
, 因为目标机器是64位的, 位AND操作一次可以对比64个bit(1个int64_t
)
但这2个方案都不是最好的, 虽然hash-bitmap的方案空间开销已经很小了.
接下来我们看看这个思路: min-hash
方案: min-hash
min-hash 实现了使用常量的空间开销对2个集合进行相似度的比较.
原理
-
A, B 是2个集合, 我们定义一个相似度的函数: Jaccard-similarity:
J(A, B) = len(A ∩ B) / len(A ∪ B)
-
假设有1个hash函数, 它不会对不同的输入得出相同的hash值, 即: 如果
x != y
, 那么hash(x) != hash(y)
, 这里我们在测试演示的时候就选择用sha1
了, 而且将sha1的输出结果按照16进制40位整数处理. -
最小hash值: 一个集合S中所有元素的hash值最小的那个(hash值, 不是原始元素), 对我们的场景来说:
min_a = min([ sha1(x) for x in A ]) min_b = min([ sha1(x) for x in B ])
显然如果A和B的元素一样, 那么 min_a == min_b
;
如果A和B的元素有很多重复, 那么 min_a
和 min_b
有很大概率相同;
更精确的, 对A, B两个集合, min_a == min_b 的概率是 J = len(A ∩ B) / len(A ∪ B)
解释下上面的结论的推导过程
-
对有n个元素的集合S, 假设S集合未知, 也就是说它里面的元素都是随机的, 那么, 对其中所有元素做一次hash后, 其中的一个元素e, 成为最小hash的概率是
1/n
, 也就是:P(sha1(e) == min([ sha1(x) for x in S ])) = 1/n
因为假设hash函数均匀, 每个元素成为最小元素的几率都是相等的.
-
对于要对比的2个集合A和B, 元素共有:
A ∪ B
, 取min_ab = min([ hash(x) for x in (A ∪ B) ])
,A ∪ B
中每个元素成为min_ab
的几率是1 / len(A ∪ B)
因此
A ∩ B
里的一个元素e 成为min_ab
的几率是len(A ∩ B) / len(A ∪ B)
. -
而
A ∩ B
里的一个元素e 成为min_ab
, 是min_a == min_b
的充要条件.所以有 P(min_a == min_b) = J = len(A ∩ B) / len(A ∪ B)
所以我们的问题就转化成: 求出P, 我们就知道的2个block中重复文件的比例J
使用 min-hash 求相似度的步骤也是2个:
生成签名:
-
确定一个hash函数, 测试中就用
sha1
了. -
分别为A 和 B准备
b
个bucket:bucket_a
和bucket_b
. -
对A中所有元素计算sha1, 按照
sha1(a) % b
拆分A中的元素到b个bucket中:bucket_a[sha1(a) % b].append(sha1(a))
对B也做同样的操作.
-
记录A, B中每个bucket中的最小hash值:
for i in range(0, b): bucket_a[i] = min(bucket_a[i]) bucket_b[i] = min(bucket_b[i])
将元素分散到b个bucket中, 是为了通过概率的均值来估算概率P.
这里也暗含了一个假设: bucket_a[i] 中的元素与bucket_b[i]的元素相似度与 len(A ∩ B) / len(A ∪ B)
相近
因为假设认为sha1 非常随机地分散了A或B中的元素, 子集相似度接近全集相似度.
计算相似度:
对比2个block, 统计 min_a == min_b
的个数:
eq = 0.0 for i in range(0, b): if bucket_a[i] == bucket_b[i]: eq += 1 P = eq / b
因为P == J, 所以我们就得到了2个block的相似度.
min-hash 实现
实现时, 要求对比的2个block的使用的bucket数量 b
相同.
-
空间复杂度
O(b)
:1KB = sizeof(int64) * b
b=128
-
时间复杂度:
O(b)
: 128次int 比较
通过min-hash 计算相似度 和 对比真实统计相似度的 python 代码:min-hash.py
通过这个程序模拟的结果如下:
模拟验证
NO. bucket: 128
Hash length: int64
总数 | a总数 | b总数 | 实际重复率(A∩B)/(A∪B)% | 估算重复% | 误差% |
---|---|---|---|---|---|
1000 | 360 | 840 | 20.00% | 21.88% | 1.87% |
1000 | 520 | 880 | 40.00% | 38.28% | -1.72% |
1000 | 680 | 920 | 60.00% | 60.94% | 0.94% |
1000 | 839 | 959 | 80.16% | 78.91% | -1.25% |
1000 | 1000 | 1000 | 100.00% | 100.00% | 0.00% |
10000 | 3600 | 8400 | 20.00% | 15.62% | -4.38% |
10000 | 5200 | 8800 | 40.00% | 35.16% | -4.84% |
10000 | 6800 | 9200 | 60.00% | 60.94% | 0.94% |
10000 | 8399 | 9599 | 80.02% | 85.16% | 5.14% |
10000 | 10000 | 10000 | 100.00% | 100.00% | 0.00% |
100000 | 36000 | 84000 | 20.00% | 21.88% | 1.87% |
100000 | 52000 | 88000 | 40.00% | 47.66% | 7.66% |
100000 | 68000 | 92000 | 60.00% | 62.50% | 2.50% |
100000 | 83999 | 95999 | 80.00% | 80.47% | 0.47% |
100000 | 100000 | 100000 | 100.00% | 100.00% | 0.00% |
1000000 | 360000 | 840000 | 20.00% | 19.53% | -0.47% |
1000000 | 520000 | 880000 | 40.00% | 40.62% | 0.62% |
1000000 | 680000 | 920000 | 60.00% | 58.59% | -1.41% |
1000000 | 839999 | 959999 | 80.00% | 75.78% | -4.22% |
1000000 | 1000000 | 1000000 | 100.00% | 100.00% | 0.00% |
结论
系统中的所有数据以block 存放, 2个block中可能包含大量的重复文件, 这时我们需要找出这2个block, 将其合并,
问题: 如何高效的(在时间上和空间上) 找出具有大量重复文件的block对.
假设:
n = 1000万 l = 512 字节 64 * 10^6 = 8MB b = 128
各种算法的开销如下
算法\开销 | 空间开销 | 实际空间 | 时间开销 |
---|---|---|---|
fn-list | O(n x l) | 5GB | O(n x l) |
hash-bitmap | O(n) | 8MB | O(n) |
min-hash | O(1) | 1KB | O(1) |
参考:
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- Windows Server 2019新版发布:新增存储合并服务
- 分组字符合并SQL语句 按某字段合并字符串之一(简单合并)
- git 的合并原理(递归三路合并算法)
- git 合并策略
- 算法 - 合并若干有序文件
- Git合并提交
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。