情報理論

前回の練習問題
２元ハフマン符号を構成せよ
平均符号長を求めよ
0.363×1+0.174×3+...+0.021×5=2.660
1.000
0
1
0.637
0.359
0.278
0.185
A
B
C
D
E
F
G
H
確率
0.363
0.174
0.143
0.098
0.087
0.069
0.045
0.021
0.135
0.066
0.363
A
0
0.174
B
100
0.143
C
110
0.098
D
1010
0.087
E
1011
0.069
F
1110
0.045
G
11110
0.021
H
11111
1
前回の練習問題
確率
４元ハフマン符号を構成せよ
A
0.363
確率の小さな４つの木を併合すれば良い？
B
0.174
⇒ 最後に，節点の個数が足りなくなるかも...
C
0.143
⇒ 一回の併合で，4 – 1 = 3 個の木が消失
D
0.098
⇒ 最後，1 個の木になって終了するには，
E
0.087
最初に 3k + 1 個の節点が必要
F
0.069
G
0.045
?
H
0.021
確率 0 のダミー節点を 2 個加え，通報数を10 = 3×3 +1に
1.000
a
0.363
A
a
b
0.174
B
b
d
c
0.143
C
c
0.098
D
da
0.320
0.087
E
db
0.069
F
dc
0.066
0.045
G
dda
0.021
H
ddb
0
*
0
*
2
本日の講義
ハフマン符号の性能と限界
ハフマン符号化の拡張
ブロック符号化と平均符号長
情報源符号化定理
情報源符号化の限界
非等長ブロックハフマン符号化
ランレングス符号化
3
平均符号長について
情報源符号化に求められる性質：
瞬時復号可能であること（自動的に一意復号可能となる）
平均符号長ができるだけ小さいこと
⇒ ハフマン符号が有力候補
一意復号可能な
符号のクラス
ハフマン符号は，どれくらい
「良い」符号なのか？
⇒ 平均符号長の限界定理
瞬時復号可能な
符号のクラス
ハフマン符号
4
平均符号長の限界定理
定常情報源 S から発生する通報を一個ずつ，
瞬時復号可能な符号Cにより符号化することを考える
通報は M 通り，各通報の発生確率は p1, ..., pM
[定理]
任意の符号について，平均符号長は必ず L  H1(S) となる
...どんなに効率的でも，平均符号長は１次エントロピー以上
平均符号長が L < H1(S) + 1となる符号を構成できる
...平均符号長が１次エントロピーに迫る符号を作ることが可能
5
シャノンの補助定理
定理の証明にあたり，補助定理（補題）をひとつ導入
（シャノンの補助定理，Shannon’s lemma）
[補題] q1 + ... + qM  1 を満たす任意の正数 q1, ..., qM に対し，
M
M
i 1
i 1
  pi log 2 qi   pi log 2 pi ( H1 ( S ))
等号成立は，p1 = q1, ..., pM = qM のとき，かつそのときのみ．
6
シャノンの補助定理の証明
M
M
i 1
i 1
  pi log 2 qi   pi log 2 pi
証明：不等式の左辺 – 右辺を考えると，
M
M
M
qi M pi
qi
  pi log 2 qi   pi log 2 pi   pi log 2  
( log e )
pi i 1 log e 2
pi
i 1
i 1
i 1
M
y = – logex
1
O
y=1–x
M
pi
qi
1

(1  )  
( pi  qi )
pi
i 1 log e 2
i 1 log e 2
M
M
M
1
1

( pi   qi ) 
(1   qi )
log e 2 i 1
log e 2
i 1
i 1
0
qi / pi = 1 (i = 1, ..., M) のとき等号成立
7
符号長限界定理の証明（前半）
Cの符号語長をl1, ..., lM とし，qi = 2–liとおく．クラフトの不等式より
2l1    2 lM  q1    qM  1.
li = – log2qi なので，平均符号長は
M
M
i 1
i 1
L   pi li   pi log 2 qi .
シャノンの補助定理を用いて，
M
M
i 1
i 1
L   pi log 2 qi   pi log 2 pi  H1 ( S ).
等号成立は，p1 = q1, ..., pM = qM のとき，かつそのときのみ
（前半証明終了）
8
符号長限界定理の証明（後半）
以下の不等式を満たすよう，整数 li を定める．
 log 2 pi  li   log 2 pi  1.
これより 2–li  2log pi =pi であり，
2
l1
 2
l M
M
  pi  1.
i 1
したがって l1, ..., lM はクラフトの不等式を満足し，
この符号長を持つ（瞬時に復号可能な）符号を構成可能．
この符号の平均符号長は
M
M
M
M
i 1
i 1
i 1
i 1
 pi li   pi ( log 2 pi  1)   pi log 2 pi   pi  H1 ( S )  1.
（後半証明終了）
9
符号長限界定理とハフマン符号
[定理]（再掲）
任意の符号について，平均符号長は必ず L  H1(S) となる
平均符号長が L < H1(S) + 1となる符号を構成できる
ハフマン符号では，平均符号長が，必ずL < H1(S) + 1となる
...実際には，もっと強い証明が可能
ハフマン符号よりも平均符号長の小さな瞬時符号は存在しない
（ハフマン符号はコンパクト符号 (compact code)である）
証明は，符号木の大きさに関する帰納法による（以下略）．
10
ハフマン符号とブロック化
ハフマン符号...一個の通報を，一個の符号語に変換する
平均符号長は，かならず１以上となる
２元情報源の符号化には向かない
A B A C C A
通報
確率 C1 C2
A
0.8
0
1
0 10 0 11 11 0
B
0.2
1
0
1.0 1.0
平均符号長
複数の通報をまとめて符号化（ブロック符号化）すると...
通報あたりの平均符号長を１以下にできるかも
A B A C C A
２元情報源の符号化にも利用可能
10
1101 01
11
ブロック符号化のイメージ
通報の系列
ABCBCBBCAA...
ブロック化
ブロック化された AB CBC BB CAA...
通報の系列
等長ブロック化
非等長ブロック化
ブロック詳細化法
ランレングス法
ハフマン符号化
符号語系列
01 10 001 1101...
12
等長ブロック符号化の例（１）
確率符号語
0
A 0.6
10
B 0.3
11
C 0.1
AA
AB
AC
BA
BB
BC
CA
CB
CC
確率
0.36
0.18
0.06
0.18
0.09
0.03
0.06
0.03
0.01
符号語
0
100
1100
101
1110
11110
1101
111110
111111
左表のとおりハフマン符号化をすると，
平均符号長は
0.6×1 + 0.3×2 + 0.1×2 = 1.4
長さ２のブロックを考える
AAの発生確率 = 0.6×0.6=0.36 ....
左表のとおりハフマン符号化をすると，
平均符号長は
0.36×1 + 0.18×3 + ... + 0.01×6 = 2.67
通報一個当たりでは，2.67 / 2 = 1.335
⇒ 少し効率が良くなった
13
等長ブロック符号化の例（２－１）
確率符号語
0
A 0.8
1
B 0.2
AA
AB
BA
BB
確率符号語
0.64
0
0.16 10
0.16 110
0.04 111
平均符号長は
0.8×1 + 0. 2×1 = 1.0
長さ２のブロックを考える
AAの発生確率 = 0.8×0.8=0.64 ....
平均符号長は
0.64×1 + 0.16×2 + ... + 0.04×3 = 1.56
通報一個当たりでは，1.56 / 2 = 0.78
⇒ ２元情報源でも，効率改善
14
等長ブロック符号化の例（２－２）
AAA
AAB
ABA
ABB
BAA
BAB
BBA
BBB
確率
0.512
0.128
0.128
0.032
0.128
0.032
0.032
0.008
符号語
0
100
101
11100
110
11101
11110
11111
長さ３のブロックを考える
AAAの発生確率 = 0.83=0.512 ....
平均符号長は
0.512×1 +... + 0.008×5 = 2.184
通報一個当たりでは，2.184 / 3 = 0.728
ブロック長一通報あたり平均符号長
1
1.0
ブロック長を大きくすると，
2
0.78
一通報あたり平均符号長は
3
0.728
小さくなる（効率が良くなる）
:
:
15
ブロック符号の平均符号長
ブロック長を大きくすると，一通報あたり平均符号長は小さくなる
⇒ どこまで小さくなるのか？
n 個単位でブロック化した通報＝n 次拡大情報源Snの通報１個
⇒ 講義前半で紹介した平均符号長の限界定理が適用できる
ブロック符号の平均符号長をLnとすると，H1(Sn)  Ln < H1(Sn)+1.
一通報当たりの平均符号長に換算すると...
H1 ( S n ) Ln H1 ( S n ) 1



n
n
n
n
16
シャノンの情報源符号化定理
H1 ( S n ) Ln H1 ( S n ) 1



n
n
n
n
H1(Sn) / n は，情報源 S の n 次拡大エントロピー Hn(S)
n → ∞のとき，
H1(Sn) / n → H(S)...情報源 S の極限エントロピー
1/n→0
[シャノンの情報源符号化定理]
情報源Sから発生する通報は，一通報あたりの平均符号長が
H(S)  L < H(S) + e である瞬時復号可能な符号に符号化可能
17
情報源符号化定理の意味するところ
情報源Sから発生する通報は，一通報あたりの平均符号長が
H(S)  L < H(S) + e である瞬時復号可能な符号に符号化可能
ブロック長を長くしてハフマン符号を使えば，効率的にはベスト
どれだけ頑張っても，極限エントロピーの壁は越えられない
確率符号語
0
A 0.8
1
B 0.2
H(S) = 0.723
ブロック長一通報あたり平均符号長
1
1.0
2
0.78
3
0.728
:
:
:
:
0.723 + e
18
ブロック符号化法の実用性
効率面からは，ブロック化＋ハフマン符号が最良な方法
ブロック長を大きくすれば，いくらでも理論限界値に近づける
実用面から見たデメリット：
通報の発生確率を，あらかじめ知っておく必要がある
（⇒ 次回講義で触れる予定）
符号の定義（通報と符号語の対応表）が巨大になる
対応表１行を記憶するのに１バイト必要だとすると...
ブロック長 8...256バイト
ブロック長 16...64キロバイト
ブロック長 32...4ギガバイト
19
非等長ブロック符号化
ここまでのブロック符号化：符号化対象のパターンは同じ長さ
⇒ 発生確率の非常に小さなパターンにも符号語定義が必要
⇒ 対応表の巨大化
A B AA B A B A
符号化対象のパターンが，異なる長さを持つことを許す
⇒ 非等長 (unequal-length) ブロック化．ただし
各パターンの発生確率が，ある程度均衡すること
任意の通報系列が，パターンにブロック化できること
...どのようにパターンを定義するかが鍵となる
A B AA B A B A
20
パターンの定義方法について
パターン定義の戦略１：ブロック詳細化（頻出パターンの細分化）
1. 長さ１のパターンを用意する
2. 発生頻度の高いパターンを細分化し，分割する
3. 所望のパターン数になるまで 2 を繰り返す
例：P(A) = 0.8, P(B) = 0.2，所望パターン数４のとき
A 0.8
B 0.2
AA 0.64
AB 0.16
B 0.2
AAA
AAB
AB
B
0.512
0.128
0.16
0.2
任意の系列を，{AAA, AAB, AB, B} にブロック化可能
21
非等長ブロック化時の平均符号長
前スライドのパターンに対し，
ハフマン符号を定義（右表）
パターン
AAA
AAB
AB
B
確率符号語
0.512
0
0.128
100
0.16
101
0.2
11
n個の通報ブロック...
符号語系列の長さは
0.512n×1 + 0.128n×3 + 0.16n×3 + 0.2n×2 = 1.776n
通報系列の長さは
0.512n×3 + 0.128n×3 + 0.16n×2 + 0.2n×1 = 2.44n
一通報あたりの符号長は，1.776n / 2.44n = 0.728
...ブロック長３（対応表８行）のときと同程度の効率 (cf. p.15)
22
パターンの定義方法について：ラン長の利用
パターン定義の戦略２：記号のランによりパターン定義
（ランレングス法）
記号のラン（run)：系列中の，同一記号からなる部分系列
A B B AAAAA B AAA B
長さ1のAのラン
長さ3のAのラン
長さ0のAのラン長さ5のAのラン
特定記号のランの長さだけ与えられれば，元の系列を復元可能
⇒ ランの長さを符号化しよう！
23
ラン長の上限
非常に長いランが発生することも...
⇒ランの長さに上限を設け，上限以上のランは短く分割して表現
上限を３とした場合
ラン長表現方法
0
0
1
1
2
2
3
3+0
4
3+1
5
3+1
6
3+3+0
7
3+3+1
:
:
ABBAAAAABAAAB を表現する：
Aが１個発生し，Ｂが発生
Aが０個発生し，Ｂが発生
Aが３個以上発生
Aが２個発生し，Ｂが発生
Aが３個以上発生
Aが０個発生し，Ｂが発生
24
ランレングスハフマン符号
ランレングスハフマン符号 (run-length Huffman code)
通報系列中の特定記号のラン長を符号化したハフマン符号
⇒ 通報の発生頻度に偏りがある場合，非常に有効
p(A) = 0.9, p(B) = 0.1 のとき
ラン長
0
1
2
3以上
符号化されるパターン
B
AB
AAB
AAA
発生確率
0.1
0.09
0.081
0.729
符号語
10
110
111
0
ABBAAAAABAAAB: 1, 0, 3+, 2, 3+, 0 ⇒ 110 10 0 111 0 10
AAAABAAAAABAAB: 3+, 1, 3+, 2, 2 ⇒ 0 110 0 111 111
AAABAAAAAAAAB: 3+, 0, 3+, 3+, 2 ⇒ 0 10 0 0 111
25
符号化例
S: 記憶のない２元定常情報源，p(A) = 0.9, p(B) = 0.1
エントロピーは H(S) = –0.9log20.9 – 0.1log20.1 = 0.469
通報確率符号語
A
0.9
0
B
0.1
1
単純なハフマン符号化：
平均符号長は1
等長ハフマンブロック符号化 (n = 3)
通報確率符号語
通報確率符号語
AAA 0.729
0
BAA 0.081 1110
AAB 0.081 100
BAB 0.009 1011
ABA 0.081 110
BBA 0.009 11110
ABB 0.009 1010
BBB 0.009 11111
平均符号長 1.661, 一通報あたりの平均符号長 1.661 / 3 = 0.55
26
符号化例（続）
ランレングスハフマン符号化（符号語数を８に設定）
ラン長確率符号語
ラン長確率符号語
0
0.1 110
4 0.066 1011
1
0.09 1000
5 0.059 1110
2 0.081 1001
6 0.053 1111
3 0.073 1010
7+ 0.478 0
nブロックでは...
符号語系列 0.1n×3+...+0.478n×1=2.466n
通報系列 0.1n×1+...+0.053×7+0.478×7=5.216n
（ラン長 k ⇒ k 個のAと一個のB なので通報数では k+1）
一通報あたりの平均符号長は 2.466n / 5.216n = 0.47
27
本日のまとめ
平均符号長の限界定理
シャノンの情報源符号化定理
ハフマン符号の拡張的利用法
ブロック符号化
非等長ブロック符号化
ブロック詳細化法
ランレングス法
（ブロック詳細化の特殊ケース，と考えることも可能）
28
練習問題
通報とその発生確率を入力すれば，ハフマン符号を構成する
プログラムを作成せよ
ブロック符号が構成できるよう，上記プログラムを改造せよ
適当な通報と発生確率を定め，一通報あたりの平均符号長が
ブロック長によりどう変化するか，プログラム実験を行え
29

Download Report