ハフマン符号化

【基本情報技術者試験】ハフマン符号化 - ITを分かりやすく解説

出現確率の高いものには短いビット列を割り当てることで圧縮する

手順

1. 各データを出現確率の高い順に並べる
2. 最も出現確率の低い2つを1つにする
3. 手順2を繰り返してハフマン木を完成させる
4. 枝の左にゼロ、右に1を割り当てる(逆でもいい)

0, 10, 110, 1110, 11110, …と、1をどれだけ並べるか