ハフマン符号表の空欄は接頭語条件で絞り込む
基本情報技術者試験 平成30年度秋期 午前 問4 ／ 基礎理論 › 情報に関する理論
過去問にチャレンジ
出現頻度の異なるA，B，C，D，Eの5文字で構成される通信データを，ハフマン符号化を使って圧縮するために，符号表を作成した。aに入る符号として，適切なものはどれか。
- ア
001
- イ
010
- ウ
101
- エ
110
会話形式の解説
講師この問題では、符号表のなかで一つだけ空いているDの符号を選びます。ポイントは、ハフマン符号ではどの符号も他の符号の先頭部分と一致しない、という性質です。これを接頭語条件と呼びます。
受験者出現頻度が書いてあるので、まず頻度から木を作らないといけないと思っていました。計算に時間がかかりそうで不安です。
講師木を作っても解けますが、もっと短い方法があります。表ではAが00、Bが01、Cが10、Eが111と決まっていますね。Dの符号は、これらとどんな関係でなければならないと思いますか。
受験者接頭語条件があるので、Dの符号が00や01や10で始まっていてはいけない、ということでしょうか。
講師そのとおりです。ハフマン符号では文字の区切りに記号を入れないので、受信側は先頭から読んで、表にある符号と一致した時点でその文字だと判断します。では001を考えてみましょう。
受験者001は、先頭の00まで読んだ時点でAと判断されてしまいます。だからDとしては復号できない、ということですね。
講師はい。同じように010と101も確かめてみてください。
受験者010は先頭が01なのでBと読まれます。101は先頭が10なのでCと読まれてしまいます。どちらもDには使えません。
講師残るのは110です。00・01・10のどれでも始まらず、Eの111とも違います。符号の木でいうと、11から分かれた枝の先にDの110とEの111が並ぶ形になります。
受験者先頭2ビットを既存の符号と照らし合わせるだけで決まるので、計算が苦手でも落ち着いて解けそうです。
講師検算として木を作ってみましょう。頻度が最も小さいD（13）とE（12）を結合して25、次にC（24）とその25を結合して49、続いてA（26）とB（25）を結合して51にします。49の側に1、51の側に0を割り当てると、Cは10、DとEは110と111になり、表と一致します。
受験者頻度の小さい二つが同じ親を持つので、DとEの符号は最後の1ビットだけが違うのですね。
講師そのとおりです。ハフマン符号は、出現頻度の高い文字に短い符号、低い文字に長い符号を割り当てる可変長符号です。空欄を埋める問題では、まず選択肢の先頭部分が既存の符号と重ならないかを確かめるのが近道だと覚えておいてください。
まとめ
この問題は、ハフマン符号の符号表で空欄になっているDの符号を選ぶものです。ハフマン符号は、どの符号も他の符号の先頭部分と一致しないという接頭語条件を満たしているため、区切り記号がなくても一通りに復号できます。001・010・101は、それぞれ先頭がAの00、Bの01、Cの10と一致するので使えません。110だけが既存のどの符号とも先頭が重ならず、Eの111とも異なるので正解です。頻度の小さいDとEから順に結合して木を作ると、DとEが110と111に並ぶことも確かめられます。
解答・解説
正解はエです
この問題のテーマ
ハフマン符号の符号表で、空欄になっているDの符号を求める問題です。どの符号も他の符号の先頭部分と一致してはならないという条件（接頭語条件）を理解しているかが問われます。
解き方の考え方
表ではA＝00、B＝01、C＝10、E＝111と決まっています。ハフマン符号はどの符号も他の符号の先頭部分にならないように作るので、復号するときは先頭から読むだけで区切りが一つに決まります。したがって、Dの符号は00・01・10で始まってはならず、111とも異なっていなければなりません。各選択肢の先頭2ビットを既存の符号と照らし合わせれば、条件を満たすものは一つに絞れます。
選択肢ごとの解説
- ×ア 001001は先頭の2ビットがAの符号00と同じです。受信側は00まで読んだ時点でAと判断してしまうため、Dとして復号できません。
- ×イ 010010は先頭の2ビットがBの符号01と一致します。01を読んだ時点でBと解釈されてしまうので、接頭語条件を満たしません。
- ×ウ 101101は先頭の2ビットがCの符号10と同じです。10を読んだ時点でCと確定してしまうため、Dの符号には使えません。
- ○エ 110110は00・01・10のどれでも始まらず、Eの111とも異なります。そのため、どの符号とも先頭部分が重ならず、接頭語条件を満たします。符号の木で見ると、11の下の枝がDの110とEの111に分かれる形になります。
補足
頻度から木を作って確かめることもできます。まず最小のD（13）とE（12）を結合して25にし、次にC（24）とその25を結合して49にします。続いてA（26）とB（25）を結合して51にします。49の側に1、51の側に0を割り当てると、Cは10、DとEは11の下に並んで110と111になり、表の符号と一致します。
POINT
- ハフマン符号は、出現頻度の高い文字に短い符号を、低い文字に長い符号を割り当てる可変長符号です。
- どの符号も他の符号の先頭部分にならないこと（接頭語条件）が、区切り記号なしで一意に復号できる理由です。
- 空欄の符号を求める問題では、選択肢の先頭部分が既存の符号と一致しないかを確かめるのが近道です。
- 木を作るときは、頻度が最も小さい2つを順に結合していきます。結合された2文字は同じ親を持ち、符号は最後の1ビットだけが異なります。