平成31年度春季基本情報午後問8

平成31年度春季 基本情報技術者試験(FE)の午後問題8は、

• ハフマン符号化を用いた文字列圧縮

に関する問題でした。

• 問題

ハフマン符号は、出現頻度が高い文字については短いビット列を、出現頻度が低いものに対しては長いビット列を割り当てることで、文字列全体のビット長を短くできるというアルゴリズムです。学生時代に習ったときには、ちょっと感動したことを今でも覚えています。 文字列の圧縮を行う前に各文字の出現頻度を求める必要があるので、文字列に対して2回の走査が必要になります*1。この欠点を改善し、1回の走査で圧縮まで行う動的ハフマン符号がありますね。

プログラム例(h31h_fe_pm8.c)

グローバル変数、ローカル変数や引数の仕様など少し変更しています。

実行結果

$ gcc h31h_fe_pm8.c && ./a.out
A: 1
B: 010
C: 00
D: 011

関連

• 情報処理技術者試験の過去問を実際に動かしてみよう!

*1:マルチパス