情報源符号化とは

情報源符号化
符号化の例
瞬時符号の構築
情報源符号化とは
目的
復元したデータが与えられた要求を満たす前提で，最大限に圧縮
し，なるべく少ないビット数でデータを表現
分類
1
無歪み圧縮（講義の対象）
圧縮されたデータから情報源データを完全に復元
確率分布が既知の場合：Huﬀman Algorithm
確率分布が未知の場合：Lempel-Ziv Algorithm
2
歪みあり圧縮
ある程度の歪みを許す
1 / 13
情報源符号化
符号化の例
瞬時符号の構築
情報源符号化定理
エントロピー
X の要素で値をとる確率変数 X の確率分布 PX (x) が与えられ
た時，
∑
H(X ) = −
P(x) log P(x)
x∈X
を確率変数 X のエントロピーと呼ぶ．
Theorem
無歪み情報源符号化定理離散無記憶情報源 X の平均符号長を L̄ と
すると，L̄ > H(X ) となる無歪み圧縮は可能であるが，L̄ < H(X )
となる無歪み符号化は存在しない．
2 / 13
情報源符号化
符号化の例
瞬時符号の構築
固定長符号
可変長符号
固定長符号
情報源（確率変数）の確率分布
X
Pr{X = xi }
x0
x1
x2
x3
1
2
1
4
1
8
1
8
符号化
E(x0 )
E(x1 )
E(x2 )
E(x3 )
=
=
=
=
00
01
10
11
例
x = (x0 x2 x1 x0 x1 x0 x3 x0 ) ⇒ E(x) = (0010010001001100)
3 / 13
情報源符号化
符号化の例
瞬時符号の構築
固定長符号
可変長符号
固定長符号
復号化
ビット列をを 2 ビットずつ区切って復号
(|{z}
00 |{z}
10 |{z}
01 |{z}
00 |{z}
01 |{z}
00 |{z}
11 |{z}
00 )
x0
x2
x1
x0
x1
x0
x3
x0
符号化効率
符号語長はすべて 2 なので，平均符号語長 L̄ = 2
確率変数 X のエントロピー
1
1 1
1
1
1
7
H(X ) = − log − log − 2 log = bit
2
2 4
4
8
8
4
L̄ > H(X ) ⇒ 平均符号語長において改善の余地がある!
4 / 13
情報源符号化
符号化の例
瞬時符号の構築
固定長符号
可変長符号
可変長符号による符号化
可変長符号
出現頻度の高いデータに短い符号語を割り当てる
三つの可変長符号
E ＼X
E1
E2
E3
x0
1
0
0
x1
00
10
01
x2
01
110
011
x3
10
111
111
5 / 13
情報源符号化
符号化の例
瞬時符号の構築
固定長符号
可変長符号
符号器 E1 （×）
符号系列
x 1 = (|{z}
1 |{z}
01 |{z}
00 |{z}
1 |{z}
00 |{z}
1 |{z}
10 |{z}
1 )
x0
x2
x1
x0
x1
x0
x3
x0
に対して多数の復号語が存在
(|{z}
10 |{z}
1 |{z}
00 |{z}
1 |{z}
00 |{z}
1 |{z}
10 |{z}
1 )
x3
x0
x1
x0
x1
x0
x3
x0
10 |{z}
1 )
00 |{z}
1 |{z}
10 |{z}
01 |{z}
(|{z}
10 |{z}
x3
x3
x2
x0
x1
x3
x0
..
.
一意復号可能符号ではない！
6 / 13
情報源符号化
符号化の例
瞬時符号の構築
固定長符号
可変長符号
符号器 E2 （◎）
符号系列
x 2 = (|{z}
0 |{z}
110 |{z}
10 |{z}
0 |{z}
10 |{z}
0 |{z}
111 |{z}
0 )
x0
x2
x1
x0
x1
x0
x3
x0
長さが 3 より短い符号語の最後に 0 で符号の終わりを表す
符号系列に対して 0 もしくは (111) が現れたら，それまでの
系列を復号できる
復号遅延がない
瞬時符号：遅れなくデータを復元できる符号
7 / 13
情報源符号化
符号化の例
瞬時符号の構築
固定長符号
可変長符号
符号器 E3 （△）
符号系列
x 3 = (|{z}
0 |{z}
011 |{z}
01 |{z}
0 |{z}
01 |{z}
0 |{z}
111 |{z}
0 )
x0
x2
x1
x0
x1
x0
x3
x0
0 で始まる符号が続く場合には 1 ビットの遅れ
x3 が続く場合には 3 ビットに対応する遅れ
(|{z}
0 |{z}
111 )
x0
x3
一意復号可能であるが，瞬時符号ではない
E2 と E3 は最適な符号
L̄2 = L̄3 =
1
1
7
1
× 1 + × 2 + 2 × × 3 = = H(X )
2
4
8
4
8 / 13
情報源符号化
符号化の例
瞬時符号の構築
瞬時符号の判断
Huﬀman アルゴリズム
Lempel-Ziv アルゴリズム
Kraft 不等式
符号語長において瞬時符号が満たすべき条件
Theorem
集合 X = {xi }M−1
i=0 上の情報源 X に対して，一意復号可能な瞬時
符号が存在する必要条件は
|X |−1
∑
2−li ≤ 1
i=0
である．ただし，li は xi , xi ∈ X , の符号長である．
9 / 13
情報源符号化
符号化の例
瞬時符号の構築
瞬時符号の判断
Huﬀman アルゴリズム
Lempel-Ziv アルゴリズム
Huﬀman アルゴリズム
情報源 X の確率分布が既知の場合の最適な瞬時符号の構成法
1
p1 ≥ p2 ≥ p3 ≥ · · · ≥ pM−1 ≥ pM を満たすようにデータを並
べる．
2
pM−1 と pM に対応するデータの符号先頭に 0 と 1 を割り当
てる．
3
M = 2 なら符号語を出力して終了．
4
M > 2 なら，(pM−1 + pM ) と残りの確率で，１）から実行
する．
10 / 13
情報源符号化
符号化の例
瞬時符号の構築
瞬時符号の判断
Huﬀman アルゴリズム
Lempel-Ziv アルゴリズム
Huﬀman アルゴリズムの例
x0
0.4
x1
0.2
0.25
x2
0.15
0.2
x3
0.15
x4
0.1
0.35 0
0.6
0
0.4
1
⊕
0.25
0
1
⊕
0
0.15
⊕
1
1
E(x0 )
(1)
E(x1 )
(000)
E(x2 )
E(x3 )
E(x4 )
(001)
(010)
(011)
平均符号長：0.4 × 1 + 0.6 × 3 = 2.2
エントロピー：
− (0.4 log2 0.4 + 0.2 log2 0.2 + 2 × 0.15 log2 0.15 + 0.1 log2 0.1)
≈ 2.15 bits
11 / 13
情報源符号化
符号化の例
瞬時符号の構築
瞬時符号の判断
Huﬀman アルゴリズム
Lempel-Ziv アルゴリズム
Lempel-Ziv アルゴリズムの背景
Huﬀman アルゴリズムは最適であるが，確率分布を必要と
する
現実的には確率分布の計算は困難
特に情報源 xm ∈ X , 0 ≤ m < M, に対して，p(x0 , x1 ) などの
連合確率分布を求めるのが難しい
符号の生成法
辞書式固定長符号
辞書にない系列が出るまで入力を一文字ずつ読み取って登録
符号は最後の一文字以外の前に，それ以外の文字列の引数を
付加して生成
12 / 13
情報源符号化
符号化の例
瞬時符号の構築
瞬時符号の判断
Huﬀman アルゴリズム
Lempel-Ziv アルゴリズム
Lempel-Ziv アルゴリズムの例
入力 (A:0, B:1)
A|A, B|AB, B|B|AB, A|ABA, B|BB
Index
1
2
3
4
5
6
7
Phrase
A
AB
ABB
B
ABA
ABAB
BB
Code
0,A
1,B
2,B
0,B
2,A
5,B
4,B
Binary
000,0
001,1
010,1
000,1
010,0
101,1
100,1
符号語
(0000
| {z } 0101
| {z } 0001
| {z } 0100
| {z } 1011
| {z } 1001
| {z })
| {z } 0011
A
AB
ABB
B
ABA ABAB BB
13 / 13

Download Report