基本情報技術者 2018年 秋期 午前（科目A） 問04
問題文
出現頻度の異なるA, B, C, D, Eの5文字で構成される通信データを、ハフマン符号化を使って圧縮するために、符号表を作成した。aに入る符号として、適切なものはどれか。
選択肢
ア：001
イ：010
ウ：101
エ：110（正解）
🔒 解説は解答すると表示されます
ハフマン符号の符号割当【午前解説】
正解の理由
問題の符号表にはA=00, B=01, C=10, E=111と与えられています。可変長・プレフィックスフリーであるハフマン符号では，既存の短いコードが他のコードの先頭になってはなりません。選択肢のうち
- 001は00（A）の拡張なのでプレフィックス条件を破る、
- 010は01（B）の拡張なので破る、
- 101は10（C）の拡張なので破る、 となり不適です。残る110は既存のどのコードの先頭にもならないため整合し，符号木（ハフマン木）を作るとD=110, E=111としてDEが枝11を共有する形になります。よって正解は エ（110）です。
解法ステップ
- 与えられた符号をリストアップ：A=00, B=01, C=10, E=111。
- プレフィックス条件を確認：候補が既存符号の先頭にならないかをチェックする。
- 各選択肢を照合：
- 001は00の拡張 → 不可
- 010は01の拡張 → 不可
- 101は10の拡張 → 不可
- 110は既存のどれも先頭ではない → 可
- 可となった110を割り当て，木の形（左右の枝と深さ）を確認して整合性を確かめる。
選択肢別の誤答解説
- ア: 001 — Aの符号00の下位に位置する拡張なのでプレフィックス条件に反し無効。
- イ: 010 — Bの符号01を先頭としてしまうためプレフィックス違反で無効。
- ウ: 101 — Cの符号10の拡張であり，プレフィックス条件を満たさないので無効。
- エ: エ 110 — 既存符号の先頭にならず，E=111と揃ってDEの枝11を形成するため妥当で正解。
よくある誤解
- 「ハフマンでは常に最小頻度同士を順に結合する」と誤解し，必ず同じ木になると思い込む。実際には同率や結合順序の違いで木は一意でないが，提示された部分符号からは一意に決まることがある。
- 「長い符号＝頻度が低い」という単純化に頼りすぎて，既に与えられたコードとのプレフィックス関係を確認しないミス。
- 「与えられたコードは順序どおりに木を作った結果だ」と決めつけ，コードの先頭関係（プレフィックス）確認を省くこと。
補足コラム
ハフマン符号では必ずしも一意の割り当てにならないことがあります（同じ頻度の組合せや結合順で差が出る）が，部分的に符号が与えられている問題では残りの符号が一意に定まることが多いです。今回のケースでの平均符号長は，頻度をパーセント（合計100）と見なすと
ビット/文字
となり，ハフマン符号化で得られる短縮効果が確認できます。
ビット/文字
となり，ハフマン符号化で得られる短縮効果が確認できます。
FAQ
Q1: ハフマン木は必ず一意ですか？
A1: いいえ。同じ重みの結合順序次第で複数の最適な木が存在します。ただし，部分的に符号が固定されていると残りが一意に定まる場合があります。
A1: いいえ。同じ重みの結合順序次第で複数の最適な木が存在します。ただし，部分的に符号が固定されていると残りが一意に定まる場合があります。
Q2: 既存の短い符号があると，長い符号はどう決めればよいですか？
A2: プレフィックス条件を満たすように，既存のコードを起点に残りの葉を配置します。候補が既存コードの拡張なら不可です。
A2: プレフィックス条件を満たすように，既存のコードを起点に残りの葉を配置します。候補が既存コードの拡張なら不可です。
Q3: なぜ110と111がEとDのように同じ11を共有するのですか？
A3: 13と12の小さい頻度を先に結合してDE=25を作り，それを他のノードと結合するとDEの枝が深くなり，両者は同じ先頭ビット列（11）を共有する形になります。提示されたE=111に合うようにD=110が決まります。
A3: 13と12の小さい頻度を先に結合してDE=25を作り，それを他のノードと結合するとDEの枝が深くなり，両者は同じ先頭ビット列（11）を共有する形になります。提示されたE=111に合うようにD=110が決まります。
関連キーワード: ハフマン符号, 可変長符号, プレフィックス, 圧縮率, 平均符号長, ハフマン木, 優先度付きキュー
\ せっかくなら /
基本情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！