画像圧縮アルゴリズム (4)ハフマン符号化 - 動的ハフマン圧縮

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