平成30年度 秋期 基本情報技術者試験 問4

解説

正解は4です。 ハフマン符号は、出現頻度の高い文字に短い符号を、低い文字に長い符号を割り当てる可変長符号です。 どの符号も他の符号の先頭部分（接頭語）にならないことが条件です。 【符号木の作成】 頻度の最も低いEの12％とDの13％を併合して25％にします。 次にCの24％と、併合したDEの25％を併合して49％にします。 残るAの26％とBの25％を併合して51％にします。 最後に49％と51％を併合して符号木が完成します。 A＝00、B＝01なのでABの組が0側、C＝10なのでCとDEの組が1側です。 DEの組は11で始まり、E＝111なので、残るDは110になります。 【選択肢別解説】 1：× 001は先頭がAの符号00と同じになるので、復号時にAと区別できず誤りです。 2：× 010は先頭がBの符号01と同じになるので、Bと区別できず誤りです。 3：× 101は先頭がCの符号10と同じになるので、Cと区別できず誤りです。 4：○ 110はどの符号の接頭語にもならず、Eの111と対になるDの符号として成り立ちます。 【ポイント】 ハフマン符号の空欄補充は、他の符号の接頭語になっていないかを調べると素早く判定できます。 頻度の低い2つを併合する操作を繰り返すことが、符号木作成の基本です。