情报科学概论.ppt

第二部：情報の表現方法を考える 情報は，実体を持たない抽象的なもの 情報の容器である「通報」に，具体的表現を与える必要がある 通報の表現方法...かなり大きな自由度がある ? 「良い」表現方法と「良くない」表現方法がある 「良い」表現方法とは？ 情報の蓄積を考えると...できるだけコンパクトであること 情報の伝達を考えると...できるだけ誤りに強いこと 相反する二つの方向性の間で，バランスを取ることが大切 技術としては，それぞれ独立したものとして扱うことが得策 第二部前半：情報のコンパクトな表現について ３種類の通報 A, B, C を，0 と 1 だけを用いて符号化する A B C 0 1 1 符号化すると，B と C が区別できなくなる （一意に復号できない） ? すべてを 1 ビットで表現することは不可能 A B C 00 10 11 一意性は保証されるが，一工夫足りない... A B C 0 10 11 符号語の長さが揃っていないが... 情報をコンパクトには表現できる 符号語 通報 （ただし，区切り記号は使わない） 様々な符号化法 A B C 0 10 11 いまのところベストの符号化法 A B C 00 11 1 上の例と似ているが，一意性が保証されない B → 11 CC → 11 A B C 00 10 1 一意性は保証されるが，取り扱いが面倒 → BAAA 1000000 → CAAA 最後の一文字を見るまで，復号を行えない 最初の方式は，一意的で，即時に復号処理ができる 様々な符号化法（続） A B C 0 10 11 いまのところベストの符号化法 A B C 11 10 0 本質的に，上と同じ？ C1 C2 通報の出現確率に偏りがある場合を考える P(A) = 0.5 P(B) = 0.4 P(C) = 0.1 C1 ：一通報を表現する符号長の平均は 0.5 ×1 + 0.4×2 + 0.1×2 = 1.5ビット C2 ：一通報を表現する符号長の平均は 0.5 ×2 + 0.4×2 + 0.1×1 = 1.9ビット C1 のほうが C2 よりもコンパクトな表現 符号に求められる性質 良い符号の三条件： 一意に復号可能であること 瞬時に復号可能であること 平均符号長ができるだけ短いこと 理論的に最適な解法が知られている ? ハフマン符号化 ハフマン符号 各通報に対して節点を準備し，その発生確率を付与する 節点はそれぞれ，大きさ１の木であると考える 木の中で発生確率最小のものを２つ選出し，以下を行う ２つの木の根節点を子とするような，新しい根節点を作る 新しい根節点と古い根節点を結ぶ枝に，0, 1 をラベル付け 新しい根節点に，２つの木の発生確率の和を与える すべての節点がつながるまで，2 の操作を繰り返す ハフマン符号化法 A 0.60 B 0.25 C 0.10 D 0.05 記号 確率 0.60 A 0.10 C 0.05 D 0.25 B 0.15 0.60 A 0.10 C 0.05 D 0.25 B 0.60 A 0.10 C 0.05 D 0.25 B 0.40 0.60 A 0.10 C 0.05 D 0.25 B 1.00 練習問題 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 符号語 等長符号の場合と比べ，平均符号長が小さくなっている ハフマン符号とブロック化 ハフマン符号： 得られる符号は，一意かつ瞬時に復号可能 通報一個を符号語一個に符号化する方式としては， 最も効率が良い（最もコンパクト，平均符号長が小さい） 複数の通報を一まとめにして（ブロック化して）符号化すれば， さらに効率が良くなることが知られている ブロックハフマン符号 ２つの通報をまとめて（ブロック化して）符号化する A B C 0.6 0.3 0.1 0 10 11 記号 確率 符号語 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 記号 確率 符号語 平均符号長 1.4 ビット 平均符号長 2.67 ビット ? 一記号あたり 1.335 ビット ブロック化と性能の限界 一般に，ブロック長を大きくすると，通報一記号あたりの 平均符号長は減少する どこまで減少するか？ 対象となっている情報源のエントロピーに漸近する ブロック長 エントロピー 平均符号長 （一記号あたり）