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

解説お願いいたします。

応用問題P118のハフマン木の問題にて
解説P120の（2）（3）の図のイメージができません。
ハフマン木を作るにあたり
問題から節を設けるとは書いてありますが
でも(DB、DBC)という節を作るなんて書いてないのですが、
どこから推測したらいいのですか。
問題と解説の理解が嚙み合わないのでお願いいたします。

問題文の（ハフマン木の作成手順）に記載されています。

まず、 A,B,C,Dの出現回数を求めますよね。
そうすると A10,B2,C4,D3 になります。

（ハフマン木の作成手順）(1)より、上記を降順に並べます。
(1) A10,C4,D3,B2 になります。

ここで(2)の通り、「出現回数の最も少ない記号」と「次に少ない記号」を葉として新たな節を設ける。
「出現回数の最も少ない記号」 = B2
「次に少ない記号」 = D3
上記を葉として新たに作った節が BD5 のことです。

BとDを葉にもつ 節BD ができたら、まだAとCがありますので同じ手順で繋げます。
先ほど作ったBD5の左隣にC4を配置します。
C4とBD5の節としてCBD9ができますので、CBD9の右隣にA10を配置します。
CBD9とA10の節としてCBDA19ができます。

あとはCBDA19から出現回数が少ない記号に向かう枝に1、もう片方に0を入れるのです。

すると上からAは0、Bは101、Cは11、Dは100になります。

追記：
BD5とかCBD9と書いてますが主さんのいうDB、DBCと同じ意です。

Ozさん

その本は持っていないのですが、別の本を読んでいてたまたまハフマン木の所で気になってやってみたのですが

> まず、 A,B,C,Dの出現回数を求めますよね。
> そうすると A10,B2,C4,D3 になります。
> 少ない記号に向かう枝に1、もう片方に0を入れる

の場合の最終結果は
A = 0
C = 10
D = 110
B = 111
となると思いますが、違うのでしょうか？

木構造としては見にくいですが下のようになって、それぞれの項目に向かう時に辺の数字を拾うと上のものになると思います。

０｜ーーーーー｜１
  ｜    ０｜ーーーー｜1
  ｜      ｜    ０｜ーー｜１
A(10)ーーC(4)ーーD(3)ーーB(2)

木が崩れてだいぶ見にくかったので・・・

０｜ーーーーー｜１
＿｜＿＿０｜ーーーー｜1
＿｜＿＿＿｜＿＿０｜ーー｜１
A(10)ーーC(4)ーーD(3)ーーB(2)

> 出現回数が少ない記号に向かう枝に1、もう片方に0を入れるのです。
（回答No.2）

ハフマン木が描けてしまえば，各二分木の枝のどちらに0と1を割り当てても（その割り当てを逆にしても）ハフマン符号化としては問題ないです。

回答No.2の
０＿＿  Ａ(10)
１１＿  Ｃ(4)
１００  Ｄ(3)
１０１  Ｂ(2)

回答No.4の
０＿＿  Ａ(10)
１０＿  Ｃ(4)
１１０  Ｄ(3)
１１１  Ｂ(2)

どちらも正しくハフマン符号化／復号できます。

ただし，問題文に0と1の割り当て規則が明記してあるのなら，
それに従って解答しないと正解にはならないです。
（私はこの参考書を持っていないのでこの点を確認できません）

横から失礼します。

Ozさん
>先ほど作ったBD5の左隣にC4を配置します。
降順なので、BD5の右隣にC4を配置では？
>CBD9の右隣にA10を配置します。
こちらも同様に、CBD9の左隣にA10を配置だと思います。

電タックさん
ハフマン木は、

０｜ーーーーーーー｜１
＿｜＿＿＿＿０｜ーーーー｜1
＿｜＿＿０｜ーー｜１
A(10)ーーD(3)ーーB(2)ーーC(4)

となるので、
A = 0
C = 11
D = 100
B = 101
になると思います。

皆様詳しい解説ありがとうございます。
〉ここで(2)の通り、「出現回数の最も少ない記号」と「次に少ない記号」を葉として新たな節を設ける。

  初見で読んだ時に引っかかってしまい混乱してしまいました。自分で解答は出来たのですが問題への引っかかりがあって慣れないですが練習いたします。

えっと私は手元にこの本があるので言えるのですが、主さんの「(DB、DBC)という節を作るなんて書いてないのですが」という点は（ハフマン木の作成手順）の(2)に記載されているという点です。

＞主さん
最初は意味わからんですよね。わかりやすく言えなくてすみません。
P120からの解説を読みながら（ハフマン木の作成手順）を沿ってみると何回目かでイメージ湧いてくると思います。ファイトです。

補足します。

問題文のハフマン木の作成手順では、
・各記号を出現回数の降順に並べる。
・節から出現回数が少ない記号に向かう枝に1、他方に0を割り当てる。
(他は省略)
となっています。

この問題、本試験の改題ですよね・・・できないってことはそのレベルまで達していないってことか・・・

jjon-comさん、wrinklyさん

木構造を作った上で符号の割当を初めたら左右の０・１はどのエッジでも一定にすると勝手に思い込んでいました。

> 節から出現回数が少ない記号に向かう枝に1、他方に0を割り当てる。
に従って組めば以下になるので、先に作った左右固定の符号だと問題としてはNGだったんですね。
０：A(10)ーCDB(9)：１
１：C(４)ーDB(５)：０
０：D(５)ーB(２)：１

０｜ーーーーー｜１
＿｜＿＿１｜ーーーー｜０
＿｜＿＿＿｜＿＿０｜ーー｜１
A(10)ーーC(4)ーーD(3)ーーB(2) 

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

まきさん、Ozさん
横槍で掲示板使ってしまい申し訳ない。