ハフマン符号（Huffman Coding）
出現頻度の高い文字に短い符号を割り当てる可変長の圧縮符号化方式
📌ハフマン符号とは
ハフマン符号とは、文字の出現頻度に応じてよく出る文字には短い符号、めったに出ない文字には長い符号を割り当てる、可変長（＝文字ごとに長さが違う）の圧縮符号化方式です。
身近な例で言うと、モールス信号に似ています。モールス信号では、英語でよく使う「E」を最短のトン（・）一つで表し、あまり使わない「Q」は長い符号で表します。よく使うものを短くすれば、全体の長さが短くなる——これがハフマン符号の発想です。
上のツールで▶ボタンを押すと、文字の頻度からハフマン木を 1 ステップずつ組み立てる様子が見られます。完成した木と、各文字に割り当てられた符号、そして平均符号長が固定長より短くなることを確認してください。
🌳ハフマン木の構築手順
ハフマン木は「もっとも頻度の小さい 2 つの節点を取り出して結合する」という操作を繰り返して作ります。結合してできた新しい節点の頻度は、元の 2 つの頻度の合計になります。
手順を整理すると以下の通りです。
・① 並べる：各文字を「頻度を持つ節点」として用意する
・② 結合：頻度が最小の 2 節点を選び、合計を頻度に持つ親節点で結ぶ
・③ 繰り返す：節点が 1 つ（＝根）になるまで②を繰り返す
・④ 符号化：根から各文字へたどり、左へ進むと 0、右へ進むと 1 を並べた列がその文字の符号
頻度の小さい文字ほど結合が早く（＝木の下のほうで）行われるため、根からの距離が遠くなり、符号が長くなります。逆に頻度の大きい文字は根の近くに残るので符号が短くなる、という仕組みです。上のツールの「残っている節点」を見ながらステップを進めると、毎回最小の 2 つが選ばれていることが分かります。
📌なぜ頻度が高いほど符号が短くなるのか
結論から言うと、「根（木のてっぺん）から葉（文字）までの距離 = 符号の長さ」だからです。木の構築では頻度の低い節点から先に結合されます。頻度が低いほど早く深いところへ沈み、根から遠くなるため、符号が長くなります。
身近な例で言うと、棚の整理に似ています。毎日使う道具は手前（根の近く）に置き、めったに使わない道具は奥（根から遠く）に片づける。よく使うものほどすぐ手が届く＝ビット数が少ない、という発想です。
上のツールで▶を押してステップを追うと、頻度が高い文字は後まで結合されず木の浅いところに残ることが確認できます。「残っている節点」が減る順番に注目してみてください。
📌平均符号長の計算 — なぜ圧縮できるのか数字で確認
平均符号長＝Σ（確率 × 符号長）で求めます。各文字の「確率（＝全体に占める割合）」に「符号の長さ（ビット数）」を掛けて合計するだけです。
上の例（A頻度12・B頻度5・C頻度3、合計20）で計算すると、
0.6 × 1 + 0.25 × 2 + 0.15 × 3 = 0.6 + 0.5 + 0.45 = 1.55 bit
3種類の文字を固定長で表すには 2 bit（2ビットで4通り表せる）必要です。ハフマン符号の平均 1.55 bit はそれより 0.45 bit 短く、全体のデータ量を約22%削減できることを意味します。頻度の偏りが大きいほどこの差は広がります。
⚖️可変長符号の利点
すべての文字を同じ長さで表す固定長符号に対し、ハフマン符号は文字ごとに長さを変える可変長符号です。最大の利点は、出現頻度に偏りがあるデータを固定長より短く（圧縮して）表せることです。
可変長で気になるのは「符号の区切りが分からなくなるのでは？」という点ですが、ハフマン符号は接頭辞符号（語頭符号）になっています。これはどの符号も、他の符号の先頭部分（接頭辞）にはなっていないという性質です。たとえば A=0 なら、他の符号は決して 0 から始まりません。そのため区切り記号がなくても、先頭から読んでいけば符号の切れ目が一意に決まり、正しく復号できます。
押さえておきたいポイント:
・頻度の偏りが大きいほど圧縮効果が高い（均等だと固定長とほぼ変わらない）
・接頭辞符号なので区切り記号なしで一意に復号できる
・平均符号長は平均情報量（エントロピー）に近づくが、それより短くはできない
