前回の復習 情報をコンパクトに表現するための符号化方式を考える 情報源符号化における基礎的な性質 一意復号可能性 瞬時復号可能性 クラフトの不等式 2 l 1 + + 2 l M 1 ハフマン符号の構成法 (2 元符号の場合 ) D. Huffman 1
前回の練習問題 : ハフマン符号 符号木を再帰的に構成し, 符号を作る A B C D E F 確率 0.3 0.2 0.2 0.1 0.1 0.1 符号語 0.3 0.2 0.2 0.1 0.1 0.1 A B C D E F 平均符号語長は... 0.3 + 0.2 0.2 + 0.1 +0.1 +0.1 = 2
今日の講義の方向性 情報源符号が目指すべきもの 瞬時復号可能性 クラフトの不等式 2 l 1 + + 2 l M 1 平均符号語長の最小化 この制約の範囲内で, 平均符号語長 M p i l i i=1 を最小化することを考える 3
あらすじ 1. 平均符号語長の下界を示す 2. シャノン ファノ符号の紹介 下界に迫る 平均符号語長を持つ符号 ハフマン符号との関係 3. 情報源の拡大と情報源符号化定理 Robert Fano 1917-4
最初の目標 前回からの お約束 定常無記憶情報源 S の発生する記号を一個ずつ符号化 記号は M 通り, 各記号の発生確率は p 1,, p M 瞬時復号可能な符号を考え, 平均符号語長を L で表す 補題 1: 平均符号語長は必ず L H 1 (S) となる シャノンの補助定理 (2 回目の講義で紹介 ) を利用して証明 q 1 + + q M 1 を満たす非負数 q i に対し, M M p i log 2 q i p i log 2 p i i=1 i=1 5
補題 1 の証明 補題 1: 平均符号語長は必ず L H 1 (S) となる 符号語の長さを l 1,, l M とし,q i = 2 l i とする l i = log 2 q i M L = p i l i i=1 M = p i log 2 q i i=1 q 1 + + q M = 2 l 1 + + 2 l M 1 ( クラフトの不等式 ) M i=1 ( シャノンの補助定理 ) p i log 2 p i = H 1 (S) 6
補題 1 の意味するところ 補題 1: 平均符号語長は必ず L H 1 (S) となる 情報源 S の発生する記号を符号化するためには, 必ず H 1 S ビットの平均符号語長が必要 どれだけ高速なコンピュータや, どれだけスゴイ天才が 将来出現しても,H 1 (S) ビットの壁を超えることはできない エントロピー... 統計的に導かれた 情報理論的な量 平均符号語長の下界... データ圧縮の限界という 操作的な量... 情報理論は, 情報に関する 普遍的な物理法則 を与える 7
下界への到達可能性 補題 1: 平均符号語長は必ず L H 1 (S) となる H 1 (S) は, あくまでも平均符号語長の 下界 次の疑問... どこまで H 1 (S) に迫ることができるのか? 補題 2: 平均符号語長が L < H 1 (S) + 1 となる符号を構成可能 シャノンとファノが, 独立に発見した符号の構成法 シャノン ファノ符号 ( 本講義では, シャノン ファノ符号のアイデア部分だけを説明 ) 8
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 補題 2 の証明 補題 2: 平均符号語長が L < H 1 (S) + 1 となる符号を構成可能 符号の構成方法 : x x 以上の整数 step 1: l i = log 2 p i として, 符号語の長さを決定する step 2: 深さ l 1,, l M に葉を持つ符号木を構成する step 3: 符号木から符号語を決定する 5 4 3 2 1 0 log 2 p i log 2 p i 確認すべき事項 : 本当に符号木が構成できるのか? 平均符号語長は? p i 9
補題 2 の証明 ( 続 ) 本当に符号木が構成できるのか? = l i はクラフトの不等式を満たすのか? l i = log 2 p i より l i log 2 p i さらに変形すると,2 l i 2 log 2 p i = p i 2 l 1 + + 2 l M p 1 + + p M = 1 平均符号語長は? l i < log 2 p i + 1であることを利用する : M M L = p i l i < p i ( log 2 p i + 1) i=1 i=1 M M = p i log 2 p i + p i = H 1 S + 1 i=1 i=1 10
補題 2 に関する補足 前スライドの証明では... 符号木以降の議論を省略 シャノン ファノ符号... 具体的な符号木の作り方までを規定確率を 2 進数表記したときの, 小数部に着目 証明のために構成された符号 の色合いが強い 一番効率が良い わけではないたとえば,M = 2, p 1 = 0.9, p 2 = 0.1の場合... シャノン ファノ符号では,l 1 = 1, l 2 = 4 ハフマン符号では,l 1 = 1, l 2 = 1 11
補題 1+2 補題 1: 平均符号語長は必ず L H 1 (S) となる どんな符号を使っても越えられない壁 補題 2: 平均符号語長が L < H 1 (S) + 1 となる符号を構成可能 シャノン ファノ符号を使えば, 下界に迫ることが可能 ハフマン符号の位置づけは? vs. 12
ハフマン符号の最適性 最適符号 = 平均符号語長を最小にする瞬時符号可能符号 定理 : ハフマン符号は最適符号である... 予備的な補題 + 数学的帰納法で証明する 補題 : ハフマン符号の符号木, 最適符号の符号木とも, 確率最小の 2 記号は, 最も深いレベルに兄弟として存在する... 背理法で証明可能 ( 証明略 ) もし, ここの確率が小さければ... 子が 1 個の節点は存在しないはず より深いところと交換して, 平均符号語長の削減が可能 13
証明 : ハフマン符号は最適符号である 記号数 M に関する帰納法で証明する M = 1のとき... 自明 M = N 以下で定理の成立を仮定,M = N + 1の場合を考える ハフマン符号の符号木 L 平均符号語長 L L opt のはず... L opt 最適符号の符号木 p N p N+1 p N p N+1 記号数 N + 1 記号数 N 確率最小の 2 記号を併合 L (p N + p N+1 ) L opt (p N + p N+1 ) p N + p N+1 これより L L opt したがって L = L opt p N + p N+1 14
補題 1+2, 改良版 補題 1: 平均符号語長は必ず L H 1 (S) となる どんな符号を使っても越えられない壁 補題 2: 平均符号語長が L < H 1 (S) + 1 となる符号を構成可能 ハフマン符号を使えば, 下界に迫ることが可能 H 1 S L opt = L Huffman L Shannon Fano < H 1 S + 1 15
2 ページの例で確認 符号木を再帰的に構成し, 符号を作る 平均符号語長は L Huffman = 2.5 エントロピーは H S = 0.3 log 2 0.3 0.2 log 2 0.2 0.1 log 2 0.1 = 2.45 A B C D E F 確率 0.3 0.2 0.2 0.1 0.1 0.1 符号語 00 10 11 010 0110 0111 H 1 S L opt = L Huffman L Shannon Fano < H 1 S + 1 2.45 2.5? 3.45 16
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 シャノン ファノ符号の場合 5 4 3 2 1 0 l i = log 2 p i log 2 p i p i A B C D E F 確率 0.3 0.2 0.2 0.1 0.1 0.1 l i 2 3 3 4 4 4 符号語 00 010 100 1011 1100 1110 vs. ハフマン 00 10 11 010 0110 0111 L Shannon Fano = 0.3 2 + + 0.1 4 = 3.0 H 1 S L opt = L Huffman L Shannon Fano < H 1 S + 1 2.45 2.5 3.0 3.45 17
ここまでのまとめ 補題 1: 平均符号語長は必ず L H 1 (S) となる どんな符号を使っても越えられない壁 補題 2: 平均符号語長が L < H 1 (S) + 1 となる符号を構成可能 ハフマン符号を使えば, 下界に迫ることが可能 H 1 S L opt = L Huffman L Shannon Fano < H 1 S + 1 この +1 が気になる 18
お約束 を破る : 符号化の単位とブロック化 1 個の記号を,1 個の符号語に変換する A 0 平均符号語長は, 必ず 1 以上となる 2 元情報源の符号化を考えても, 意味がない B 10 A 0 C 11 C 11 A 0 記号確率 A 0.8 B 0.2 平均符号語長 C 1 0 1 1.0 C 2 1 0 1.0 複数の記号をまとめて符号化 ( ブロック符号化 ) すると... 1 記号あたりの平均符号長を1 以下にできるかも... 2 元情報源の符号化にもチャンスが... A B A C C A 10 1101 01 19
ブロック符号化のイメージ 記号の系列 ABCBCBBCAA... ブロック化 ブロック化された記号の系列 AB CBC BB CAA... ハフマン符号化 符号語系列 01 10 001 1101... ( 実際には, 符号語の間のスペースはナシ...) 20
ブロック符号化の例 (2-1) A B 確率 0.8 0.2 符号語 0 1 平均符号語長は 0.8 1 + 0. 2 1 = 1.0 AA AB BA BB 確率 0.64 0.16 0.16 0.04 符号語 0 10 110 111 長さ2のブロックを考える AAの発生確率 = 0.8 0.8=0.64... 平均符号語長は 0.64 1 + 0.16 2 +... + 0.04 3 = 1.56 記号 1 個当たりでは,1.56 / 2 = 0.78 2 元情報源でも, 効率改善 21
ブロック符号化の例 (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 ブロック長を大きくすると, 1 記号あたり平均符号語長は小さくなる ( 効率が良くなる ) 長さ 3 のブロックを考える AAA の発生確率 = 0.8 3 =0.512... 平均符号語長は 0.512 1 +... + 0.008 5 = 2.184 記号 1 個当たりでは,2.184 / 3 = 0.728 ブロック長 1 2 3 : 1 記号あたり平均符号語長 1.0 0.78 0.728 : 22
ブロック符号の平均符号長 ブロック長を大きくすると,1 記号あたり平均符号語長は小さくなる... ただの偶然? n 個単位でブロック化した記号 =n 次拡大情報源 S n の記号 1 個 記号を 1 個ずつ符号化する 場合の 議論が適用できる ブロック長 n のときの平均符号語長を L n とすると 平均符号語長は必ず L n H 1 (S n ) となる平均符号語長が L n < H 1 S n + 1 となる符号を構成可能 23
不等式の変形 H 1 S n L n < H 1 S n + 1 n で割る H 1 S n n L n n < H 1 S n + 1 n H 1 S n lim n n 極限を取る L n lim n n < lim H 1 S n + 1 n n 極限エントロピーで表現する H S L n n < H S + ε 1 記号あたりの平均符号語長 24
情報源符号化定理 情報源 S に対し, 瞬時復号可能な符号を構成する 構成した符号の,1 記号あたりの平均符号長を L とする H S L n n < H S + ε シャノンの情報源符号化定理 逆定理 L < H(S) であるような符号は存在しない 順定理 L が H(S) に限りなく近い符号を構成することができる 25
情報源符号化定理の意味するところ 逆定理 L < H(S) であるような符号は存在しない どれだけブロック長を大きくしても, エントロピーの壁は 越えられない 順定理 L が H(S) に限りなく近い符号を構成することができる ブロック長を大きく設定し, ハフマン符号を使えば, いくらでも下界に近づくことができる A B 確率 0.8 0.2 符号語 0 1 H(S) = 0.723 ブロック長 1 2 3 : 一通報あたり平均符号長 1.0 0.78 0.728 : 0.723 + ε 26
別視点からの説明 ブロック化すると, どうして効率が良くなるか? 理想的な符号語長は実数値 l i = log 2 p i p 1 = 0.8, p 2 = 0.2 の場合, 理想的な符号語の長さは... 0.8l 1 + 0.2l 2 min s.t. 2 l 1 + 2 l 2 1 l 1 = log 2 0.8 0.322 l 2 = log 2 0.2 2.322 現実には, 符号語長は整数値しか許されない シャノン ファノ符号の場合,l i = log 2 p i 符号語長は, 理想的な場合の log 2 p i log 2 p i 倍になる 27
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 別視点からの説明 ( 続 ) 確率値が大きくなると, 理想と現実のギャップが顕著に 15 10 5 log 2 p i log 2 p i 0 p i ブロック化すると... 各記号の発生確率が比較的小さくなる 理想と現実の間に多少ギャップがあっても, 1 記号あたり で考えるために n で割れば, 影響は小さくなる 28
本日のまとめ シャノンの情報源符号化定理 逆定理 L < H(S) であるような符号は存在しない 順定理 LがH(S) に限りなく近い符号を構成することができる情報源をブロック化し, ハフマン符号を使えばよい 理論的には完結しているが, 実用上の問題は残る符号化 復号の ( 時間 空間 ) 計算量削減前提条件の緩和 ( 確率分布が未知のケース etc.) 可逆でない 情報源符号化 続きは,III 期の 符号理論 で... 29
練習問題 ハフマン符号を構成するプログラムを作成せよ さらに, 拡大情報源に対して利用できるよう改良せよ 30