ハフマン符号

定義

出現頻度の高い文字に短い符号、低い文字に長い符号を割り当てる可変長符号化方式。

詳細解説

1952年デビッド・ハフマン考案。文字の出現頻度に基づき二分木を構成して符号を割り当てる。頻度の小さい二つを枝として結合する手順を繰り返し、根に至るまでの経路（0/1）が符号となる。語頭符号（接頭符号）の性質を持ち、復号が一意に決まる。平均符号長が情報理論のエントロピーに近い最適性を持つ。ZIPやJPEG、MP3等の圧縮形式で利用される。出現確率が偏るほど高い圧縮率を得られる。

「ハフマン符号」が出る問題

• 完全二分木において、節点数がnのときの木の高さのオーダとして、正しいものはどれか。

• ハフマン符号化に関する記述として、適切なものはどれか。

• テクノロジ

  ハフマン符号化の特徴として正しいものはどれか。

関連用語

よくある質問