ハフマン符号とは？

ハフマン符号の意味

出現頻度の高い記号ほど短いビット列を割り当てる可変長符号化方式。頻度の低い2つを繰り返しまとめて木を作ることで、平均符号長が最小になる符号を構成できる。

ハフマン符号の具体例

A:0.5、B:0.25、C:0.125、D:0.125のとき、A=0、B=10、C=110、D=111とすると平均符号長＝0.5×1＋0.25×2＋0.125×3×2＝1.75ビット。固定長2ビットより短い。

ハフマン符号は試験でどう引っ掛けられる？

圧縮効果は「平均符号長＝Σ（出現確率×符号長）」で評価する。最短の符号長だけを見て判断しない。

ハフマン符号と関連する用語

• 語頭条件
• 情報量とエントロピー

ハフマン符号が出た過去問

• a, b, c, dの4文字から成るメッセージを符号化してビット列にする方法として表のア〜エの4通りを考えた。この表はa, b, c, dの各1文字を符号化する…

  正解：a=0, b=10, c=110, d=111

  要点：語頭条件を満たし、高頻度文字ほど短い符号にすると平均長が縮む

  一意に復号するには、ある符号語が他の符号語の先頭部分になっていない（語頭条件を満たす）必要がある。ア（0が00の先頭）とイ（0が01の先頭）は語頭条件を満たさず復号が一意に定まらない。残るウとエで平均符号長を計算すると、ウは0.5×1+0.3×2+0.1×3+0.1×3＝1.7ビット、エは一律2ビットなので、ウが最短となる。出現頻度の高い文字へ短い符号を割り当てるハフマン符号の考え方である。

  出典：令和2年度 10月 高度共通_午前I試験 am1 問2（IPA）