データ圧縮（ハフマン符号化）とは？

データ圧縮（ハフマン符号化）の意味

データの可逆圧縮技術の代表例。出現頻度の高い文字ほど短いビット列を、出現頻度の低い文字ほど長いビット列を割り当てることで、全体のデータ量を削減する符号化方式（ハフマン符号化）。

データ圧縮（ハフマン符号化）の具体例

「a」が非常に多く「z」がほとんど出現しない文章では、「a」に2ビット、「z」に8ビットのように可変長の符号を割り当てることで、全員に固定8ビットを割り当てる場合よりデータ量を圧縮できる。

データ圧縮（ハフマン符号化）は試験でどう引っ掛けられる？

ハフマン符号化は元のデータを完全に復元できる可逆圧縮で、JPEGやMP3のような非可逆圧縮と混同しないこと。またどんなデータでも縮むわけではなく、すべての文字の出現頻度が等しい場合は圧縮効果がない（乱数列などではむしろ増えうる）。可変長符号でありながら区切り記号なしに復号できるのは、どの符号も他の符号の先頭部分にならない（語頭条件を満たす）ように割り当てているからで、単に「短い符号を割り当てる」だけでは復号できない。

データ圧縮（ハフマン符号化）が出た過去問

• 出現頻度の異なるA，B，C，D，Eの5文字で構成される通信データを，ハフマン符号化を使って圧縮するために，符号表を作成した。aに入る符号として，適切なものはどれ…

  正解：110

  要点：ハフマン符号は他の符号の接頭辞になってはならない

  ハフマン符号は語頭条件を満たす必要があり、どの符号も他の符号の先頭部分になってはならない。既に00・01・10が使われているので2ビットは11しか残らず、Eが111を使うことからDは110となる。頻度がEより高いDに同じ3ビットを割り当てても矛盾はしない。

  出典：平成30年度 秋期 基本情報技術者試験 午前 問4（IPA）