ハフマン法

ハフマン法とは、データの出現頻度に基づき、頻出するデータには短い符号を、出現頻度が低いデータには長い符号を割り当てることで、データ量全体を圧縮する可逆圧縮アルゴリズムです。統計的なデータの特徴を利用して符号の長さを可変にすることで、効率的に圧縮を実現します。

このアルゴリズムでは、二分木（ハフマン木）と呼ばれる構造を作成し、頻度に基づいて符号を生成します。頻度が高いものほど木の根に近い短いパスが割り当てられ、頻度が低いものほど深い場所に置かれます。これにより、データ全体のビット長を最小化できます。復号時には、この木構造を参照することで、誤りなく元のデータを復元できます。

混同しやすいものに、固定長符号がありますが、こちらは出現頻度に関わらず一律の長さでデータを扱うため、ハフマン法のような圧縮効率は期待できません。ハフマン法は可逆圧縮（元のデータと完全に一致する）であるため、テキストファイルやソースコードの圧縮など、情報の欠損が許されない場面で広く利用されています。