例えば、100,000文字のデータファイルを圧縮したいとする。このとき、a〜fの各アルファベットの頻出回数は次のようになったとする。
a | b | c | d | e | f | |
回数(千単位) | 45 | 13 | 12 | 16 | 9 | 5 |
各アルファベットのバイナリコードとして、固定長のバイナリコードに変換するのが自然な方法である。一方、頻出回数が多いアルファベットに対して、短いバイナリコードをうまく対応させれば、バイナリ変換後の総文字コード数は固定長の場合に比べて少なくなる。つまり、圧縮できているとことである。
a | b | c | d | e | f | |
固定長のバイナリコード | 000 | 001 | 010 | 011 | 100 | 101 |
可変長のバイナリコード | 0 | 101 | 100 | 111 | 1101 | 1100 |
a〜fを上記の表のように3ビットの固定長のバイナリコードに対応させたとする。この方式を採用したとき、ファイル全体として300,000ビットになる。
101は4ビットのバイナリコードに対応されるが、最も頻出頻度が高い0は1ビットのバイナリなりコードに対応される。バイナリ変換後の総文字コード数は次のように計算できる。
固定長時は300,000ビットであったが、可変長時は224,000ビットになった。よって、圧縮率は約0.75(=224,000/300,000)になる。つまり、25%分だけ圧縮できたことを意味する。
可変長を採用した場合のバイナリコードはハフマン符号(Huffman code)と呼ばれたものがある。
ハフマン木を用いて最も効率的なバイナリコードが割り当てられる。割り当て用のバイナリコードの作成手順は次の通りである。
例1:記号列aaaabbc(aが4文字、bが2文字、cが1文字)に対するハフマン木は次のようになる。
このハフマン木から、各アルファベットのハフマン符号を導ける(上から枝のラベルを見ていけばよい)。
また、各アルファベットの生起確率は次のようになる。
ハフマン符号と生起確率を比較すると、生起確率の高いaには短いバイナリコードである0が割り当てられたことが確認できるはずだ。
例2:記号列xyyyyzzzzuuuuuvvvvvv(xが1文字、y,zが4文字、uが5文字、vが6文字)に対するハフマン木は次のようになる。葉から節を作るときは、最小のものと2番目に小さいものから作ることに注意。よって、9/20を作った次は、6/20と5/20から11/20を作らなければならない。
[補講]可変長のバイナリコードの場合は、ハフマン木が採用される。一方、固定長のバイナリコードの場合は、完全2分木が採用される。だから、各アルファベットのバイナリコードは同じビット長を持つわけである。
もし、例1のabcという文字列をまとめて圧縮したときのバイナリコード列は、01011(=0・10・11)になる。このように変換することがエンコードである。一方、符合化された記号列を元の記号列に戻すことをデコード(復号)という。静的ハフマン符号の手法では、復号のために記号と符号の対応表が必要である。
各記号を次のように定義する。
ハフマン木を生成するハフマンアルゴリズムの主要関数Huffman(C)は次のように構成される。
1 2 3 4 5 6 7 8 9 10 11 |
|
2行目で、Cに含まれる文字たちをQにセットする。
for文で最小値と2番目に小さい値をQから取り出して、それぞれをx,yにセットする。そして、x,yの生起確率の和をzの生起確率としてセットする(zはあらかじめノードとして定義しておいた)。そのzをQに挿入する。これをn-1回繰り返す。
最終的にハフマン木の根を返している。
最後に計算量を分析する。
2行目のQの初期化において、QはバイナリヒープなのでBuild-Heapアルゴリズムを実行する。よって、回になる。
forループの中の各ヒープの操作に回必要なので、forループ全体で見るとこれを|n|-1回繰り返す。よって、
回になる。
総合すると、n個の文字の集合Cを処理するためには回必要である。
[補題1]
Cの中で頻度回数が1番目・2番目に小さいものをそれぞれx,yとする。
このとき、「同じビット長かつ最後のビットだけが異なる」ようなx,yのcodewordを含むoptimal prefix codeが存在する。
[補講2]
Tを、C上のoptimal prefix codeを表す完全2部木とする。また、f[c]をc∈Cの頻度回数とする。
Tの兄弟葉である2つのx,y、x,yの親としてzを考える。
このとき、f[z]=f[x]+f[y]の頻度回数を持つ文字としてzを考えると、木T'=T-{x,y}はC'=C-{x,y}∪{z}のoptimal prefix codeを示す。
[定理]
Huffmanはoptima prefix codeを生成する。
[証明]補題1と2より、成り立つ。 □
圧縮率の定義から、ハフマン符号における圧縮率の公式を作ることができる。このとき、記号と符号の対応表の存在を忘れてはいけない。
(圧縮率)={(ハフマン符号化された記号列のビット長)+(記号と符号の対応表のビット数)}/(原記号列のビット数)
なお、「記号と符号の対応表のビット数」の長さは、記号をM種類とすると、約ビットになる。