ハフマン符号

ハフマン符号は、各記号の生起確率又は頻度に基づき、頻出記号へ短い符号、まれな記号へ長い符号を割り当てる可変長の可逆圧縮符号です。

■ 試験で押さえるポイント

• 頻度が最小の二つを一つの節へまとめ、その合計頻度を候補へ戻す操作を一つの木になるまで繰り返し、枝へ0と1を割り当てます。

• どの符号語も別の符号語の先頭にならない接頭語条件を満たすため、区切り記号を付けず木をたどって一意に復号できます。

• 既知の記号確率に対する二進接頭語符号の平均符号長を最小にしますが、記号単位の符号なので、確率によっては算術符号等より圧縮率が劣ります。

• 符号表又は木が復号側にも必要で、頻度表の格納量、小さなデータ、頻度変化も含めて実際の圧縮効果を評価します。

■ 選択肢での判断ポイント

最小頻度の二項を順に結合し、各記号の$\text{符号長}\times\text{確率}$を合計して平均符号長を求めます。接頭語条件も確認します。

例: 確率$A=1/2$、$B=1/4$、$C=D=1/8$なら符号長を1、2、3、3ビットにできます。平均は$1/2\times1+1/4\times2+1/8\times3+1/8\times3=1.75\,\text{ビット}$です。