ハフマン符号

前提

• 符号化
  • 情報を2進数のデジタルデータに変換
  • なるべく少ないビット数が望ましい
    • 処理効率・メモリ効率から

ハフマン符号化

• データの出現頻度に着目した圧縮方法
• 出現頻度の高いデータに短いビット列を割り当て、出現頻度の低いデータに長いビット列を割り当てる

アルゴリズム

• 貪欲法
  • コストを小さくするためには、小さい2つをマージしていくことを繰り返す。それを降順に扱えばよい。
  • 頻度の小さいデータをマージすることをくりかえすと、頻度の小さいデータほど２分木の深いところに位置するようになる。
  • 二分木で一段ごとに文字を追加していけばよい。