最終更新日：2026年9月20日
fe fe-technology basic-theory binary
まず結論
ハフマン符号は、出現頻度の高い記号には短いビット列、出現頻度の低い記号には長いビット列を割り当て、平均符号長を短くする可変長符号です。
FE試験では、まず次の順で考えると判断しやすくなります。
1. 一意に復号できるか
2. できるものだけ残す
3. 出現確率 × 符号長で平均符号長を求める
4. 平均符号長が短いものを選ぶ
特に、
よく出る記号 → 短い符号
あまり出ない記号 → 長い符号
という対応が重要です。
直感的な説明
4種類の記号をすべて同じ2ビットで表すとします。
a → 00
b → 01
c → 10
d → 11
この方式では、どの記号も2ビット必要です。
ところが、もし出現頻度が、
a → 50%
b → 30%
c → 10%
d → 10%
だったら、よく出る a や b に短い符号を使った方が、全体として短くできそうです。
例えば、
a → 0
b → 10
c → 110
d → 111
とすると、よく出る a は1ビット、b は2ビットで表せます。
平均すると、
1×0.5 + 2×0.3 + 3×0.1 + 3×0.1
= 1.7ビット
となり、固定長の2ビットより短くできます。
このように、出現頻度に応じて符号の長さを変えるのが可変長符号の考え方です。
定義・仕組み
固定長符号と可変長符号
固定長符号では、すべての記号を同じ長さで表します。
a → 00
b → 01
c → 10
d → 11
4種類なら2ビットずつ必要です。
一方、可変長符号では、記号ごとに符号長を変えます。
a → 0
b → 10
c → 110
d → 111
出現頻度が偏っているときは、可変長符号を使うことで平均符号長を短くできます。
平均符号長
平均符号長は、
平均符号長
= Σ（各記号の出現確率 × その記号の符号長）
で求めます。
例えば、
| 記号 | 出現確率 | 符号 | 符号長 |
|---|---|---|---|
| a | 0.5 | 0 | 1 |
| b | 0.3 | 10 | 2 |
| c | 0.1 | 110 | 3 |
| d | 0.1 | 111 | 3 |
なら、
1×0.5 + 2×0.3 + 3×0.1 + 3×0.1
= 1.7
なので、平均符号長は 1.7ビット です。
一意に復号できることが前提
可変長符号なら何でもよいわけではありません。
符号化したビット列から、元の記号列を一意に復元できることが必要です。
例えば、
b → 1
d → 11
という割当てでは、ビット列 11 を見たとき、
b b → 1 1
d → 11
のどちらなのか区別できません。
このような符号は使えません。
プレフィックス符号
ハフマン符号は、ある符号語が別の符号語の先頭部分にならないように構成されます。
例えば、
a → 0
b → 10
c → 110
d → 111
では、
0は他の符号の先頭ではない10も他の符号の先頭ではない110と111も互いに区別できる
ので、左から順に読めば迷わず復号できます。
FE試験では、厳密な用語を覚えるより、
短い符号が、別の長い符号の先頭になっていないか
を見ると判断しやすくなります。
科目Aでどう出る？
科目Aでは、次のような問題が出やすいです。
- 複数の符号表から、一意に復号できるものを選ぶ
- 出現頻度から平均符号長を計算する
- 最も短い平均符号長になる符号表を選ぶ
- 固定長符号と可変長符号を比較する
- ハフマン符号の特徴を選ぶ
判断手順は次の順がおすすめです。
① 一意に復号できる？
↓
② できない選択肢を消す
↓
③ 出現確率 × 符号長を計算
↓
④ 合計が最小のものを選ぶ
ここで大事なのは、いきなり平均ビット数を計算しないことです。
復号できない符号は、平均符号長が短くても候補から外れます。
どんな場面で使う？
ハフマン符号は、データ圧縮で使われる代表的な符号化方式です。
考え方はとてもシンプルです。
よく出るもの
→ 短く表す
あまり出ないもの
→ 長く表す
この仕組みによって、情報を失わずに全体のデータ量を減らせます。
このように、元の情報を完全に復元できる圧縮を 可逆圧縮 といいます。
よくある誤解・混同
平均符号長が短ければ、それだけで正解
誤りです。
まず、一意に復号できることが必要です。
復号できない
→ その時点で除外
復号できる
→ 平均符号長を比較
この順番で判断します。
4種類なら必ず2ビット必要
固定長符号なら、
2^2 = 4
なので2ビット必要です。
しかし、可変長符号では、出現頻度に偏りがあれば平均符号長を2ビット未満にできる場合があります。
ここは、何ビット必要？種類数から必要ビット数を求める方法との違いです。
種類数から最低ビット数を求める
→ 固定長符号の考え方
出現頻度を使って平均を短くする
→ 可変長符号・ハフマン符号
出現頻度が低い記号ほど短くする
逆です。
出現頻度が高い
→ 短い符号
出現頻度が低い
→ 長い符号
と割り当てることで、平均符号長を短くします。
符号長の合計を最小にすればよい
見るのは単純な符号長の合計ではありません。
重要なのは、
出現確率 × 符号長
の合計です。
頻繁に出る記号の符号長の影響が大きくなります。
参考になる一次情報
ハフマン符号は、David A. Huffman が1952年に発表した論文で提案された方式です。
論文では、メッセージ集合に対して平均符号長を小さくする符号の構成方法が示されています。
FE試験では論文のアルゴリズムを細かく追う必要はありませんが、
出現頻度を利用する
→ 平均符号長を短くする
→ 一意に復号できる
という考え方を押さえておけば十分です。
公式の試験範囲は、IPAの情報も確認できます。
まとめ（試験直前用）
- ハフマン符号は 可変長符号
- 出現頻度が高い記号ほど 短い符号
- 出現頻度が低い記号ほど 長い符号
- まず 一意に復号できるか を確認する
- 平均符号長は 出現確率 × 符号長 の合計
- 固定長符号より平均符号長を短くできる場合がある
試験中は、次の順番で判断します。
復号できる？
↓
頻度が高い記号ほど短い？
↓
出現確率 × 符号長
↓
平均が最小？