玄関コンピュータの部屋各種解説コーナーデータ圧縮法概説

3.4 ハフマン符号化と復号化の手順

ハフマン符号化の手順は以下のとおりです。

  1. 元データをスキャンして、全ての記号の種類と出現率を求める。
    符号化手順1
  2. 各記号に対する葉を作り、それぞれの葉に記号とその出現率を書いておく。
    符号化手順2
  3. 出現率の最も小さい2枚の葉について節点を1つ作り、その節点と2枚の葉を枝で結ぶ。 そして枝の一方には「0」、他方には「1」のラベルを付ける。
    符号化手順3
  4. この新しい節点に2枚の葉の出現率の和を書き、この節点を新たな葉と考える。
    符号化手順4
  5. 節点より下の枝と葉をないものと考え、3.と4.の手順を繰り返す。
    符号化手順5
  6. 葉(節点)が1枚になったところで符号の木が完成する。 このようにして構成した符号の木を「ハフマン木」と呼ぶ。
    符号化手順6
  7. ハフマン木によって構成された符号に基づき、元データを可変長符号に変換する。
    a→0 b→10 c→110 d→111

符号化されたデータの復号方法は、前節で説明しましたように符号化されたビット列にしたがってハフマン木を根からたどり、葉にたどり着いたところでその葉に対応する記号に逆変換します。 このためハフマン符号化では圧縮後のデータにハフマン木を追加保存しておく必要があり、そのぶんが圧縮後データのオーバーヘッドになります。

3.5 符号化の実例

例として、「aabbccccddddeeeeeeeeffff」という元データを前節の手順に従って符号化してみましょう。

  1. 元データをスキャンして全記号の種類と出現率を求め、対応する葉を作る。
    符号化実例1
  2. 出現率の最も小さい2枚の葉について節点を作り、出現率を合計する。
    符号化実例2
  3. 同手順の続き。
    符号化実例3
  4. 同手順の続き。
    符号化実例4
  5. 同手順の続き。
    符号化実例5
  6. 同手順の続き、ハフマン木完成。
    符号化実例6
  7. このハフマン木より構成されるハフマン符号。
    e:0 c:100 d:101 f:110 a:1110 b:1111
  8. 元データの符号化。
    111011101111111110010010010010110110110100000000110110110110
    aabbccccddddeeeeeeeeffff
    この時の圧縮率と平均符号長は次のようになります。
    圧縮率=60
    ───
    24×8
    60
    ──
    192
    =0.3125(31.25%)
    平均符号長=60
    ──
    24
    =2.5ビット

符号化されたビット列「111011101111111110010010010010110110110100000000110110110110」を復号するのは、6.で完成されたハフマン木を利用すれば比較的簡単ですので、説明は省略します。 一度、自分で実際に復号してみてください。(^_-)

3.6 ハフマン符号化の特徴