あつみ先生
ここでは，可逆圧縮のひとつである「ハフマン符号化」のアルゴリズムについて学習していきましょう。
教科書や参考書などを参照しながら，以下の空欄に当てはまる語句を調べましよう。
スライドの解説
出現回数に応じて，出現頻度の高い文字に短いビット列を，低い文字に長いビット列を与える圧縮法をハフマン符号化といいます。
例えば，文字列「AAAAAAAAABBBBCCCDDEEF」をハフマン符号化により圧縮することを考えてみましょう。
ハフマン符号化では，まず与えられたデータにおける各文字の出現回数を数え，それをもとにハフマン木を作成します。次に，ハフマン木から，各文字に与えるビット列を求めることにより，圧縮することができます。
なお，ハフマン木の作り方は，次のとおりです。
【ハフマン木の作り方】
手順❶：出現回数が多い文字を左から順に並べ，出現回数を丸数字で書き込む。
手順❷：最も小さい数字から順に2つ選び，それを足した結果を上に書き，枝を結ぶ。
手順❸：手順❷を繰り返す。
手順❹：節から出る枝の左側に0，右側に1を与える。
この手順に従って作成したハフマン木がスライド右下図になります。