100,000文字のデータファイルを圧縮したいとする。このとき、a〜fの各アルファベットの頻出回数は次のようになったとする。5各アルファベットのバイナリコードとして、固定長のバイナリコードに変換するのが自然な方法である。頻出回数が多いアルファベットに対して、短いバイナリコードをうまく対応させれば、バイナリ変換後の総文字コード数は固定長の場合に比べて少なくなる。圧縮できているとことである。†a〜fを上記の表のように3ビットの固定長のバイナリコードに対応させたとする。この方式を採用したとき、ファイル全体として300,000ビットになる。†101は4ビットのバイナリコードに対応されるが、最も頻出頻度が高い0は1ビットのバイナリなりコードに対応される。バイナリ変換後の総文字コード数は次のように計算できる。固定長時は300,000ビットであったが、可変長時は224,000ビットになった。よって、圧縮率は約0.75(=224,000/300,000)になる。25%分だけ圧縮できたことを意味する。code)と呼ばれたものがある。ハフマン木を用いて最も効率的なバイナリコードが割り当てられる。割り当て用のバイナリコードの作成手順は次の通りである。各記号を生起確率の降順に並べる。同じ生起確率を持つ記号はどちらが先でも構わない。生起確率の最も小さい記号とその次に小さい記号を葉として、新たな節点を設ける。その節点にそれら2つの記号の生起確率の合計を与える。その節点から生起確率が小さい記号に向かう枝に1というラベルを、もう片方の枝に0というラベルを与える。ステップ2で作成した節点を新たな記号と見なして、新たに節点を作ることができなくなるまでステップ2を繰り返す。最上位の節点(根)から各記号に至る各枝に与えられたラベルの系列が、その記号のハフマン記号である。例1:記号列aaaabbc(aが4文字、bが2文字、cが1文字)に対するハフマン木は次のようになる。このハフマン木から、各アルファベットのハフマン符号を導ける(上から枝のラベルを見ていけばよい)。aのハフマン符号:0bのハフマン符号:10cのハフマン符号:11また、各アルファベットの生起確率は次のようになる。aの生起確率:P(a)=4/7bの生起確率:P(b)=2/7cの生起確率:P(c)=1/7ハフマン符号と生起確率を比較すると、生起確率の高いaには短いバイナリコードである0が割り当てられたことが確認できるはずだ。例2:記号列xyyyyzzzzuuuuuvvvvvv(xが1文字、y,zが4文字、uが5文字、vが6文字)に対するハフマン木は次のようになる。葉から節を作るときは、最小のものと2番目に小さいものから作ることに注意。よって、9/20を作った次は、6/20と5/20から11/20を作らなければならない。xのハフマン符号:101yのハフマン符号:100zのハフマン符号:11uのハフマン符号:01vのハフマン符号:00[補講]可変長のバイナリコードの場合は、ハフマン木が採用される。固定長のバイナリコードの場合は、完全2分木が採用される。各アルファベットのバイナリコードは同じビット長を持つわけである。例1のabcという文字列をまとめて圧縮したときのバイナリコード列は、01011(=0・10・11)になる。このように変換することがエンコードである。符合化された記号列を元の記号列に戻すことをデコード(復号)という。静的ハフマン符号の手法では、復号のために記号と符号の対応表が必要である。各記号を次のように定義する。Cn個の文字の集合cCの要素(c∈C)。Cに含まれる文字のこと。queue)優先度の大きいものから要素を取りだす仕組みになっているデータ構造。ハフマン木を生成するハフマンアルゴリズムの主要関数Huffman(C)は次のように構成される。Extract-Min(Q)2行目で、Cに含まれる文字たちをQにセットする。for文で最小値と2番目に小さい値をQから取り出して、それぞれをx,yにセットする。x,yの生起確率の和をzの生起確率としてセットする(zはあらかじめノードとして定義しておいた)。そのzをQに挿入する。これをn-1回繰り返す。最終的にハフマン木の根を返している。最後に計算量を分析する。2行目のQの初期化において、QはバイナリヒープなのでBuild-Heapアルゴリズムを実行する。回必要なので、forループ全体で見るとこれを|n|-1回繰り返す。