ハフマン符号化とは（全体像）
ハフマン符号化は、文字の出る回数（頻度）に合わせて符号の長さを変える圧縮のやり方。よく使う文字を短く、あまり使わない文字を長くすることで、全体のデータ量を減らす。
身近な発想は「よく使うものほど手短に」。あいさつを「お疲れさまです」より「おつ」と短く言うようなもので、頻出する文字を短い符号にすれば、全体が短くなる。
このように長さがバラバラの符号を可変長符号という。すべて同じ長さにする固定長とは反対で、頻度に応じて長さを変えるのがハフマンの肝だ。
詳しく：この手順と性質だけ覚えれば戦える
ここが記事の心臓部。まずは木を作る4ステップ。
ハフマン木を作る4ステップ
| 手順 | やること |
|---|---|
| ①頻度計算 | 各文字が何回出るかを数える |
| ②木の構築 | いちばん頻度の少ない2つをくっつける、を繰り返す |
| ③枝に0と1 | 木の左の枝に0、右の枝に1を割り当てる |
| ④符号の確定 | 根（ルート）から各文字までたどった0と1の並びが符号 |
たとえば A が5回・B が3回・C が2回・D が1回・E が1回出るなら、よく出る A は「0」のように短く、めったに出ない D・E は「1110」「1111」のように長くなる。
ここで超重要なのが接頭符号（せっとうふごう）という性質。
どの符号も、ほかの符号の「先頭部分」になっていない。
たとえば A が「0」なら、ほかの符号は絶対に「0」から始まらない。だから区切り記号がなくても、前から読んでいけば迷わず元に戻せる（一意に復号できる）。これがハフマン符号の最大の強みだ。
ハフマン符号の性質と位置づけ
| 項目 | 内容 |
|---|---|
| 符号の長さ | 可変長（頻度が高いほど短い） |
| 接頭符号 | どの符号も他の符号の先頭にならない＝一意に復号できる |
| 効率 | エントロピー（理論限界）に近づく |
| さらに上 | 算術符号はハフマンより効率的なことがある |
つまり、ハフマンは「可変長の中ではかなり優秀だが、最強ではない（算術符号が上回ることがある）」と押さえておくとひっかからない。
わかりやすく言い換えると
要するに、ハフマン符号化は「よく使う文字を短い背番号にする」ことだ。
①まず文字の出る回数を数える
②少ない2つをくっつけて木を育てる
③枝に0と1をふって、根からの道のりを符号にする
接頭符号のイメージは「だれの背番号も、ほかの人の背番号の出だしにならない」こと。だから番号を続けて読んでも、どこで一人ぶんが終わるか迷わない。区切りの「・」を入れなくても元に戻せる、というわけだ。
試験のツボ
🔴 一番出る：ハフマン木の作り方
①各文字の頻度を数える
②頻度の少ない2つをくっつけるのを繰り返す
③枝に0と1をふり、根からの道のりが符号
🔴 次に出る：接頭符号だから一意に復号できる
①どの符号も他の符号の先頭にならない
②区切り記号なしで元に戻せる
🟡 押さえると安定：可変長・エントロピーに漸近
①頻度が高い文字ほど短い符号（固定長ではない）
②算術符号はさらに効率的なことがある
よくある間違い
①「ハフマン符号は固定長である」→ ✗ 頻度に応じて長さが変わる可変長。固定長ではない。
②「ハフマンが常に最も効率がよい」→ ✗ 可変長では優秀だが、算術符号がより効率的なことがある。
③「符号を区切る記号が別に必要」→ ✗ 接頭符号なので区切りなしで一意に復号できる。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（木の作り方）
ハフマン符号化の手順に関する次の記述のうち、正しいものはどれか。
- 各文字の頻度を数え、頻度の最も小さい2つを結合する操作を順に繰り返して木を作る
- 各文字をアルファベット順に並べ、上から順に0、1、2…と番号を振って符号とする
- すべての文字に同じ長さの符号を割り当て、文字の出現頻度は一切考慮しない方式だ
- 最も頻度の高い文字に最も長い符号を割り当て、稀な文字には短い符号を割り当てる
解答は 1 だぜ。
ハフマン木は「頻度の少ない2つをくっつける」を繰り返して作る。そのあと枝に0と1をふって、根からの道のりが各文字の符号になるんだ。
選択肢2はアルファベット順で番号を振る別物。選択肢3は固定長で頻度を無視する誤り。選択肢4は「高頻度に長い符号」が逆で、高頻度ほど短い符号だぜ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | 最小頻度2つを結合する繰り返しで正しい |
| 2 | ✗ | アルファベット順の番号付けではない |
| 3 | ✗ | ハフマンは頻度を考慮する可変長 |
| 4 | ✗ | 高頻度ほど短い符号（逆） |
オリジナル問題2（接頭符号）
ハフマン符号が持つ接頭符号の性質に関する次の記述のうち、正しいものはどれか。
- すべての符号が同じ先頭ビットから始まるため、復号の処理がとても速くなる
- どの符号も他の符号の先頭部分にならないので、区切りなしで一意に復号できる
- 符号と符号の間に必ず区切り記号を入れるため、長さがばらばらでも復号できる
- 復号するときは符号を後ろから読む必要があり、前から読むと意味が定まらない
解答は 2 だぜ。
接頭符号とは「どの符号も、ほかの符号の先頭にならない」性質のこと。だから前から順に読んでいくだけで、区切り記号なしでも一意に元へ戻せる。これがハフマンの強みだな。
選択肢1は「同じ先頭から始まる」が逆で、それでは区別できない。選択肢3は「区切り記号が必要」で誤り。選択肢4の「後ろから読む」も誤りで、前から読んで復号できるぜ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 同じ先頭では区別できない |
| 2 | ✓ | 区切りなしで一意に復号できる |
| 3 | ✗ | 区切り記号は不要 |
| 4 | ✗ | 前から読んで復号できる |
オリジナル問題3（効率と用途）
ハフマン符号化の効率や用途に関する次の記述のうち、正しいものはどれか。
- ハフマン符号は可変長だが、データを大きくしてしまうので実際には使われない
- ハフマン符号はあらゆる方式の中で必ず最も高い圧縮効率になることが保証される
- ハフマン符号は圧縮には使えず、誤りを訂正するための符号として使われている
- ハフマン符号は効率がエントロピーに近づき、ZIPやJPEGで使われている
解答は 4 だぜ。
ハフマン符号は圧縮効率がエントロピー（理論限界）に近づく優秀な方式で、ZIP・JPEG・MP3などで実際に使われている。
選択肢1は「実際には使われない」が誤りで、現役の技術だ。選択肢2は「必ず最も高い」が誤りで、算術符号がより効率的なことがある。選択肢3は「圧縮には使えない・誤り訂正用」が誤りで、ハフマンは圧縮の手法だぜ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 圧縮に広く使われている |
| 2 | ✗ | 算術符号が上回ることがある |
| 3 | ✗ | ハフマンは圧縮の手法 |
| 4 | ✓ | エントロピーに漸近・ZIPやJPEGで使用 |
まとめ
押さえどころ
- 🔴 木の作り方 ＝ 頻度を数える→少ない2つを結合→枝に0と1→根からの道のりが符号。高頻度ほど短い。
- 🔴 接頭符号 ＝ どの符号も他の符号の先頭にならない。区切りなしで一意に復号できる。
- 🟡 効率と用途 ＝ 可変長でエントロピーに漸近（算術符号が上回ることも）。ZIP・JPEG・MP3で使用。
次に学ぶ
- 情報量・エントロピー ── ハフマンが近づく「圧縮の理論限界」を決める考え方。セットで理解すると「なぜ短くできるのか」が腑に落ちる。
- 可逆圧縮・非可逆圧縮 ── 元に戻せる圧縮（ハフマンはこちら）と、戻せない圧縮の違い。圧縮の全体像がつかめる。
執筆: SikakuQuest編集部