対象試験と出題頻度
ハフマン符号（ハフマン符号化）は、基本情報技術者・応用情報技術者で出題されるテーマです。
出現頻度に応じた可変長符号の仕組みを理解しているか、また符号表から平均符号長を計算できるかが問われます。
FE H30秋期 午前問4、FE R3年度 免除問6、AP R2秋期 午前問4など、複数の試験区分で繰り返し出題されています。
詳細をクリックして確認
基本情報技術者
応用情報技術者
★★★☆☆
ランクB（標準）覚えておくと有利
用語の定義
情報処理試験を勉強していると、「ハフマン符号って結局何をやっているの？」と手が止まりがちです。
ハフマン符号（Huffman Coding）とは、一言で言うと
「出現頻度が高いデータには短い符号を、低いデータには長い符号を割り当てて、全体のデータ量を減らす可逆圧縮アルゴリズム」
のことです。
イメージとしては、「よく使う言葉ほど短い略語にする」こと。
たとえば、日常会話で「了解」は「り」、「お疲れさまです」は「おつ」と略しますが、めったに言わない長い挨拶は略しません。使用頻度が高いものほど短くする。これがハフマン符号の発想です。
📊 ハフマン符号の基本情報
| 項目 | 内容 |
|---|---|
| 英語名 | Huffman Coding / Huffman Code |
| 分類 | 可逆圧縮（ロスレス圧縮）・可変長符号化 |
| 考案者 | デビッド・ハフマン（David A. Huffman, 1952年） |
| 最大の特徴 | 平均符号長を最小にできる最適な接頭辞符号を生成する |
解説
コンピュータが文字を扱うとき、通常はASCIIなどの固定長符号を使います。
たとえばA～Eの5文字をすべて3ビットで表すと、どの文字も一律3ビット消費します。
しかし、文字ごとの出現頻度に偏りがある場合、よく使う文字に短いビット列を割り当てれば全体のデータ量を減らせます。この着想を数学的に最適化したのがハフマン符号です。
ハフマン木の作り方
ハフマン符号を生成するには「ハフマン木」と呼ばれる二分木を構築します。手順は次の通りです。
🌳 ハフマン木の構築手順（例：A=50%, B=30%, C=10%, D=10%）
ステップ1：各文字を出現確率とセットにしてノードとし、確率の昇順に並べる。
ステップ2：確率が最も小さい2つのノード（C:10% と D:10%）を取り出し、1つの親ノード（20%）にまとめる。
ステップ3：次に小さい2つ（20% と B:30%）をまとめて親ノード（50%）にする。
ステップ4：残った2つ（50% と A:50%）をまとめて根ノード（100%）にする。
ステップ5：根から各葉ノードへ向かう枝に「左＝0」「右＝1」を割り当て、根から葉までの経路が各文字の符号となる。
▶ ハフマン木の図解（クリックで展開）
[100%]
／ ＼
0 1
／ ＼
A(50%) [50%]
／ ＼
0 1
／ ＼
B(30%) [20%]
／ ＼
0 1
／ ＼
C(10%) D(10%)
根から各文字への経路を読むと：A＝0、B＝10、C＝110、D＝111 となる。
平均符号長の計算
上のハフマン木から得られた符号表で平均符号長を計算します。
📊 符号表と平均符号長の計算
| 文字 | 出現確率 | 符号 | 符号長 | 確率 × 符号長 |
|---|---|---|---|---|
| A | 0.50 | 0 | 1 | 0.50 |
| B | 0.30 | 10 | 2 | 0.60 |
| C | 0.10 | 110 | 3 | 0.30 |
| D | 0.10 | 111 | 3 | 0.30 |
| 平均符号長 | 1.70 ビット | |||
固定長（2ビット均等）なら平均2.0ビット。ハフマン符号なら1.7ビットで済み、約15%の圧縮効果が得られる。
「接頭辞符号」である理由
ハフマン符号には「ある文字の符号が、別の文字の符号の先頭部分と一致しない」という性質があります。これを接頭辞符号（プレフィックスフリー符号）と呼びます。
先ほどの例でいえば、Aの符号「0」はBの符号「10」の先頭とは一致しません。
この性質があるからこそ、ビット列を先頭から順に読むだけで一意に復号できます。もし接頭辞の条件を満たさない符号表を作ると、同じビット列が複数の文字列に解釈できてしまい復号が破綻します。
▶ 一意に復号できない例（クリックで展開）
仮に A=0, B=1, C=00, D=11 と符号を割り当てたとします。ビット列「00」を受け取ったとき、「AA」なのか「C」なのか判別できません。Aの符号「0」がCの符号「00」の接頭辞になっているためです。
ハフマン木から生成した符号はこの問題が起きないよう自動的に設計されます。
他の圧縮手法との比較
ハフマン符号は可逆圧縮の代表格ですが、試験では他の圧縮手法との区別も押さえておくと安心です。
ランレングス符号化：同じデータが連続する部分を「値＋連続回数」に置き換える方式。画像のように同じ色が並ぶデータに強いが、文字列の出現頻度の偏りには着目しない。
LZW符号化：データ中に繰り返し出現する文字列パターンを辞書に登録し、辞書番号で置き換える方式。GIF画像やZIP圧縮の基盤技術として利用される。
では、この用語が試験でどのように出題されるか見ていきましょう。
💡 ハフマン符号の核心を3行で
・出現頻度が高いデータに短い符号、低いデータに長い符号を割り当てる可逆圧縮
・ハフマン木（二分木）を構築して符号を決定し、平均符号長を最小化する
・接頭辞符号の性質により、先頭から読むだけで一意に復号できる
試験ではこう出る！
ハフマン符号は、基本情報技術者・応用情報技術者の午前問題で繰り返し出題されている定番テーマです。
出題パターンは大きく2つに分かれます。
📊 過去問での出題実績
| 試験回 | 出題内容 | 問われたポイント |
|---|---|---|
| FE H30秋 午前 問4 |
A～Eの5文字をハフマン符号化した符号表の空欄を埋める問題。 | ・接頭辞符号の条件を理解しているか ・既存の符号の先頭部分と重ならない符号を選べるか |
| FE R3 免除 問6 |
a～dの4文字の符号化方式4通りから、一意に復号可能かつ最短のものを選ぶ問題。 | ・一意復号可能性の判定（接頭辞条件） ・平均符号長の計算（確率×符号長の総和） |
| AP R2秋 午前 問4 |
FE R3免除 問6と同一内容の流用問題。 | ・FEとAPで同じ問題が出回る典型例 ・出題歴はAP H22秋問2、AP H28春問4にも遡る |
📝 IPA試験での出題パターン
パターン1：「一意に復号可能かつ最短の符号化方式を選べ」
4通りの符号表が提示され、接頭辞条件を満たすかどうかを判定し、満たすものの中で平均符号長を計算して最小のものを選ぶ形式。計算自体は単純な掛け算と足し算なので、手順さえ知っていれば確実に正答できる。
パターン2：「符号表の空欄を埋めよ」
一部の文字の符号が空欄になった符号表が提示され、接頭辞条件を崩さない符号を選ばせる形式。既存の符号の先頭部分と重ならない選択肢を消去法で絞れば正解にたどり着ける。
試験ではここまででOKです。ハフマン木を一から手書きで構築する手順まで求められることは午前問題ではないので、「接頭辞条件」と「平均符号長の計算」の2つだけ押さえてください。
【確認テスト】理解度チェック
ここまでの内容を理解できたか、簡単なクイズで確認してみましょう。
Q. データ圧縮手法であるハフマン符号化の説明として、最も適切なものはどれでしょうか？
- A. 出現頻度が高いデータに短い符号を、低いデータに長い符号を割り当て、平均符号長を最小化する可変長符号化方式である。
- B. 同じデータが連続する部分を「値＋連続回数」に置き換えることで、データ全体のサイズを削減する方式である。
- C. データ中に繰り返し出現する文字列パターンを辞書に登録し、辞書の参照番号で置き換えることで圧縮する方式である。
正解と解説を見る
正解：A
解説：
ハフマン符号化は、データの出現頻度に応じて可変長の符号を割り当て、平均符号長を最小にする圧縮アルゴリズムです。接頭辞符号の性質により一意に復号できる点が特徴です。
選択肢Bはランレングス符号化の説明です。連続する同一データの「長さ」に着目する方式であり、出現頻度には着目しません。選択肢CはLZW符号化に代表される辞書式圧縮の説明です。繰り返し出現するパターンを辞書番号に置き換える方式であり、ハフマン符号のように個々のデータに最適な符号長を割り当てる手法とは異なります。
よくある質問（FAQ）
Q. ハフマン符号は実際にどんな場面で使われていますか？
ZIP圧縮の内部アルゴリズム（DEFLATE）やJPEG画像の圧縮処理の最終段階で使われています。単独で使うよりも、LZ77などの辞書式圧縮と組み合わせて「辞書圧縮後のデータをさらにハフマン符号で短くする」という二段構えが主流です。PDFやPNG、FAXの送信データなど、身近なファイル形式の裏側で広く活躍しています。
Q. ハフマン符号の弱点はありますか？
符号表を生成するためにデータ全体の出現頻度をあらかじめ調べる必要がある点が弱点です。リアルタイムのストリーミングデータのように、全体を事前に走査できない場面では使いにくくなります。この弱点を補うために、符号表を動的に更新する「適応型ハフマン符号」も考案されていますが、IPA試験の範囲では深追い不要です。
Q. ハフマン符号と算術符号の違いは何ですか？
ハフマン符号は各データに整数ビットの符号を割り当てますが、算術符号（Arithmetic Coding）はメッセージ全体を1つの小数値に変換します。算術符号の方が理論上の最適値（情報エントロピー）に近い圧縮率を達成できますが、計算コストが高い傾向にあります。試験ではハフマン符号の方が圧倒的に出題頻度が高いため、まずハフマン符号を優先して覚えてください。
Q. ハフマン符号は「非可逆圧縮」にも使えますか？
ハフマン符号自体は可逆圧縮です。しかし、JPEGのように「まず非可逆処理（離散コサイン変換＋量子化）でデータを間引き、その後の仕上げにハフマン符号で可逆圧縮する」という組み合わせで使われるケースがあります。この場合、全体としては非可逆圧縮になりますが、ハフマン符号が担当するパートは可逆です。
