基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

H30 秋の ハフマン符号の問題で質問です。

解答は、a=110（文字D 出現度%) です。

ただ、Eの符号110と"11"の部分が被りますが、
なぜ110は問題ないのか気になります。

001は、００と被るのでNG
010は、０１と被るのでNG
101は、10と被るのでNG
となり、これは理解できます。

「11」の時点では完全一致するものがないためです。

ほかの選択肢は2ケタの時点で、その2ケタが完全一致するものがあります。
たとえば、選択肢アが回答の場合、
A＋Dは「00＋001」ですが、「00」をAと読んだあと、2回目の「00」もAと読んでしまいます。これは、00＝Aと完全一致しているためです。

一方、回答通りD＝110の場合、
D＋Eは「110111」です。
「11」まで読んでも特定できる文字列がないので、「110」まで読んでDと特定します。次の「11」も同様に読めないので3桁目含めた「111」まで読んでEと判定します。

基本情報 平成30年 秋期 午前 問4
https://www.fe-siken.com/kakomon/30_aki/q4.html

> 解答は、a=110（文字D 出現度%) です。
> ただ、Eの符号110と"11"の部分が被りますが、
> なぜ110は問題ないのか気になります。

この問いのハフマン表には 11 という符号（11 という2bitに対応する文字）は存在しないから。
（No.2 で解説のあった、「11」の時点では完全一致するものがないため、と同じです）

同じことを別の例で言い換えてみます。

'A' は 00 で、'B' は 01 です。
先頭の 0 の部分が被りますがなぜ問題ないのか。
それは、この問いのハフマン表には 0 という符号（0 という1bitに対応する文字）は存在しないから。

この問いのハフマン表をハフマン木で表すと次のようになります。
イラストが描けないので、左が根側、右が葉側の2分木を次のように表してみました。文字位置がずれるようなら等幅フォントのテキストエディタなどに貼り付けてください。

お二方、解説ありがとうございます！

お二人の解説で理解深めることが
できました。

要素数が違うので、3桁まで読み込まないと特定できないので110は対象外になるのですね。

ありがとうございました。