データ圧縮（ハフマン符号化）とは？でーたあっしゅく
データ圧縮（ハフマン符号化）とは、出現頻度の高い記号に短いビット列、低い記号に長いビット列を割り当てて全体量を減らす可逆圧縮の符号化方式。頻度表から二分木を組み、根から葉までの経路がそのまま符号になる。平均符号長は各記号の確率と符号長の積の総和で求まり、情報源のエントロピーが理論的な下限を与える。
最終更新：2026-10-06
エンベデッドSPを最短で暗記・合格する →背景
固定長符号は、どの記号も同じコストで扱うという前提を置いている。実際のデータは偏っているので、その前提の分だけ無駄が残る。頻度の偏りをそのままビット数へ反映すれば無駄は消える、というのが出発点である。組込みでは効き方が二重で、ROMに載せるフォントやメッセージの容量と、無線区間の送信ビット数すなわち消費電力の双方に直結する。
具体例
zlibのDEFLATEはLZ77で繰り返しを置き換えたうえにハフマン符号を掛ける構成で、組込み向けの軽量実装も広く出回っている。センサ値をそのまま毎秒送る代わりに符号化して送信ビット数を半分にできれば、無線の送信時間が減り、電池寿命がそのぶん伸びる。
試験での引っ掛け
可逆であることを外さない。元のデータを完全に復元でき、JPEGやMP3のような非可逆圧縮とは別物である。また万能ではなく、全記号の出現確率が等しければ縮まず、乱数列では表の分だけ増えうる。可変長なのに区切り記号なしで復号できるのは、どの符号も他の符号の先頭部分にならない語頭条件を満たすからで、単に短い符号を割り当てるだけでは復号できない。
関連用語
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。