出典：公益社団法人 日本技術士会「技術士第一次試験 過去問題」
5つのシンボルP、Q、R、S、Tで構成された信号(生起確率0.10、0.05、0.20、0.25、0.40)をハフマン符号化したときの最も適切な符号化方法を選ぶ問題。
確率から、ハフマン符号の木を構成して、符号語の長さが最適となる符号表を選ぶ問題。
① ハフマン符号: 確率の小さい2つを順に併合。確率の大きいものほど短い符号、どの符号も他の符号の先頭にならない
② Q0.05+P0.10=0.15 → +R0.20=0.35 → +S0.25=0.60 → +T0.40。符号長は T1・S2・R3・P4・Q4 → これに合うのは①。②はS=1がQ=10の先頭になり、⑤はTが2ビット
③ ①
ハフマン法では、確率の小さい2つを順に併合する。まず、P(0.10)とQ(0.05)を併合して0.15。次に、R(0.20)と0.15を併合して0.35。次に、S(0.25)と0.35を併合して0.60。最後に、T(0.40)と0.60を併合する。符号長は、Tが1ビット、Sが2ビット、Rが3ビット、PとQが4ビットとなる。これに合致するのは、P:0010、Q:0011、R:000、S:01、T:1の①である。この符号は、どの符号語も他の符号語の語頭にならない(語頭条件を満たす)。
ハフマン符号=確率の小さい2つを順に併合して木を作り、確率の大きいシンボルほど短い符号語を割り当てる。平均符号長が最小の語頭符号になる。
キーワード: ハフマン符号、可変長符号、データ圧縮、生起確率、語頭符号、平均符号長、情報工学部門