ハフマン符号

ハフマン符号とは、データの圧縮手法の一つであり、出現頻度が高い文字には短い符号を、出現頻度が低い文字には長い符号を割り当てることで、データ全体のサイズを小さくするアルゴリズムです。情報の効率的な伝送や保存のために用いられます。

仕組みとしては、まず文字の出現頻度を数え上げ、頻度が低いものから順に二分木を構築していきます。この木を辿ることで各文字に固有のビット列（ハフマン符号）を生成します。頻出文字が短い符号になるため、平均的な符号長が短縮され、高い圧縮率が実現されます。

固定長符号との違いを押さえることが試験では重要です。固定長符号はすべての文字を同じビット長で表現するため単純ですが、ハフマン符号のような可変長符号と比べると圧縮効率は低くなります。復号の際に曖昧さが発生しないよう、どの符号も他の符号の先頭部分と一致しない性質を持たせることが特徴です。