ハフマン符号と符号木とは？

ハフマン符号と符号木とは、出現頻度の高い記号ほど短いビット列を割り当てて、全体の符号長を短くする可変長符号化。頻度の低い2つを繰り返し併合して木を作り、根から葉までたどった経路がその記号の符号になる。

基本情報技術者試験の過去問では1回出題されています。

はふまんふごうとふごうぎ

基本情報技術者試験の頻出用語／テクノロジ系／別名：ハフマン符号

ハフマン符号と符号木の意味

出現頻度の高い記号ほど短いビット列を割り当てて、全体の符号長を短くする可変長符号化。頻度の低い2つを繰り返し併合して木を作り、根から葉までたどった経路がその記号の符号になる。

文章中でaが非常に多くzがまれなとき、aに1〜2ビット、zに6ビットのように割り当てる。全記号を8ビット固定にするより総ビット数が減るため、可逆圧縮の基礎技術として広く使われる。

長さがばらばらでも区切り記号が要らないのは、どの符号も他の符号の先頭部分にならない（語頭符号）ためで、記号を木の葉にだけ置くことでこれが保証される。復号できないという説明は誤り。

出現頻度の異なるA，B，C，D，Eの5文字で構成される通信データを，ハフマン符号化を使って圧縮するために，符号表を作成した。aに入る符号として，適切なものはどれ…
正解：110
要点：ハフマン符号は他の符号の接頭辞になってはならない
ハフマン符号は語頭条件を満たす必要があり、どの符号も他の符号の先頭部分になってはならない。既に00・01・10が使われているので2ビットは11しか残らず、Eが111を使うことからDは110となる。頻度がEより高いDに同じ3ビットを割り当てても矛盾はしない。
出典：平成30年度秋期基本情報技術者試験午前問4（IPA）

最終更新：2026-08-25／解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。