ENGINEER_GUIDANCE: ハフマン符号化
ハフマン符号化（Huffman Coding）は、データの可逆圧縮において最も有名かつ強力なアルゴリズムの一つです。ZIPファイルやJPEG画像など、私たちが普段利用している多くの圧縮技術の土台となっています。
1. 固定長から可変長へのパラダイムシフト
通常のコンピュータは、すべての文字を「8ビット（1バイト）」など同じ長さ（固定長）のデータとして扱います。しかし、文章中には「A」のように頻繁に出る文字もあれば、「Z」のように滅多に出ない文字もあります。
そこで、「よく出る文字には短い記号を、滅多に出ない文字には長い記号を割り当てる」ことで、全体のデータ容量を劇的に減らすアプローチが考案されました。これが「可変長符号化」です。
2. アルゴリズムの動作原理
ハフマン符号化では、データ全体から「文字の出現回数」をカウントし、以下の手順で木構造（ハフマン木）を構築します。
- 出現回数が最も少ない2つのノードをペアにして結合する。
- 結合されたノードの出現回数は、2つのノードの合計値とする。
- ノードが残り1つ（根）になるまで 1. と 2. を繰り返す。
このルールにより、頻繁に出る文字は木の根元（上）の方に配置され、結果的に「0」や「1」といった非常に短いビット列が割り当てられます。
3. 接頭語条件 (Prefix Property)
可変長符号の最大の課題は、「どこで文字が区切れるかわからなくなる」ことです。しかしハフマン木から生成された符号は、「ある文字の符号が、別の文字の符号の一部（接頭語）にならない」という強力な特性を持っています。これにより、受信側は区切り文字なしで正確にデータを復元（デコード）することができます。