Document

Report
レポート課題
4/25出題,5/9提出締切
問題1:
|  ,  = |   , |  ,  = |   を利用
各種エントロピーの定義まで立ち入っての式計算が必要
問題2:
(電子シラバスだけでなく)講義ページも参照すべき
http://isw3.naist.jp/~kaji/lecture/
1
前回 4/22 の練習問題
定常確率分布を求めよ
010 が出力される確率を求めよ
極限エントロピー ()を求めよ
A
0/0.4 0/0.5
B
0/0.8
前回スライドの p.24~の情報源と
(本質的には)同じでした...すみません
1/0.2
1/0.6
C
1/0.5
定常確率分布
0 0.4 0.6
1 , 2 , 3 = (1 , 2 , 3 ) 0 0.8 0.2
0.5 0.5 0
1 + 2 + 3 = 1
1 , 2 , 3
= (0.1,0.7,0.2)
2
前回 4/22 の練習問題(続)
010 が出力される確率
状態 A から 010...
0.4 × 0.2 × 0.5 = 0.04
状態 B から 010...
0.8 × 0.2 × 0.5 = 0.08
状態 C から 010...
0.5 × 0.6 × 0.5 = 0.15
A
0/0.4 0/0.5
B
0/0.8
1/0.2
1/0.6
C
1/0.5
定常確率分布 1 , 2 , 3 = (0.1,0.7,0.2)で重みを付けて...
0.1 × 0.04 + 0.7 × 0.08 + 0.2 × 0.15 = 0.09
3
前回 4/22 の練習問題(続々)
極限エントロピー ()
0/0.4
A
0/0.4 0/0.5
B
0/0.8
1/0.2
1/0.5
A
1/0.6
1/0.6
0/0.5
0/0.8
C
B
C
1/0.2
1/0.5
定常確率
× 0.1 = 0.0971
状態A: ℋ 0.4 = 0.971
× 0.7 = 0.5054
状態B: ℋ 0.8 = 0.722
× 0.2 = 0.2000
状態C: ℋ 0.5 = 1.000
0.8025
4
chapter 2:
情報をコンパクトに表現する
5
chapter 2の目的
情報源からの記号(列)を,効率よく(コンパクトに)符号化する
情報源符号化
データ圧縮
0101101
符号化
情報源符号化の目的:
通信に適した表現方式への変換
情報の中の無駄な部分を整理し,捨て去る
情報源
目標とする符号化方式:
できるだけ正確に元の情報を復元できること
できるだけコンパクトな情報表現を与えること
6
議論の順序
情報源符号化の基礎
一意復号可能性
瞬時復号可能性
ハフマン符号
ハフマン符号の構成法
ハフマン符号の拡張
データ圧縮の理論限界
今日の目標
7
用語について
はじめに,情報源の記号ごとに符号化を行う方式を考える
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 は符号語ではない
8
符号化と復号
符号化... 与えられた記号から,対応する符号語を求めること
復号 ... 与えられた符号語から,対応する記号を求めること
晴
曇
雨
符号化
復号
00
010
101
encode = 符号化
decode = 復号
符号語間に,スペース,コンマ等の区切り記号は使わない
01000101101はOK, 010 00 101 101 はNG
「区切り記号 = 第3の文字」
⇒ 「3元」符号を考えることになってしまう
9
一意復号可能性
符号は,一意に復号可能でないといけない
異なる記号が同じ符号語を持つのは,当然NG
異なる記号が異なる符号語を持つ,だけでも不十分
異なる記号系列は,異なる0-1系列に符号化されること
a1
a2
a3
a4
C1
00
10
01
11
OK
C2
0
01
011
111
OK
C3
0
10
11
0
NG
C4
0
10
11
01
NG
C4 を使う場合...
a1 a3 a1
0110
a4 a 2
10
一意性だけで十分か?
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秒後でも,最初の記号すら確定できない
 受信データのバッファが必要,復号遅延の問題...
 動画ダウンロードだったら,どうなるか
11
瞬時復号可能性
実用的なシステムでは,瞬時に復号可能であることが望ましい
「符号語のパターンが出現したら,即時に復号して良い」
一意復号可能の「上位」の性質
「瞬時復号可能」ならば「一意復号可能」である
符号  が瞬時復号可能であるとは...
任意の系列  ∈ 0,1 ∗ に対し,
 = 1 1 となる符号語1 ∈ が存在するならば,
 = 2 2 となる他の符号語2 ∈  が存在しない
1
1
=
2
2
12
語頭条件
符号が瞬時復号可能でないならば,  = 1 1 = 2 2 となる
系列 ∈ 0,1 ∗ と,二つの異なる符号語 1 , 2 が存在する
1
1
=
2
2
1 は2 の語頭である,という
補題:
符号 C が瞬時復号可能である必要十分条件は,
他の符号語の語頭となる符号語が存在しないこと
(prefix condition, 語頭条件)
a1
a2
a3
“0” は “01” と “011”の語頭
“01” は “011”の語頭 a4
C2
0
01
011
111
13
雑談:語頭条件とユーザインタフェース
語頭条件は,情報理論以外でも重要
Palm Vx
1999発売
graffiti (ver. 1)
すべて一筆書きでOK
Sony Clie PEG-TH55
2004年発売
graffiti (ver. 2)
2画の文字が出現
語頭条件に反する
“3-1”と書いたつもりが “3+” に...
14
語頭条件を確保するには
語頭条件を満たす符号の作り方:
全ての符号語を,同じ長さで設計する; 等長符号
符号語の最後に「特殊パターン」を置く
C = {011, 1011, 01011, 10011} ; “コンマ符号”
... どちらも,(後述する)効率がよくない
木構造を利用して符号語を選ぶ (「符号木」)
2元符号の場合,次数が2の木を利用
元符号の場合,次数がの木を利用
次数3の
符号木
15
符号の構成法(元の場合)
個の符号語を持ち,語頭条件を満たす元符号の作り方
1.
2.
3.
葉を個持つような,次数の木を構成する
の各枝に,0から − 1の値をラベル付けする
兄弟が同じラベルを持つことは禁止
根節点から葉節点まで木をたどり,途中のラベルを連接する
 連接の結果得られる系列を符号語とする
16
構成例
 = 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}
17
構成例(続き)
他の構成方法もアリ;
異なる木を使う,異なるラベル付けを行う...
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}
どのように作っても,語頭条件は保証される
 瞬時復号可能な符号となる
18
「最良な」瞬時復号可能符号
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] vs. [2, 3, 4, 4]
もっとコンパクトな瞬時復号可能符号はあるか? たとえば
符号語の長さ= [1, 1, 1, 1]?
符号語の長さ = [1, 2, 2, 3]?
どこに壁がある?
符号語の長さ = [2, 2, 2, 3]?
19
クラフトの不等式
定理:
A) 元符号 {1, … , } (| | =  とする)が瞬時復号可能なら,
 −1 + ⋯ +  − ≤ 1 (クラフトの不等式)が成り立つ
... 次ページで証明
B) もし  −1 + ⋯ +  − ≤ 1なら,瞬時復号可能な
元符号 {1, … , } で | | =  となるものが存在する
... 深さ  に葉節点を配置していけばよい
20
定理Aパートの証明( = 2の場合)
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
21
具体例に戻って考える
できるだけコンパクトな瞬時復号可能な 2元符号を作りたい
符号語の長さ = [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
瞬時復号可能な符号を構成可能...符号木を使えば簡単
22
次の段階へ
情報源符号化の基礎
一意復号可能性
瞬時復号可能性
ハフマン符号
ハフマン符号の構成法
ハフマン符号の拡張
データ圧縮の理論限界
23
「コンパクトさ」の指標
情報をコンパクトに表現する符号を作りたい
1個の記号を表現する符号語の長さの期待値を小さくしたい
=
平均符号語長
記号
1
2
:

確率
1
2
:

符号語
1
2
:

長さ
1
2
:

平均符号語長は

  ビット
=1
(記号)
24
平均符号語長の計算例
記号
1
2
3
4
確率
0.4
0.3
0.2
0.1
1 2 3
0 111 00
10 110 01
110 10 10
111 0 11
1: 0.4×1+ 0.3×2+ 0.2×3+ 0.1×3 = 1.9
2: 0.4×3+ 0.3×3+ 0.2×2+ 0.1×1 = 2.6
3: 0.4×2+ 0.3×2+ 0.2×2+ 0.1×2 = 2.0
1 が最も効率よく(=コンパクトに)情報を表現できる(はず)
25
ハフマン符号
ハフマンアルゴリズム:
平均符号語長の小さな瞬時復号可能符号を作る方法
1.
2.
M 個の節点を準備し,各節点に記号の発生
確率を付与する (節点 = サイズ 1の木)
David Huffman
1925-1999
木が一個になるまで,以下の操作を繰り返す
a. 確率最小の木を二個選択 ... T1, T2 とする
b. 新しい節点を導入し, T1, T2 を新節点の子とする
(二個の木を一個に併合)
c. T1, T2 の確率の和を,併合してできた木の確率とする
26
例
“資本の小さな会社の合併劇”
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
27
練習問題
A
B
C
D
E
確率 符号語
0.2
0.1
0.3
0.3
0.1
「等長符号」と平均符号語長を比べると,ありがたみがわかる
28
符号構成の自由度について
ハフマンアルゴリズムの実行結果は,一意でない可能性も...
同じ確率を持つ節点が多数存在
枝へのラベル付けにも,自由度がある
異なる選択肢を取ると異なるハフマン符号ができあがる,が,
平均符号語長は,どの選択肢を取っても変わらない
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
29
ここまでのまとめ
情報源符号化の基礎
一意復号可能性
瞬時復号可能性
ハフマン符号
ハフマン符号の構成法
ハフマン符号の拡張
データ圧縮の理論限界
30
練習問題
右図に示す記号に対し
ハフマン符号を構成し,
その平均符号語長を求めよ
A
B
C
D
E
F
確率 符号語
0.3
0.2
0.2
0.1
0.1
0.1
31
レポート課題
4/25出題,5/9提出締切
問題1:
|  ,  = |   , |  ,  = |   を利用
各種エントロピーの定義まで立ち入っての式計算が必要
問題2:
(電子シラバスだけでなく)講義ページも参照すべき
http://isw3.naist.jp/~kaji/lecture/
32

similar documents