ハフマン符号
更新日:
用語解説
ハフマン符号は、よく出る記号には短い符号を、まれな記号には長い符号を割り当てて、データ量を減らす可逆圧縮の符号です。
■ 試験で押さえるポイント
出現頻度の最も小さい二つをまとめる操作を繰り返して、木を作ります。
どの符号も他の符号の先頭部分にならないため、区切りなしで一意に復号できます。
平均符号長は、各記号の符号長×出現確率の合計です。
■ 選択肢での判断ポイント
頻度の小さい二つから順にまとめ、平均符号長を計算する問題が頻出です。
例: 確率1／2、1／4、1／8、1／8の記号に1、2、3、3ビットを割り当てると、平均は1.75ビットです。