ハフマン木

ハフマン木を作りたいので勉強中。LHAとZIP―圧縮アルゴリズム×プログラミング入門をもう一度、読もう。

関数言語っぽいアレンジはあとですることにして、とりあえず本の内容をまとめる。

ハフマン符号器

1. バッファ中のデータの頻度をカウントする(FrequencyTable)
2. ハフマン木を作る
   1. 教科書通りのやりかたで木を作る
   2. すべてのノードの根からの深さを調べる
   3. 深さの分布を調べる
   4. 16よりも深くにあるノードを探す

1. ビット長テーブルを作る
2. ビットパターンを割り当てる
3. バッファ中のをデータをビットパターンに置きかえる

ハフマン復号器

1. ビット長をファイルから読み込む
2. ビットパターンを割り当てる
3. 入力と一致するビットパターンを探してもとのデータに置きかえる
   1. 効率をあげるための工夫がなされているので保留