狠狠撸

あらまし一意復号可能性エントロピーと平均符号長
実験数学 3
(大阪大学理学部数学科 3 年?4 年)
第 7 回: データ圧缩
鈴木譲
大阪大学
2014 年 6 月 26 日
1 / 14
実験数学 3, (大阪大学理学部数学科 3 年?4 年), 第 7 回: データ圧缩

あらまし
1 一意復号可能性
2 エントロピーと平均符号長
2 / 14

符号化
A: 有限集合
{0, 1}?: 有限の長さの 2 進列の集合
φ : A → {0, 1}? (符号化)
lφ : A → N が符号化 φ の長さ
.
.
x ∈ A に φ(x) ∈ {0, 1}l なる l ∈ N (長さ) を対応させる写像
φn : An → {0, 1}? が n 次の符号化
xn = (x1, · · · , xn) ∈ An に φ(x1), · · · , φ(xn) を連結した長さ
n∑
i=1
lφ(xi ) の 2 進列 φ(x1) · · · φ(xn) ∈ {0, 1}? を対応させる写像
3 / 14

一意復号可能性
φ が一意復号可能
.
.
各 n = 1, 2, · · · と各 un, vn ∈ An について、
φn
(un
) = φn
(vn
) =? un
= vn
r ∈ {0, 1}? は s ∈ {0, 1}? の語頭 (r ? s)
.
.
r が s の最初の部分の 2 進列
φ が瞬時復号可能
u, v ∈ A について、
φ(u) ? φ(v) =? u = v
4 / 14

例: A = {α, β, γ, δ}
φa, φb, φc は一意復号可能
φa, φb は瞬時復号可能
φc は瞬時復号可能ではない。
φ6
d (α, γ, α, δ, β, α) = φ6
d (δ, β, α, γ, α, α) = 011001100
x φa(x) φb(x) φc (x) φd (x)
α 00 0 0 0
β 01 10 01 10
γ 10 110 011 11
δ 11 111 111 01
(α, γ, α, δ, β, α) 001000110100 01100111100 00110111010 011001100
(δ, β, α, γ, α, α) 110100100000 11110011000 11101001100 011001100
5 / 14

φa
?
?
?
d
d
d
¨¨¨
rrr
rrr
¨¨¨
0
1
0
1
0
1
α
β
γ
δ
φb
?
?
?
d
d
d
rrr
¨¨¨
$$$
???
0
1
0
1
0
1
α
β
γ
δ
φc
?
?
?
d
d
d
rrr
rrr
???
???
0
1
1
1
1
1
α
β
γ
δ
φd
?
?
?
d
d
drrr
¨¨¨
rrr
0
1
0
1
1
α
δ
β
γ
6 / 14

瞬時復号可能 =? 一意復号可能
命題
.
.瞬時復号可能 =? 一意復号可能
証明: φ が瞬時復号可能と仮定
符号化された後の系列 φ(x1) · · · φ(xn) ∈ φn(A) から
.
1 φ(x) ? φ(x1) · · · φ(xn) =? x1 = x
φ(x1)φ(x2) · · · φ(xn) から φ(x1) を取り除く
.
2 φ(x) ? φ(x2) · · · φ(xn) =? x2 = x
φ(x2)φ(x3) · · · φ(xn) から φ(x2) を取り除く
3 ......
符号化される前の系列 xn = (x1 · · · xn) ∈ An が一意
7 / 14

一意復号可能であるための同値な条件
定理
.
以下の 3 つの条件は同値である。
.
1 lφ が瞬時復号可能な符号化 φ の長さ
.
2 lφ が一意復号可能な符号化 φ の長さ
.
3 lφ が Kraft の不等式を満足：
∑
x∈A
2?lφ(x)
≤ 1
1. =? 2. は，命題から。
8 / 14

2. =? 3.
lmax := maxx∈A lφ(x)
αn(m) := #{xn ∈ An|
∑n
i=1 lφ(xi ) = m}
(
∑
x∈A
2?lφ(x)
)n
=
∑
x1∈A
2?lφ(x1)
· · ·
∑
xn∈A
2?lφ(xn)
=
∑
xn∈An
2?
∑n
i=1 lφ(xi )
=
n·lmax∑
m=1
αn
(m)2?m
φ が一意復号可能 =? 重複がない =? 各 n で αn(m) ≤ 2m
=? 各 n で
∑
x∈A
2?lφ(x)
≤ (n · lmax )1/n
=?
∑
x∈A
2?lφ(x)
≤ 1
9 / 14

3. =? 1.
∑
x∈A
2?lφ(x)
≤ 1 ??
lmax∑
m=1
α1
(m) · 2?m
≤ 1
??
?
????
????
α1(1) ≤ 2
α1(2) ≤ 2{2 ? α1(1)}
...
...
α1(lmax ) ≤ 2{2lmax ?1 ? 2lmax ?2 · α1(1) ? · · · ? α1(lmax ? 1)}
=? レベル m で使用する葉の個数が、レベル m ? 1 で未使用の葉
の個数の 2 倍以下 (m ≥ 2)
=? 各レベル m に α1(m) 個の葉をもつ 2 進木 T が存在 (m ≥ 2)
=? φ(x) から T のレベル lφ(x) の葉への 1 対 1 写像が存在
=? lφ が瞬時復号可能な符号化 φ の長さ
10 / 14

エントロピーと平均符号長
PX (x): 事象 (X = x) の確率 (x ∈ A)
X のエントロピー H(X) と φ についての平均符号長 Elφ(X)
.
.
H(X) :=
∑
x∈A
?PX (x) log2 PX (x)
Elφ(X) :=
∑
x∈A
PX (x)lφ(x)
命題
H(X) ≤ Elφ(X) ≤ H(X) + 1
となる一意復号可能な符号化 φ が存在
11 / 14

証明: Q(x) := 2?lφ(x)
とおくと、
Elφ(X) =
∑
x∈A
?PX (x) log2 Q(x)
log x ≤ x ? 1, x > 0 と Kraft の不等式より，
Elφ(X) ? H(X) =
∑
x∈A
PX (x) log2
PX (x)
Q(x)
≥
1
log 2
∑
x∈A
PX (x)
{
1 ?
Q(x)
PX (x)
}
=
1
log 2
{1 ?
∑
x∈A
Q(x)} ≥ 0
lφ(x) := ?? log2 PX (x)? (切上げ) は Kraft の不等式を満足し，
?? log2 PX (x)? ≤ ? log2 PX (x) + 1 より，右の不等式が成立。
12 / 14

ブロック符号化
Xn := (X1, · · · , Xn): 確率変数の列
事象 (Xi = xi ), (Xj = xj ), xi , xj ∈ A, i ?= j が独立
PXn (xn), xn ∈ An: 事象 (Xn = xn) の確率
H(Xn
) :=
∑
xn∈An
?PXn (xn
) log PXn (xn
)
=
∑
xn∈An
?PXn (xn
)
n∑
i=1
log PX (xi )
=
n∑
i=1
∑
x∈A
?PX (xi ) log PX (xi ) = nH(X)
13 / 14

φ : An
→ {0, 1}?
(n 次の符号化とは限らない)
lφ(xn
) := ?? log2 PXn (xn
)?
Q(xn
) := 2?lφ(xn)
, xn
∈ An
nH(X) ≤ Elφ(Xn
) ≤ nH(X) + 1
平均圧縮率
.
.
平均の長さを n で割った値
Elφ(Xn)
n
定理
Elφ(Xn)
n
→ H(X)
(n → ∞) で一意復号可能な符号化 φ : An → {0, 1}? が存在
14 / 14

狠狠撸

公開鍵暗号(7): データ圧缩

Recommended

More Related Content

What's hot (19)

Viewers also liked (20)

Similar to 公開鍵暗号(7): データ圧缩 (15)

More from Joe Suzuki (20)

公開鍵暗号(7): データ圧缩