Information Theory

Report
chapter 2:
情報をコンパクトに表現する
1
chapter 2の目的
情報源からの記号(列)を,効率よく(コンパクトに)符号化する
情報源符号化
データ圧縮
0101101
符号化
情報源符号化の目的:
通信に適した表現方式への変換
情報の中の無駄な部分を整理し,捨て去る
情報源
目標とする符号化方式:
できるだけ正確に元の情報を復元できること
できるだけコンパクトな情報表現を与えること
2
議論の順序
情報源符号化の基礎
一意復号可能性
瞬時復号可能性
ハフマン符号
ハフマン符号の構成法
ハフマン符号の最適性
ブロック符号化
情報源符号化定理
関連する話題
3
用語について
はじめに,情報源の記号ごとに符号化を行う方式を考える
M: 情報源が生成する記号の集合
M の各記号に対し,{0, 1}上の系列を対応付ける
符号語: Mの記号に対応付けられた{0, 1}上の系列
符号: 符号語の集合
2種類の文字 {0, 1} を使用...2元符号
M
晴
曇
雨
C
00
010
101
符号語は3つ; 00, 010, 101
符号 C = {00, 010, 101}
011 は符号語ではない
4
符号化と復号
符号化... 与えられた記号から,対応する符号語を求めること
復号 ... 与えられた符号語から,対応する記号を求めること
晴
曇
雨
符号化
復号
00
010
101
encode = 符号化
decode = 復号
符号語間に,スペース,コンマ等の区切り記号は使わない
01000101101はOK, 010 00 101 101 はNG
「区切り記号 = 第3の記号」
⇒ 「3元」符号を考えることになってしまう
5
一意復号可能性
符号は,一意復号可能でないといけない
異なる記号が同じ符号語を持つのがNG
異なる記号が異なる符号語を持つ,だけでも不十分
異なる記号系列は,異なる0-1系列に符号化されること
a1
a2
a3
a4
C1
00
10
01
11
yes
C2
0
01
011
111
yes
C3
0
10
11
01
no
C4
0
10
11
0
no
C3 を使う場合...
a1 a3 a1
0110
a4 a 2
6
一意性だけで十分か?
C2 を使ってa1, a4, a4, a1を符号化,1bit/secでデータ送信
a1
a1, a4, a4, a1 ⇒ 01111110 (8ビットのデータ)
a2
a3
受信者が,最初の記号を確定できるのはいつか?
a4
7秒経過後 ... 0111111 まで受信
次に 0 が来ると,0 - 111 - 111 - 0  a1, a4, a4, a1
次に 1 が来ると, 01 - 111 - 111  a2, a4, a4
C2
0
01
011
111
7秒後でも,最初の記号すら確定できない
 受信データのバッファが必要,復号遅延の問題...
 動画ダウンロードだったら,どうなるか
7
瞬時復号可能性
実用的なシステムでは,瞬時に復号可能であることが望ましい
「符号語のパターンが出現したら,即座に復号して良い」
一意復号可能の「上位」の性質
瞬時復号可能ならば, 必ず一意復号可能
符号  が瞬時復号可能であるとは...
任意の系列  ∈ 0,1 ∗ に対し,
 = 1 1 となる符号語1 ∈ が存在するならば,
 = 2 2 となる他の符号語2 ∈  が存在しない
1
1
=
2
2
8
語頭条件
符号が瞬時復号可能でないならば,  = 1  = 2  となる
系列 ∈ 0,1 ∗ と,二つの異なる符号語 1 , 2 が存在する
c1
s1
=
c2
1 は2 の語頭である,という
s2
補題:
符号 C が瞬時復号可能である必要十分条件は,
他の符号語の語頭となる符号語が存在しないこと
(prefix condition, 語頭条件)
a1
a2
a3
“0” は “01” と “011”の語頭
“01” は “011”の語頭 a4
C2
0
01
011
111
9
雑談:語頭条件とユーザインタフェース
語頭条件は,情報理論以外でも重要
悪い例:PDAにおける文字ストローク
graffiti (ver. 1)
すべて一筆書きでOK
graffiti (ver. 2)
二画の文字が出現
語頭条件に反する
“– –” と “=”,“– 1” と “+”,etc
10
語頭条件を確保するには
語頭条件を満たす符号の作り方:
全ての符号語を,同じ長さで設計する
符号語の最後に「特殊パターン」を置く
C = {011, 1011, 01011, 10011} ... “コンマ符号”
... あまりにも安直
木構造を利用して符号語を選んでくる (「符号木」)
2元符号の場合,次数が2の木を利用
次数2の
符号木
11
符号の構成(2元の場合)
M個の符号語を持ち,語頭条件を満たす 2元符号の作り方
1.
葉をM個持つような,次数 2の木 T を構成する
2.
T の各枝に,0 か 1 の値をラベル付けする
兄弟が同じラベルを持つことは禁止
3.
根節点から葉節点まで木をたどり,途中のラベルを連接する
 連接の結果得られる系列を符号語とする
12
構成例
4つの符号語を持つ2元符号を構成する
Step 1
Step 2
0
0
0
1
0
1
Step 3
0
1
1
0
1
1
00
01
10
11
構成された符号は {00, 01, 10, 11}
13
構成例(続き)
他の構成方法もアリ;
異なる木を使う,異なるラベル付けを行う...
0
1
0
1
0
1
0
C1={0, 10, 110, 111}
0
1
1
0
0
C2={0, 11, 101, 100}
1
1
0
0
1
0
1
1 0
C3={01, 000, 1011, 1010}
どのように作っても,語頭条件は保証される
 瞬時復号可能な符号となる
14
「最良な」瞬時復号可能符号
0
1
0
1
0
1
C1={0, 10, 110, 111}
0
1
0
1
0
1
0 1 0
C3={01, 000, 1011, 1010}
C1 のほうが,C3 よりもコンパクトな符号語表現を持つ
符号語の長さ = [1, 2, 3, 3]
もっとコンパクトな瞬時復号可能符号はあるか? たとえば
符号語の長さ= [1, 1, 1, 1]?
符号語の長さ = [1, 2, 2, 3]?
どこに壁がある?
符号語の長さ = [2, 2, 2, 3]?
15
クラフトの不等式
定理:
A) 2元符号 {1, … , } (| | =  とする)が瞬時復号可能なら,
2−1 + ⋯ + 2− ≤ 1 (クラフトの不等式)が成り立つ
... 次ページで証明
B) もし 2−1 + ⋯ + 2− ≤ 1なら,瞬時復号可能な
2元符号 {1, … , } で | | =  となるものが存在する
... 深さ  に葉節点を配置していけばよい
16
定理Aパートの証明
A) 2元符号 {1, … , } (| | =  とする)が瞬時復号可能なら,
2−1 + ⋯ + 2− ≤ 1 (クラフトの不等式)が成り立つ
証明:ℎ = max  とし,2ℎ−1 + ⋯ + 2ℎ− ≤ 2ℎ を示せばよい
高さℎの完全2分木を考える
符号語 =深さ  の節点,先祖にも子孫にも他の符号語ナシ
深さℎにある の子孫の数=2ℎ−
深さℎにある節点の総数=2ℎ
1
よって 2ℎ− ≤ 2ℎ
2
3
2ℎ
ℎ=4
2ℎ−2
2ℎ−3
2ℎ−4
17
具体例に戻って考える
できるだけコンパクトな瞬時復号可能な符号を作りたい
符号語の長さ = [1, 2, 2, 3]?
…2−1
+
2−2
+
2−2
+ 2−3
9
8
= >1
瞬時復号可能な符号は構成できない
符号語の長さ = [2, 2, 2, 3]?
7
8
…2−2 + 2−2 + 2−2 + 2−3 = < 1
瞬時復号可能な符号を構成可能...符号木を使えば簡単
18
次の段階へ
情報源符号化の基礎
一意復号可能性
瞬時復号可能性
ハフマン符号
ハフマン符号の構成法
ハフマン符号の最適性
ブロック符号化
情報源符号化定理
関連する話題
19
「コンパクトさ」の指標
情報をコンパクトに表現する符号を作りたい
1個の記号を表現する符号語の長さの期待値を小さくしたい
=
平均符号語長
記号
1
2
:

確率
1
2
:

符号語
1
2
:

長さ
1
2
:

平均符号語長は

  ビット
=1
(記号)
20
平均符号語長の計算例
記号
a1
a2
a3
a4
確率
0.4
0.3
0.2
0.1
C1 C2 C3
0 111 00
10 110 01
110 10 10
111 0 11
C1: 0.4×1+ 0.3×2+ 0.2×3+ 0.1×3 = 1.9
C2: 0.4×3+ 0.3×3+ 0.2×2+ 0.1×1 = 2.6
C3: 0.4×2+ 0.3×2+ 0.2×2+ 0.1×2 = 2.0
C1 が最も効率よく(=コンパクトに)情報を表現できる(はず)
21
ハフマン符号
ハフマンアルゴリズム:
平均符号語長の小さな瞬時復号可能符号を作る方法
1.
2.
M 個の節点を準備し,各節点に記号の発生
確率を付与する (節点 = サイズ 1の木)
David Huffman
1925-1999
木が一個になるまで,以下の操作を繰り返す
a. 確率最小の木を2個選択 ... T1, T2 とする
b. 新しい節点を導入し, T1, T2 を新節点の子とする
(二個の木を一個に併合)
c. T1, T2 の確率の和を,併合してできた木の確率とする
22
例
“資本の小さな会社の合併劇”
0.15
0.6
A
0.25
B
0.1
C
0.05
D
0.6
A
1.0
1 0.4
0
1 0.15
0
0 1
0.25 0.1
0.05
B
C
D
0.6
A
0.25
B
0.1
C
0.05
D
0.4
0.15
0.6
A
0.25
B
0.1
C
0.05
D
23
練習問題
A
B
C
D
E
確率 符号語
0.2
0.1
0.3
0.3
0.1
A
B
C
D
E
F
確率 符号語
0.3
0.2
0.2
0.1
0.1
0.1
「等長符号」と平均符号語長を比べると,ありがたみがわかる
24
符号構成の自由度について
ハフマンアルゴリズムの実行結果は,一意でない可能性も...
同じ確率を持つ節点が多数存在
枝へのラベル付けにも,自由度がある
異なる選択肢を取ると異なるハフマン符号ができあがる,が,
平均符号語長は,どの選択肢を取っても変わらない
0.4 0.2 0.2 0.1 0.1
a1 a2 a 3 a4 a5
0.4 0.2 0.2 0.1 0.1
a1 a2 a3 a4 a5
25
ここまでのまとめ
情報源符号化の基礎
一意復号可能性
瞬時復号可能性
ハフマン符号
ハフマン符号の構成法
ハフマン符号の最適性
ブロック符号化
情報源符号化定理
関連する話題
26
情報源符号が「最適」であるとは
情報源符号が目指すべきもの
瞬時復号可能性
平均符号語長の最小化
クラフトの不等式
2−1 + ⋯ + 2− ≤ 1
この制約の範囲内で,平均符号語長

 
=1
を最小化することを考える
27
あらすじ
1.
平均符号語長の下界を示す
2.
シャノン・ファノ符号の紹介
「下界に迫る」平均符号語長を持つ符号
ハフマン符号との関係
3.
ハフマン符号の最適性
4.
情報源の拡大と情報源符号化定理
Robert Fano
1917-
28
最初の目標
約束事:
定常無記憶情報源  の発生する記号を一個ずつ符号化
記号は通り,各記号の発生確率は 1, … , 
瞬時復号可能な符号を考え,平均符号語長を  で表す
補題1:平均符号語長は必ず  ≥ 1 () となる
シャノンの補助定理(chapter 1で紹介)を利用して証明
1 + ⋯ +   1 を満たす非負数  に対し,


− log 2  ≥
=1
− log 2 
=1
29
補題1の証明
補題1:平均符号語長は必ず  ≥ 1 () となる
符号語の長さを 1 , … ,  とし, = 2− とする
 = − log 2 

=
1 + ⋯ + 
= 2−1 + ⋯ + 2− ≤ 1
(クラフトの不等式)
 
(シャノンの補助定理)
=1

=

− log 2 
=1
≥
− log 2  = 1 ()
=1
30
補題1の意味するところ
補題1:平均符号語長は必ず  ≥ 1 () となる
情報源  の発生する記号を符号化するためには,
必ず 1  ビットの平均符号語長が必要
どれだけ高速なコンピュータや,どれだけスゴイ天才が
将来出現しても,1 ()ビットの壁を超えることはできない
エントロピー... 統計的に導かれた「情報理論的な量」
平均符号語長の下界...データ圧縮の限界という「操作的な量」
... 情報理論は,情報に関する「普遍的な物理法則」を与える
31
下界への到達可能性
補題1:平均符号語長は必ず  ≥ 1 () となる
1 ()は,あくまでも平均符号語長の「下界」
次の疑問... どこまで1 ()に迫ることができるのか?
補題2:平均符号語長が < 1() + 1となる符号を構成可能
シャノンとファノが,独立に発見した符号の構成法
⇒ シャノン・ファノ符号
(本講義では,シャノン・ファノ符号のアイデア部分だけを説明)
32
補題2の証明
補題2:平均符号語長が < 1() + 1となる符号を構成可能
5
符号の構成方法:
step 1:  = ⌈− log 2  ⌉として,符号語の 4
長さを決定する
3
step 2: 深さ 1 , … ,  に葉を持つ符号木を 2
構成する
1
step 3: 符号木から符号語を決定する
0
確認すべき事項:
本当に符号木が構成できるのか?
平均符号語長は?
− log 2 
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
⌈⌉…以上の整数

33
補題2の証明(続)
本当に符号木が構成できるのか?
=  はクラフトの不等式を満たすのか?
 = ⌈− log 2  ⌉ より  ≥ − log 2 
さらに変形すると,2− ≤ 2log2  = 
2−1 + ⋯ + 2− ≤ 1 + ⋯ +  = 1
平均符号語長は?
 < − log 2  + 1であることを利用する:

=

  <
=1
 (− log 2  + 1)
=1

=

− log 2  +
=1
 = 1  + 1
=1
34
補題2に関する補足
前スライドの証明では...符号木以降の議論を省略
シャノン・ファノ符号...具体的な符号木の作り方までを規定
確率を 2進数表記したときの,小数部に着目
「証明のために構成された符号」の色合いが強い
「一番効率が良い」わけではない
たとえば, = 2, 1 = 0.9, 2 = 0.1の場合...
シャノン・ファノ符号では,1 = 1, 2 = 4
ハフマン符号では,1 = 1, 2 = 1
35
補題1+2
補題1:平均符号語長は必ず  ≥ 1 () となる
どんな符号を使っても越えられない壁
補題2:平均符号語長が < 1() + 1となる符号を構成可能
シャノン・ファノ符号を使えば,下界に迫ることが可能
ハフマン符号の位置づけは?
vs.
36
ハフマン符号の最適性
最適符号 = 平均符号語長を最小にする瞬時符号可能符号
定理:ハフマン符号は最適符号である
... 予備的な補題 + 数学的帰納法で証明する
補題:ハフマン符号の符号木,最適符号の符号木とも,
確率最小の2記号は,最も深いレベルに兄弟として存在する
子が1個の節点は
...背理法で証明可能(証明略)
存在しないはず
もし,ここの確率が小さければ...
より深いところと交換して,
平均符号語長の削減が可能
37
証明:ハフマン符号は最適符号である
記号数  に関する帰納法で証明する
 = 1のとき ... 自明
 = 以下で定理の成立を仮定, =  + 1の場合を考える
ハフマン
符号の
符号木


平均符号語長
 ≥ opt のはず...
最適符号の
符号木
opt
+1

+1
確率最小の2記号を併合
 − ( + +1 )
 + +1
opt − ( + +1 )
 ≤ opt
したがって  = opt
 + +1
38
補題1+2,改良版
補題1:平均符号語長は必ず  ≥ 1 () となる
どんな符号を使っても越えられない壁
補題2:平均符号語長が < 1() + 1となる符号を構成可能
ハフマン符号を使えば,下界に迫ることが可能
1  ≤ opt = Huffman ≤ Shannon⋅Fano < 1  + 1
39
p.23 の例で確認
符号木を再帰的に構成し,符号を作る
平均符号語長は Huffman = 2.5
A
B
C
D
E
F
確率
0.3
0.2
0.2
0.1
0.1
0.1
符号語
00
10
11
010
0110
0111
エントロピーは
  = −0.3 log 2 0.3 − 0.2 log 2 0.2 − ⋯ − 0.1 log 2 0.1 = 2.45
1  ≤ opt = Huffman ≤ Shannon⋅Fano < 1  + 1
2.45
2.5
?
3.45
40
ここまでのまとめ
補題1:平均符号語長は必ず  ≥ 1 () となる
どんな符号を使っても越えられない壁
補題2:平均符号語長が < 1() + 1となる符号を構成可能
ハフマン符号を使えば,下界に迫ることが可能
1  ≤ opt = Huffman ≤ Shannon⋅Fano < 1  + 1
この +1 が気になる
41
ハフマン符号とブロック化
1個の記号を,1個の符号語に変換する
平均符号語長は,かならず1以上となる
2元情報源の符号化には向かない
A B A C C A
記号
確率
A
0.8
0 10 0 11 11 0
B
0.2
平均符号語長
C1 C2
0
1
1
0
1.0 1.0
複数の記号をまとめて符号化(ブロック符号化)すると...
1記号あたりの平均符号長を1以下にできるかも
2元情報源の符号化にもチャンスが... A B A C C A
10
1101 01
42
ブロック符号化のイメージ
記号の系列
ABCBCBBCAA...
ブロック化
ブロック化された AB CBC BB CAA...
記号の系列
等長ブロック化
非等長ブロック化
ブロック詳細化法
ランレングス法
ハフマン符号化
符号語系列
01 10 001 1101...
(実際には,符号語間のスペースはナシ...)
43
等長ブロック符号化の例(2-1)
確率 符号語
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
長さ2のブロックを考える
AAの発生確率 = 0.8×0.8=0.64 ....
平均符号長は
0.64×1 + 0.16×2 + ... + 0.04×3 = 1.56
記号一個当たりでは,1.56 / 2 = 0.78
⇒ 2元情報源でも,効率改善
44
等長ブロック符号化の例(2-2)
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
長さ3のブロックを考える
AAAの発生確率 = 0.83=0.512 ....
平均符号語長は
0.512×1 +... + 0.008×5 = 2.184
記号一個当たりでは,2.184 / 3 = 0.728
ブロック長 記号あたり平均符号語長
1
1.0
ブロック長を大きくすると,
2
0.78
1記号あたり平均符号語長は 3
0.728
小さくなる(効率が良くなる)
:
:
45
ブロック符号の平均符号長
ブロック長を大きくすると,1記号あたり平均符号語長は小さくなる
... ただの偶然の可能性も否定できない
個単位でブロック化した記号=次拡大情報源   の記号1個
⇒ 「記号を 1個ずつ符号化する」場合の
議論が適用できる
ブロック長  のときの平均符号語長を  とすると
平均符号語長は必ず  ≥ 1 (  ) となる
平均符号語長が  < 1   + 1となる符号を構成可能
46
不等式の変形
1   ≤  < 1   + 1
で割る
1  
 1   + 1
≤
<



極限を取る
1  

1   + 1
lim
≤ lim
< lim
→∞
→∞ 
→∞


極限エントロピーで表現する

  ≤
<  +

1記号あたりの平均符号語長
47
情報源符号化定理
情報源に対し,瞬時復号可能な符号を構成する
構成した符号の,1記号あたりの平均符号長をとする

  ≤
<  +

シャノンの情報源符号化定理
【逆定理】  < ()であるような符号は存在しない
【順定理】 が()に限りなく近い符号を構成することができる
48
情報源符号化定理の意味するところ
【逆定理】  < ()であるような符号は存在しない
⇒どれだけブロック長を大きくしても,エントロピーの壁は
越えられない
【順定理】 が()に限りなく近い符号を構成することができる
⇒ブロック長を大きく設定し,ハフマン符号を使えば,
いくらでも下界に近づくことができる
確率 符号語
0
A 0.8
1
B 0.2
H(S) = 0.723
ブロック長 1記号あたり平均符号長
1
1.0
2
0.78
3
0.728
:
:
0.723 + 
49
別視点からの説明
ブロック化すると,どうして効率が良くなるか?
理想的な符号語長は実数値  = −log 2 
1 = 0.8, 2 = 0.2 の場合,理想的な符号語の長さは...
0.81 + 0.22 → min
s.t. 2−1 + 2−2 ≤ 1
1 = − log 2 0.8 ≈ 0.322
2 = − log 2 0.2 ≈ 2.322
現実には,符号語長は整数値しか許されない
シャノン・ファノ符号の場合, = ⌈− log 2  ⌉
⌈− log 2  ⌉
倍になる
符号語長は,理想的な場合の
− log 2 
50
別視点からの説明(続)
15
確率値が大きくなると,
理想と現実のギャップが顕著に 10
⌈− log 2  ⌉
− log 2 
5

0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
0
ブロック化すると...
各記号の発生確率が比較的小さくなる
さらに...理想と現実の間に多少ギャップがあっても,
「1記号あたり」で考えるために で割れば,影響は小さくなる
51
ここまでのまとめ
シャノンの情報源符号化定理
【逆定理】  < ()であるような符号は存在しない
【順定理】 が()に限りなく近い符号を構成することができる
情報源をブロック化し,ハフマン符号を使えばよい
理論的に完結しているが,実用上の問題は残る
52
ここまでのまとめ
情報源符号化の基礎
一意復号可能性
瞬時復号可能性
ハフマン符号
ハフマン符号の構成法
ハフマン符号の最適性
ブロック符号化
情報源符号化定理
関連する話題
53
ブロック符号化法の実用性
効率面からは,ブロック化+ハフマン符号が最良な方法
ブロック長を大きくすれば,いくらでも理論限界値に近づける
実用面から見たデメリット:
記号の発生確率を,あらかじめ知っておく必要がある
(⇒ この問題については後述)
符号の定義(記号と符号語の対応表)が巨大になる
対応表1行を記憶するのに1バイト必要だとすると...
ブロック長 8...256バイト
ブロック長 16...64キロバイト
ブロック長 32...4ギガバイト
54
授業では省略
「ブロックの長さを揃えない」という選択肢
AAA
AAB
ABA
ABB
BAA
BAB
BBA
BBB
確率 符号語
0.512
0
0.128
100
0.128
101
0.032 11100
0.128
110
0.032 11101
0.032 11110
0.008 11111
確率 符号語
0
AAA 0.512
100
AAB 0.128
101
AB 0.16
0.2
11
B
ブロックの「長さ」を揃えると ...
いくつかのブロックは,非常に小さな
確率を持つことになる
そのようなブロックにも符号語が必要
ブロックの「発生確率」を揃えると ...
ブロックの長さはバラバラになる
「役に立たない対応関係」を撲滅
55
授業では省略
ブロックパターンの「選び方」
ブロックパターンの選び方がマズイと,「表現できない系列」が
発生することも ...
悪い例: {AAA, AAB, AB} をブロックパターンとすると
AABABAAB
AAB AB AAB
AABBBAAB
AAB ?
この問題を回避するアプローチ ...以下の二種が有効
ブロック詳細化方式
ランレングス符号化方式
56
授業では省略
ブロック詳細化方式
頻出パターンを細分化していく
1. 長さ1のパターンを用意する
2. 発生頻度の高いパターンを細分化し,分割する
3. 所望のパターン数になるまで 2 を繰り返す
例:P(A) = 0.8, P(B) = 0.2,パターン数を4にしたいとき
A
B
0.8
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} にブロック化可能
57
授業では省略
非等長ブロック符号化の性能評価
AAA
AAB
AB
B
0.512 0
0.128 100
0.16 101
0.2
11
平均符号語長の計算は,やや面倒...
「情報源 S から,ブロックがn 個発生」
と考える
S
0 101 0 11 101 ...
0.512n×1 + 0.128n×3 ...
= 1.776n ビット
符号化
AAA AB AAA B AB ...
0.512n×3 + 0.128n×3 ...
= 2.44n 個の記号
2.44n 個の記号が,1.776n ビットに符号化された
 記号あたり平均符号語長は 1.776n / 2.44n = 0.728 bit
...ブロック長 3の場合 と同程度の性能を,小さな対応表で実現
58
ランレングス符号化方式
記号のランにより,ブロックパターンを定義する
記号のラン(run):系列中の,同一記号からなる部分系列
ABBAAAAABAAAB
長さ1のAのラン
長さ0のAのラン
長さ3のAのラン
長さ5のAのラン
特定記号のランの長さだけ与えられれば,元の系列を復元可能
⇒ ランの長さを符号化しよう!
59
ラン長の上限
非常に長いランが発生することも...
⇒ランの長さに上限を設け,上限以上のランは短く分割して表現
上限を3とした場合
ラン長 表現方法
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が1個発生し,Bが発生
Aが0個発生し,Bが発生
Aが3個以上発生
Aが2個発生し,Bが発生
Aが3個以上発生
Aが0個発生し,Bが発生
60
ランレングスハフマン符号
ランレングスハフマン符号 (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
61
符号化例
S: 記憶のない2元定常情報源,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
62
符号化例(続)
ランレングスハフマン符号化(符号語数を8に設定)
ラン長 確率 符号語
ラン長 確率 符号語
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)
1記号あたりの平均符号語長は 2.466n / 5.216n = 0.47
63
関連する話題,さらに3題
ハフマン符号以外の符号化法について考える
装置化が簡単で効率が良い符号化法
算術符号化法
通報の発生確率が事前にわからない場合の符号化法
Lempel-Ziv法
許容範囲内での情報劣化と引き換えに,効率を稼ぐ符号化法
画像や音声の符号化法について
ある程度独立した3つの話題の紹介
64
授業では省略
算術符号化法
装置化が簡単で効率が良い符号化法
65
授業では省略
符号化方式の実現について
符号化 = 記号と符号語との対応付け
性能確保のためには,大きな対応表が必要になる
「静的」アプローチ
対応表を事前に作成し,符号化側,復号側で事前に共有
大きな記憶装置・容量が必要
「動的」アプローチ
対応表の必要な部分を,on-the-flyで構成する
⇒ よりコンパクトな実装が可能となる
算術符号(arithmetic code)... シャノン・ファノ符号の実現例
66
授業では省略
算術符号:基本的な考え方
記憶のない2元定常情報源:   = ,   = 1 − 
長さ  の記号系列の符号化を考える ⇒ 2 通りの記号系列
 = 0.7,  = 3 の場合
番号
0
1
2
3
4
5
6
7
()
0.343
0.147
0.147
0.063
0.147
0.063
0.063
0.027
↑
発生確率

AAA
AAB
ABA
ABB
BAA
BAB
BBA
BBB
8通りの系列 , … , 7
()
0
辞書式に並んでいること
0.343
( ) :系列 の発生確率
0.490
0.637
( ) :系列の累積発生確率
0.700
−1


=

=0  
0.847
=  −1 +  −1
0.910
0.973
↑
累積確率...着目系列より小さい系列の発生確率
67
授業では省略
アイデア:系列と区間
各系列に対し,[0,1]の部分区間を対応付け可能
0
0.5
0.343
番号
0
1
2
3
4
5
6
7
AAA

AAA
AAB
ABA
ABB
BAA
BAB
BBA
BBB
()
0.343
0.147
0.147
0.063
0.147
0.063
0.063
0.027
区間のサイズ
0.147
AAB
()
0
0.343
0.490
0.637
0.700
0.847
0.910
0.973
1.0
0.0630.063 0.027
0.147
0.063
0.147
ABA
ABB
BAA BAB BAB BBB
系列  は,区間
 = [( ), ( ) + ( ))を占有
 を, 内の代表点   で表現
代表点  をどう選ぶ?
実数値  をどう表現する?
区間の左端
68
授業では省略
区間の木表現と累積確率計算
系列と実数値の対応付け:二方向への変換が必要
【符号化】 系列  から,区間内実数値  を求める
【復号】 実数値  から,対応する系列  を求める
⇒ どちらも、区間の木構造表現を利用して計算すれば良い

A
AA
AAA
AAB
0.343
B
AB
ABA
ABB
0.147
BA
BAA
0.147
BAB
0.063
AB
BAB
0.147
BBB
0.0630.063 0.027
69
授業では省略
【符号化】 系列  から区間内実数値  を求める
( ), ( ) の値を再帰的に計算していく
() = 1, () = 0とする( は空系列)
 に対して () = (), () = ()
 に対して   =   1 –  , () = () + ()
ABBの区間は?
() = 1
() = 0 
() = 0.7 A
() = 0
AA
 = () = 0.7
() ()
() ()
B
AB
ABA
()
()
() = 0.21
() = 0.49
ABB () = 0.063
() = 0.637
ABB の占有区間は
[0.637, 0.637 + 0.063)
70
授業では省略
【符号化】 系列  から区間内実数値  を求める
占有区間  は特定できた ... どの  ∈  を代表値とするか
 の表現長は,短ければ短いほど良い
 内で,表現長が最小のものを選びたい
( ) + ( ) の小数点以下 ⌈– log2  ⌉ ビットを  にする
()
+ ()
( + 1)
0.aa...aaa...a
+0.00...0bb...b
0.aa...acc...c
0.aa...ac
x
x = aa...ac
0.aa...aaa...a
0.aa...ac
0.aa...acc...c
この桁未満を
切り捨てる
 の長さ ≈ – log2( )
ほぼ理想的な長さ
71
授業では省略
【復号】 実数値  から対応する系列  を求める
与えられた実数値から,を含む区間に対応する系列を求める
符号化のときと,ほぼ同種の再帰計算を行えばよい
 = 0.600
()
() = 1
() = 0 
() = 0.7 A
() = 0
AA
() = 0.147 ABA
() = 0.49
B () = 0.7
AB
ABB
()
() ()
() ()
() = 0.21
() = 0.49
(左右の区切り)
() = 0.637
「 = 0.600 は,系列ABA の占有区間に属する」
72
授業では省略
算術符号化の性能
発生確率()の系列は,⌈− log 2   ⌉ビットに符号化される
平均符号語長は
1
1
() − log 2 ( ) ≈
−  log 2   = ()




∈
∈
対応表を使わないのに,ほぼ理論限界を達成
デメリット:
精度の高い計算を繰り返し行う必要がある
⇒ 乗算を用いない(近似)計算法も研究されている
73
Lempel-Ziv法
通報の発生確率が事前にわからない場合の符号化法
74
通報の発生確率について
ここまでの議論...
記号の発生確率が,あらかじめわかる場合を想定
現実世界の通報系列...
各記号の発生確率がわからないケースも多い
単純な解決法として,2スキャン方式がある
1回目のスキャンで各記号の発生確率を測定
2回目のスキャンで符号化
⇒ 符号化遅延の発生,対応表を添付する必要性が生じる
75
Lempel-Ziv 法
記号の発生確率が不明でも,効率よい符号化を実現する方式:
LZ77法
lha, gzip, zip, zoo 等の圧縮ツールで採用
LZ78法
compress, arc, stuffit等の圧縮ツールで採用
LZW法
GIF, TIFF等の画像フォーマットで採用
どのような情報源に対しても効率が良い
⇒ ユニバーサル符号化 (universal coding)
76
LZ77方式
A. Lempel, J. Ziv により,1977年に提案された方式
記号の部分系列を,過去に出現したパターンとの最長一致
により表現していく
アルゴリズム概要
系列を先頭から動的にブロック化し、符号化する
一つのブロックを,(, , ) の3項組で表現
「 文字前から始まる長さの系列に を追加したもの」
–
– + 
–1 0
符号化の完了した系列

– 1 
77
LZ77の符号化例
ABCBCDBDCBCDを符号化する
記号
A
B
C
B
C
D
B
D
C
B
C
D
状況
初出現
初出現
初出現
2文字前と同一
2文字前と同一
2文字前とは異なる
3文字前と同一
3文字前とは異なる
6文字前と同一
6文字前と同一
6文字前と同一
6文字前と同一
符号語
(0, 0, A)
(0, 0, B)
(0, 0, C)
(2, 2, D)
(3, 1, D)
(6, 4, *)
78
LZ77の復号例
(0, 0, A), (0, 0, B), (0, 0, C), (2, 2, D), (3, 1, D), (6, 4, *) を復号
得られた符号語から,もとの記号系列を逐次構成していく
問題点...整数値の表現をどうする?
大きな整数は,それなりに大きな表現長となってしまう
表現長を超えるようなブロックは,分割して表現する必要あり
⇒ LZ78 法に比べると,若干の効率ロスがある
79
LZ78方式
A. Lempel, J. Ziv により,1978年に提案された方式
パターンを,(, , ) の3項組ではなく,(, ) の2項組で表現
「 個前のブロックに,文字  を追加したもの」

–
–1
0
符号化の完了した系列
80
LZ78の符号化例
ABCBCBCDBCDEを符号化する
記号
A
B
C
B
C
B
C
D
B
C
D
E
状況
初出現
初出現
初出現
2つ前のブロックと同一
符号語
(0, A)
(0, B)
(0, C)
ブロック番号
1
2
3
(2, C)
4
(1, D)
5
(1, E)
6
1つ前のブロックと同一
1つ前のブロックと同一
81
LZ78の復号例
(0, A), (0, B), (0, C), (2, C), (1, D), (1, E)を復号
得られた符号語から,もとの記号系列を逐次構成していく
LZ77法より,符号語がコンパクト
一つの符号語が表現するブロックサイズに上限がない
⇒ LZ77 法よりも,若干優れた効率を発揮
82
ユニバーサル符号化について:まとめ
LZ法では,適応的にパターン・符号語の対応表を構成する
記号の発生確率がわからなくても,高い性能を発揮
記憶のある情報源から発生する通報にも,自然に対応可能
LZW法には,UNISYS社が主張する特許問題が存在した
⇒ 2004 年に特許期限が切れ,自由に利用可能に
83
授業では省略
画像や音声の符号化法について
許容範囲内での情報劣化と引き換えに,効率を稼ぐ符号化法
84
授業では省略
符号化の可逆性
ここまでで考えてきた符号化法...
符号化したものを復号すれば,元の情報と完全に同一の
記号系列が得られる
⇒ 可逆符号化,無歪み符号化 (reversible, lossless coding)
可逆性に関する条件を緩めれば,さらに効率が改善できるかも
⇒ 非可逆符号化,有歪み符号化 (non-reversible, lossy coding)
画像や音声等,最終的に人間が受容する情報の符号化を念頭
本講義では,個々の符号化方式については述べない
(それぞれ専門の講義科目を履修のこと)
85
授業では省略
情報源符号化定理,再考
シャノンの情報源符号化定理:
【逆定理】  < ()であるような符号は存在しない
【順定理】 が()に限りなく近い符号を構成することができる
X?
X
encoder
Y
符号化器 = 通信路と考えると
入力  = 記号, 出力  = 符号語
可逆符号では,  を知れば  を一意に特定可能
エントロピーは,()から0に...相互情報量(; ) = ()
“符号語は,サイズ(; )の情報を入れる容器である”
... 容器のサイズは,中身のサイズ(; ) = () 以下にできない
86
授業では省略
非可逆符号の場合
非可逆符号では,
 を知っても, に関して曖昧さが残る
エントロピーは 0 にならず,相互情報量は (; ) < ()
X?
X
encoder
Y
“符号語は,サイズ(; )より小さな情報を入れる容器である”
容器サイズ(符号語長)< () とできる可能性もある
 数学的な議論は,もっと込入っている
 rate-distortion theory
87
chapter 2 のまとめ
情報源符号化の基礎
一意復号可能性
瞬時復号可能性
ハフマン符号
ハフマン符号の構成法
ハフマン符号の最適性
ブロック符号化
情報源符号化定理
関連する話題
88

similar documents