ハフマン符号化の問題について

午前試験免除制度対応!基本情報技術者試験のeラーニング【独習ゼミ】
しおさん
(No.1)
平成30年度問4について
出現頻度の異なるA,B,C,D,Eの5文字で構成される通信データを,ハフマン符号化を使って圧縮するために,符号表を作成した。aに入る符号として,適切なものはどれか。
★出現頻度の高い方から順にABCDEで
A:00,B:01,C:10,D:XX,E:111
Dに入るのは何か
という問題ですが、ハフマン符号化の木の作り方から考えると、このようなビット列になるのが理解できません。A:0,B:10,C:110,D:1110,E:1111
という風なものかと思っていましたが、他にも符号化の仕方があるのでしょうか?このサイトの解説をみてもさっぱりでした。どなたか分かる方宜しければよろしくお願いします。
2020.10.19 08:30
ミソシルさん
(No.2)
ハフマン木を平成31年春のアルゴリズム問題のようにして作成してみます。
出現確率を出現回数として計算して、且つ問題文の符号に重なるように作成すると、
              100
          0/     \1
          51          59
   0 /    1\      0/   \1
  26          25   24       25
   A           B    C    0 /  \1
                         12       13 
                         ?        E
となるはずです。
私の浅学さが露見したら申し訳ありませんが、本来ならAとBの位置は逆のはずですが、この問題に当てはめるしかなさそうなのでやってみると上のようになります。
ハフマン木はこうやって作っていくものなので、もし疑問に感じた場合は私が言ったアルゴリズム問題を解いてみるといいかもしれません。
2020.10.19 09:55
しおさん
(No.3)
迅速なご回答ありがとうございます!そのハフマン木の理屈は理解できました、AとBが逆なのだけがちょっと腑に落ちない感じですね。。ありがとうございます!
2020.10.19 10:45
ミソシルさん
(No.4)
すいません、間違えました。
0と1の順序は任意であったことを失念していました。
正確には以下のようになり、問題文に沿うように0と1を配置します。
              100
          1/      \0
          49           51
   0 /    1 \      1/   \0
  24          25   25       26
   C                B       A
           1/  \0
          12      13
          E        D
2020.10.19 12:38

返信投稿用フォーム

スパム防止のために初投稿日から10日以上経過したスレッドへの書き込みは禁止しています。

その他のスレッド


Pagetop