![](https://csdnimg.cn/release/download_crawler_static/86288262/bg3.jpg)
问题2:不重复元素数
流模型(Streaming Model)
A stream:
σ = ha
1
, a
2
, . . . , a
n
i, a
i
∈ [m],
then we can dene a frequency vector
f = (f
1
, . . . , f
m
), s.t.
1≤i≤n
f
i
= n.
定义1.15[The Distinct Elements Problem]
给定数据流 σ,计算
1≤i≤m
I[f
i
> 0],I[f
i
> 0] = 1当且仅当f
i
> 0。
42 / 250
问题2:不重复元素数
精确计算需要多少空间代价?
▷ 方法1:O(m) 位.
为每一个[m]中的元素维护一个位,长度为m的向量.
▷ 方法2:O(n log(m)) 位.
维护n个数,每一个使用log(m)位.
43 / 250
问题2:不重复元素数
▷ 一个理想化的解决方案:假设可以存储实数
▷ 利用哈希函数(hash function)
◦ h : [m] 7→ [0, 1]
◦ h(i)的函数值是[0, 1]实数,均匀分布
FM Algorithm [Flajolet‑Martin 1985]
/** Maintain a variable z **/
1. 随机选取一个哈希函数h : [m] 7→ [0, 1]
2. z = 1.
3. 每遇到一个元素i,更新: z = min (z, h(i))
4. return 1/z − 1.
53 / 250
问题2:不重复元素数
FM算法的分析:令X =
1
z
− 1,E[z] =
1
D+1
,var[z] ≤
2
(D+1)(D+2)
Pr[|z −
1
D + 1
| > c
1
D + 1
] <
2(D + 1)
2
c
2
· (D + 1)(D + 2)
<
2
c
2
Pr[|X − D| > ϵD]
≤Pr[|z −
1
D + 1
| >
ϵD
(D + 1 + ϵD)
1
(D + 1)
]
c =
ϵD
D + 1 + ϵD
<
2(D + 1 + ϵD)
2
ϵ
2
D
2
=2(
D + 1
ϵD
+ 1)
2
<2(
2
ϵ
+ 1)
2
58 / 250
问题2:不重复元素数
Pr[|X − D| > ϵD]
⇔Pr[|1/z − 1 − D| > ϵD]
⇔Pr[
1
z
< 1 + (1 − ϵ)D或
1
z
> 1 + (1 + ϵ)D]
⇔Pr[z >
1
1 + (1 − ϵ)D
或z <
1
1 + (1 + ϵ)D
]
⇔Pr[z −
1
1 + D
>
ϵD
(D + 1)(1 + D − ϵD)
或z −
1
1 + D
<
−ϵD
(D + 1)(1 + D + ϵD)
]
≤Pr[|z −
1
D + 1
| >
ϵD
1 + D + ϵD
1
D + 1
]
59 / 250
问题2:不重复元素数
利用多次运行
FM+ Algorithm
/** Maintain a variable z **/
1. for j from 1 to k
2. 随机选取一个哈希函数h
j
: [m] 7→ [0, 1]
3. z
j
= 1.
4. 每次遇到 i,更新: z
j
= min (z
j
, h
j
(i))
5. Z =
1
k
k
j=1
z
j
;
6. return 1/Z − 1.
60 / 250
问题2:不重复元素数
FM+算法分析:X =
1
Z
− 1,Z =
1
k
k
j=1
z
j
,E[Z] = E[z],var[Z] =
var[z]
k
Pr[|Z −
1
D + 1
| > c
1
D + 1
] <
(D + 1)
2
c
2
var[Z]
c =
ϵD
D + 1 + ϵD
⇒ Pr[|X − D| > ϵD] <
2(D + 1 + ϵD)
2
kϵ
2
D
2
<
2
k
(
2
ϵ
+ 1)
2
这里,ϵ为精度要求,假设概率要求为1 − δ,只需
2
k
(
2
ϵ
+ 1)
2
< δ
⇒k >
2
δ
(
2
ϵ
+ 1)
2
= O(
1
ϵ
2
δ
)
61 / 250
问题2:不重复元素数
利用Median技术
FM++ Algorithm
1. 运行具有常数概率的FM+算法m = Θ(log
1
δ
)次;
2.
ˆ
D为所有 m 个结果的中间值;
3. return
ˆ
D.
FM++是一个以1 −δ概率保证(1 ±ϵ)近似的算法
整体代价为O(
1
ϵ
2
log
1
δ
)
63 / 250