ハフマン符号の平均符号長
4 種類の記号 A，B，C，D の出現確率が，それぞれ 0.5，0.25，0.125，0.125 である。これらの記号をハフマン符号化したときの，1 記号当たりの平均符号長は何ビットか。
- ア1.5
- イ1.75
- ウ2.0
- エ2.25
正解と解説を見る
正解 イ
この問題の基礎知識
- ハフマン符号は，出現確率の低い記号から順に二つずつ併合して木を作り，出現確率の高い記号ほど短い符号を割り当てる可変長符号である。
- 1 記号当たりの平均符号長は，各記号の「出現確率×符号長」の総和で求める。
- 情報源のエントロピー（各記号の確率 p について p×log2(1/p) を合計した値）は，一意に復号可能な符号の平均符号長の下限である。出現確率がすべて 2 の負のべき乗のとき，ハフマン符号の平均符号長はエントロピーに一致する。
- n 種類の記号を固定長符号で表すには，2 の k 乗が n 以上となる最小の k ビットが必要である。
ア1.5
この情報源のエントロピーは 0.5×1＋0.25×2＋0.125×3×2＝1.75 ビットであり，平均符号長がこれを下回る一意に復号可能な符号は存在しない。
イ1.75正解
確率の小さい C と D を併合して 0.25，それと B を併合して 0.5，最後に A と併合すると，符号長は A が 1，B が 2，C と D が 3 となる。平均は 0.5×1＋0.25×2＋0.125×3＋0.125×3＝1.75 ビットである。
ウ2.0
4 種類の記号をすべて 2 ビットの固定長符号で表した場合の値である。ハフマン符号では出現確率の高い A に短い符号を割り当てるので，これより短くなる。
エ2.25
出現確率の低い記号に短い符号を割り当てるなど，最適でない割当てをした場合の値である。ハフマン符号の平均符号長 1.75 ビットより長い。
検証用の出典出典照合済み
D. A. Huffman, A Method for the Construction of Minimum-Redundancy Codes (1952)照合の根拠（1 件）
- イ（正解）: ハフマン符号がデータ圧縮（情報源符号化）の技法として扱われることの確認。値は note の計算による
用語例 符号理論，ランレングス，ハフマン符号
IPA 応用情報技術者試験シラバス Ver.7.2 · 1.4 データ圧縮（新しいタブで開きます）
計算の検算: C(0.125)+D(0.125)→0.25，+B(0.25)→0.5，+A(0.5)→1.0 で符号長 A1・B2・C3・D3。平均＝0.5×1＋0.25×2＋0.125×3×2＝1.75。確率がすべて 2 の負べきなのでエントロピー（1.75）と一致し，ア（1.5）は下限未満で不可能，ウ 2.0 は固定長，エ 2.25 は最適でない。一般的な情報理論の計算のため出典の定義は不要と判断