
情報量・エントロピー・ハフマン符号――情報を短く表す
保存容量としてのビット数と、出来事から得られる情報量は関連しますが、同じ言葉として無条件に扱えません。起こりやすさから考えます。
情報量と平均情報量
正確な意味: 確率pの出来事の自己情報量は−log2 pビットです。平均情報量(エントロピー)は、それぞれの情報量を確率で重み付けした合計H=−Σp log2 pです。
ざっくり言うと: 起こりにくい出来事ほど、知ったときの意外さが大きいと考えます。エントロピーはその平均です。
用途・問題での見方: 圧縮できる余地などを考えます。確率1/8の出来事なら情報量3ビットです。等確率の4種類なら1種類を知る情報量も平均情報量も2ビットです。確実に起こる出来事p=1の情報量は0です。ここでの情報量は文章の価値や重要さを評価するものではありません。
情報源符号化と通信路符号化
正確な意味: 情報源符号化はデータの表現を効率化する符号化です。可逆圧縮では元へ完全に戻せるよう冗長さを減らします。通信路符号化は、伝送中の誤りの検出・訂正などのため規則的な冗長性を加える符号化です。
ざっくり言うと: 短くする工夫と、壊れても気付ける・直せる工夫です。
用途・問題での見方: 保存や通信の容量削減と、通信の信頼性向上を分けます。同じ「符号化」でも目的が異なります。暗号化は機密性などを守る別の処理で、圧縮したから秘密になるわけではありません。
ハフマン符号と接頭語
正確な意味: ハフマン符号は、出現確率の小さいもの同士を順にまとめる木を作り、頻出する記号に短い符号を割り当てる可変長符号です。ある符号語が別の符号語の先頭にならない接頭語条件を満たします。
ざっくり言うと: よく出る記号は短く、区切りが分かるように割り当てます。
用途・問題での見方: A・B・Cの確率が1/2、1/4、1/4なら、A=0、B=10、C=11とすれば平均長は1/2×1+1/4×2+1/4×2=1.5ビット/記号です。3種類を固定長で表す2ビットより短くなります。木の左右を交換しても平均長が同じ符号があり、唯一のビット列になるとは限りません。復号には対応表なども必要で、短いデータでは付加情報を含む総容量も考えます。
確認問題【オリジナル】
確率1/16の出来事が起きたと知ったときの自己情報量はどれでしょうか。
ア:1ビット
イ:2ビット
ウ:4ビット
エ:16ビット
正解と理由
ウ:4ビットです。 −log2(1/16)=4です。ア・イはそれぞれ確率1/2、1/4の場合です。エは確率の分母をそのままビット数としています。1/16=2の−4乗という対応を使えば計算できます。
参考資料と問題について
学習範囲の確認:IPA「基本情報技術者試験 シラバス Ver.9.2」。本記事は独自の説明・例題です。
考え方の参照:MIT OpenCourseWare:Information and Entropy。
確認問題と解説はオリジナルです。公開過去問の転載・改変問題ではありません。出題頻度は未集計です。
前後の記事と学習目次
前の記事:待ち行列とM/M/1――利用率が高いと待ち時間はどうなる?