基本情報技術者 2018年 秋期 午前（科目A） 問04

ハフマン符号の符号割り当て【午前2 解説】

要点まとめ

• 結論：与えられた符号表から D に割り当てられる符号は エ の 110 が唯一整合する候補です。
• 根拠：00,01,10 がそれぞれ A,B,C の完全な符号であり，残る枝 11 の下に DE を配置すると E=111 から D=110 に決まります。
• 差がつくポイント：プレフィックス条件（ある符号が別の符号の先頭にならない）を使って既存コードとの衝突を速やかに検出することです。

正解の理由

• 001 は 00（A）の拡張なのでプレフィックス条件を破る、
• 010 は 01（B）の拡張なので破る、
• 101 は 10（C）の拡張なので破る、 となり不適です。残る 110 は既存のどのコードの先頭にもならないため整合し，符号木（ハフマン木）を作ると D=110, E=111 として DE が枝 11 を共有する形になります。よって正解は エ（110）です。

よくある誤解

• 「ハフマンでは常に最小頻度同士を順に結合する」と誤解し，必ず同じ木になると思い込む。実際には同率や結合順序の違いで木は一意でないが，提示された部分符号からは一意に決まることがある。
• 「長い符号＝頻度が低い」という単純化に頼りすぎて，既に与えられたコードとのプレフィックス関係を確認しないミス。
• 「与えられたコードは順序どおりに木を作った結果だ」と決めつけ，コードの先頭関係（プレフィックス）確認を省くこと。

解法ステップ

1. 与えられた符号をリストアップ：A=00, B=01, C=10, E=111。
2. プレフィックス条件を確認：候補が既存符号の先頭にならないかをチェックする。
3. 各選択肢を照合：
   • 001 は 00 の拡張 → 不可
   • 010 は 01 の拡張 → 不可
   • 101 は 10 の拡張 → 不可
   • 110 は既存のどれも先頭ではない → 可
4. 可となった 110 を割り当て，木の形（左右の枝と深さ）を確認して整合性を確かめる。

選択肢別の誤答解説

• ア: 001 — A の符号 00 の下位に位置する拡張なのでプレフィックス条件に反し無効。
• イ: 010 — B の符号 01 を先頭としてしまうためプレフィックス違反で無効。
• ウ: 101 — C の符号 10 の拡張であり，プレフィックス条件を満たさないので無効。
• エ: エ 110 — 既存符号の先頭にならず，E=111 と揃って DE の枝 11 を形成するため妥当で正解。

補足コラム

FAQ