参考サイト:https://www.fe-siken.com/kakomon/30_aki/q4.html
そもそもハフマン符号化って？
可変長の符号化方式。
出現確率が高いデータには短い符号を、低いデータには長い符号を与えることで圧縮を効率よく行う方法。
問題の注意点
平成30年度秋期の問題を例に見ていく。
符号表は出現頻度をキーに、上から降順に記載されている。
Dよりも一つ出現頻度の高いCの符号は 10であり、10進数に直すと2になる。
Dよりも一つ出現頻度の低いEの符号は111であり、10進数に直すと7になる。
そのため解答は10進数に直したとき、3~6になるものを解答すれば良いように思われるかもしれない。
しかし、実際に選択肢を10進数に直すと次のようになる。
(ア)001 → 1
(イ)010 → 2
(ウ)101 → 5
(エ)110 → 6
先ほどの考え方でいくと、(ア)と(イ)は範囲に入ってないから良いとして、(ウ)と(エ)がどちらも範囲に入ってしまっている。
つまり、この問題を解答するための観点として、範囲だけでは足りないということだ。
では、何が足りないのか。
それは、(ウ)と(エ)の符号を左から「展開」しようとしてみればわかる。
下記にその結果を示す。
(ウ)101 → 241
(エ)110 → 110
上にある通り、(ウ)を D の符号として割り当ててしまうと、実際に圧縮された文字を展開した時に、「101」の接頭辞「10」が C として展開されてしまうのだ。
まとめ
ハフマン符号化に関する問題が出題された時は、下記のことに注意する。
・解答しようとしている符号が、出現頻度の高い文字に対して割り当てられている符号よりも大きいこと。
・解答しようとしている符号が、出現頻度の低い文字に対して割り当てられている符号よりも小さいこと。
・解答しようとしている符号が、符号表を基に展開できないこと。