前回の練習問題１２ページの例において，３次，４次のエントロピーを求めよ．可能であれば，n 次エントロピーを計算するプログラムを書け．以下を示せ I(X; Y) = H(X) – H(X | Y) I(X; Y) = I(Y; X) I(X; Y) = H(X) + H(Y) – H(X, Y) http://narayama.naist.jp/~kaji/lecture/ に解答例，プログラム掲載 1 前回の補足マルコフ情報源の（極限）エントロピー：各状態について，その状態を記憶のない情報源と考え，極限エントロピー（一次エントロピー）を計算すればよい ... 厳密には「なぜこれで良いか」を考える必要がある説明資料（証明概要）を http://narayama.naist.jp/~kaji/lecture/ に掲載しました 2 comments to foreign students To help understanding this class, I try to provide English notes in the PowerPoint slide file. Download ppt files from http://narayama.naist.jp/~kaji/lecture/ and check notes in the file. 3 第二部：情報をコンパクトに表現する情報に含まれるムダを削り，情報を圧縮する情報源から発生した通報を記録するときには... 計算機で扱いやすい文字を使って表現しないといけない ⇒ 適切に符号化 (encode)する必要があるどんな符号化でもＯＫ？できるだけ正確に記録しないとダメ（⇒ 第二部＋第三部）できるだけ効率的に記録しないとダメ記録に必要となる手間，時間，データ量... を節約したい 4 情報源符号化情報源符号化 (source coding）：情報源から発生した通報（または通報の系列）を，記録系や処理系で利用可能な記号系列に変換すること正確で手間のかからない符号化一意復号可能性，瞬時復号可能性効率の良い（圧縮率の高い）符号化ハフマン符号ハフマン符号の拡張，その他の符号化法符号化効率の限界関連する話題本日の講義 5 情報源符号化と用語の定義例：天気予報（通報は「晴」「曇」「雨」）の符号化記録系で利用できる記号（アルファベット）は 0 または 1 通報符号語 00 晴 10 曇 11 雨一個ずつが，それぞれ符号語符号 ≠符合通報とアルファベット系列の一対一関係を考える符号語 (codeword)：通報に対応するアルファベット系列 00 は符号語，10 は符号語，01 は符号語でない符号 (code)：符号語の集合，上例では {00, 10, 11} ２元符号... アルファベットが２種類の記号 6 符号化と復号符号化 (encode)：通報を符号語に変換すること復号 (decode): 符号語を通報に変換すること注意：符号化の際，符号語と符号語の間には，分離記号を挟まない（空白文字など） ○ 晴曇晴 ⇒ 001000 × 晴曇晴 ⇒ 00 10 00 分離記号が欲しい場合... 分離記号も，アルファベットや符号の定義に含めること「空白文字でも，一文字は一文字」 7 符号に求められる性質情報源符号化に求められる第一条件：符号化した結果が，正しく一意に復号できること符号語を，すべて異なるものにすればＯＫ？晴曇雨雪 C1 00 10 01 11 C2 0 01 011 111 C3 0 10 11 01 C4 0 10 11 0 C4 は明らかにダメ他はＯＫ？ C3を使って「晴，雨，晴」を符号化すると 0110 C3を使って「雪，曇」を符号化すると 0110 ⇒ 両者の区別がつかない...一意には復号できない 8 一意復号可能性符号が一意復号可能である (uniquely decodable)：異なる通報系列が，同一の符号語系列に符号化されないこと晴曇雨雪 C1 00 10 01 11 C2 0 01 011 111 C3 0 10 11 01 C4 0 10 11 0 C1, C2 は一意復号可能 C3, C4 は一意復号可能でない（特異符号，singular code） C1, C2 はどちらも一意復号可能だが...C2 はちょっと使いにくい 9 符号 C2 の問題点 C2で「晴，雪，雪，晴」を符号化 ⇒ 符号語系列は 01111110 この系列を一文字ずつ送る場合を考える７文字目まで受け取った時点では ...復号結果として，２通りの候補が存在次が... 0 0111111 7文字目次が... 1 晴曇雨雪 C2 0 01 011 111 0 111 111 0 晴雪雪晴 01 111 111 雨雪雪８文字目以降を受け取るまで，最初の復号結果すら確定できない ⇒ 復号器内に大きなバッファが必要，大きな復号遅延の発生 10 瞬時復号可能性符号が瞬時復号可能である (immediately decodable)：符号語系列の先読みをしなくても，復号を行えること（符号語パターンが出現すれば，すぐに復号してよい） A B C D 01 010 011 100 左例：瞬時復号可能でない 0110 0 ⇒ 01 100 (AD) 1 ⇒ 011 01 (CA) 右例：瞬時復号可能でない 0111101 0 ⇒ 01 11 10 0? (ACB?) 1 ⇒ 011 11 01 (DCA) A B C D 01 10 11 011 11 瞬時復号可能性と語頭条件瞬時復号可能性は，工学上，非常に重要な性質でも，すべての系列についてチェックするのは大変どんなときに，瞬時復号可能でなくなるか？ ⇒ ある符号語が，他の符号語の最初の部分と一致するとき語頭となる A 01 A 01 B C D 010 011 100 B C D 10 11 011 符号Cが瞬時復号可能となる ⇔ Cのどの符号語も，他の符号語の語頭とならないこと（語頭条件，prefix condition) 12 余談：語頭条件といえば... 語頭条件の確保は，システム設計全般にわたって重要 PDAの手書き入力用文字ストローク Graffiti 1 すべて一筆書き prefix condition を満たす Graffiti 2 二筆文字も出現 prefix condition を満たさない 13 語頭条件を満たす符号の作り方語頭条件を満たす符号の単純な作り方：すべての符号語を，同じ長さを持つ相違なる系列とする（等長符号，equal-length code）符号語の最後（最初）に特別なパターンを配置する（コンマ符号，comma code） ⇒ どちらも，取り扱いは楽だが効率が悪い一工夫して，必要最小限の長さを持つ符号語を選んでくる（非等長符号，unequal-length code）符号木を利用した構成法が便利 14 符号木 a元符号の符号木 (code tree)：各節点が，最大 a 個の子を持つことのできる木構造根...親を持たない節点葉...子を持たない節点根葉 15 符号木を利用した符号の構成法 M 個の符号語を持つ符号の構成手順： 1. 葉の数がM個であるような符号木 T を任意に構成する 2. Tの各枝に，0 から a の記号をラベル(名前）付けするただし，一つの親が同一ラベルの枝を複数持ってはならない 3. 根から葉までの経路を考える経路上のラベルを順に連接したものが，一個の符号語となる 16 符号の構成例符号語数が４の２元瞬時復号可能符号を構成する 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 C1={0, 10, 110, 111} 0 0 1 0 1 0 1 1 1 1 0 0 C2={0, 11, 101, 100} 1 0 0 0 1 1 0 C3={01, 000, 1011, 1010} どのようにしても語頭条件を満たす ⇒ 瞬時復号可能な符号 18 符号語の長さと符号の効率 0 1 0 1 C1={0, 10, 110, 111} 0 1 0 1 0 1 C3={01, 000, 1011, 1010} 0 0 1 1 0 C1 vs. C3...どちらも，符号語数４の瞬時復号可能な符号個々の符号語が短いほうが，効率が良い（コンパクトな表現）４つの符号語の長さを，すべて 1 にできるか？４つの符号語，長さを 1, 2, 2, 3 にできるか？瞬時復号可能な符号が構成できる条件は？ 19 クラフトの不等式 C = {w1, ..., wM}, |wi| = li であるa元符号とする [定理] C が語頭条件を満たすなら，以下の不等式が成立 a l1  a l2  a lM  1 ：クラフトの不等式 (Kraft’s inequality) 定理の逆は必ずしも成立しないが... クラフトの不等式を満たす符号語長l1, ..., lMが与えられたとき，語頭条件を満たし，この符号長をもつ符号を構成可能 20 符号語長からの符号構成符号語長が1, 2, 3, 3 である瞬時復号可能な符号を作りたい ⇒ 深さ 1, 2, 3, 3 に葉がくるように符号木 T を構成すれば良い 0 1 0 1 0 C1={0, 10, 110, 111} 1 符号語長が1, 2, 2, 2 である瞬時復号可能な符号を作りたい 2–1 + 2–2 + 2–2 + 2–2 = 0.5 + 0.25 + 0.25 + 0.25 = 1.25 > 1 ⇒ 無理 21 符号の効率についてここまでの議論...取り扱い上の利点を持つ符号の構成方法ここからの議論...取り扱い上の利点＋効率の良さに着目晴曇雨雪確率 0.4 0.3 0.2 0.1 C1 0 10 110 111 C2 111 110 10 0 C1とC2，どちらが良い符号？「晴晴曇雨晴」を符号化してみる C1:00101100 ８記号１４記号 C2:11111111010111 C1のほうが，通報をコンパクトに表現可能コンパクトさの定量的指標... 符号長の加重平均（平均符号長） 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 22 情報源符号化の指標良い符号の三条件：一意復号可能であること瞬時復号可能であること平均符号長ができるだけ短いこと最初２つの条件だけなら，符号木を使うだけで構成可能最後の条件を満たすため，符号木の作り方に一工夫する ⇒ ハフマン符号 (Huffman code) とくに断らない限り，記憶のない定常情報源を考える 23 ハフマン符号一般的な性質ではなく，符号木の構成法によって定式化： 1. 各通報に対して節点を準備し，その発生確率を付与する節点はそれぞれ，大きさ１の木であると考える 2. 木の中で発生確率最小のものを２つ選出し，以下を行う 1. ２つの木の根節点を子とするような，新しい根節点を作る 2. 新しい根節点と古い根節点を結ぶ枝に，0, 1 をラベル付け 3. 新しい根節点に，２つの木の発生確率の和を与える 3. すべての節点がつながるまで，2 の操作を繰り返す 24 ハフマン符号の構成例 0.15 0.6 A 0.25 B 0 0.6 A 0.25 B 0.1 C 0.05 D 0.6 A 0.25 B 1.0 1 0.4 1 0.15 0 0 1 0.1 C 0.05 D 0.1 C 0.05 D 0.4 0.15 0.6 A 0.25 B 0.1 C 資本金による合併劇，と考えるとわかりやすいかも... 0.05 D 25 練習問題 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 符号語等長符号の場合と平均符号長を比較すると... 26 ハフマン符号構成上の自由度ハフマン符号の構成においては，ラベル割当の自由度確率の等しい節点選択の自由度が存在するが... ⇒ どのように選択しても，平均符号長は変わらない A B C D E F 確率 0.3 0.2 0.2 0.1 0.1 0.1 符号語 27 本日のまとめ情報源符号化に関する基本概念の整理一意復号可能性瞬時復号可能性クラフトの不等式符号木利用による符号構成ハフマン符号加重平均符号長による評価具体的な符号構成法 28 練習問題右の情報源を効率よく符号化できる，２元ハフマン符号を構成せよ上で構成した符号の平均符号長を求めよ４元ハフマン符号の構成法を検討し，右の情報源に適した符号を構成せよ A B C D E F G H 確率 0.363 0.174 0.143 0.098 0.087 0.069 0.045 0.021 29