圧縮アルゴリズム (4) ハフマン符号化 - 適応型ハフマン圧縮

上の例では、赤で塗られた同レベルの節を入れ替えて木の右側ほどレベルが深くなるようにしてから、黄色で塗られた同レベルの葉を入れ替えてデータ番号が昇順に並ぶようにしています。 正規化によって得られたハフマン符号には強い規則性が見られます。最も符号長が短く、かつデータの一番若い葉は全てのビットが 0 になり、逆に符号長が最も長く、かつデータが最大の葉は全てのビットが 1 になります。符号長の等しい葉の符号は、データの若いものから順に 1 ずつ増えていき、符号長が 1 ビット長くなると、符号に 1 を加えた後で末尾に 0 を付加した形になっていることが上の例からもわかると思います。 この規則性を利用して、次のような手順で符号長からハフマン符号を再現させることができます。 各節の中で、葉の部分のみを符号長でソートする。符号長が等しい場合は、データ順に並べる。 ソート後の葉の配列から先頭の要素の符号長