*目次 [#j7e5b518]
#contents
*圧縮後のバイナリコードの設計 [#z6af1f91]
例えば、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|
**固定長を採用した場合 [#ua448d06]
a〜fを上記の表のように3ビットの固定長のバイナリコードに対応させたとする。この方式を採用したとき、ファイル全体として300,000ビットになる。
**可変長を採用した場合 [#k586c9b3]
101は4ビットのバイナリコードに対応されるが、最も頻出頻度が高い0は1ビットのバイナリなりコードに対応される。バイナリ変換後の総文字コード数は次のように計算できる。
&mimetex("(45 \times 1 + 13 \times 3 + 12 \times 3 + 16 \times 3 + 9 \times 4 + 5 \times 4 ) \cdot 1,000 = 224,000 [bit]");
固定長時は300,000ビットであったが、可変長時は224,000ビットになった。よって、圧縮率は約0.75（＝224,000/300,000）になる。つまり、25%分だけ圧縮できたことを意味する。
*ハフマン符号 [#b2580aa0]
可変長を採用した場合のバイナリコードは''ハフマン符号（Huffman code）''と呼ばれたものがある。
ハフマン木を用いて最も効率的なバイナリコードが割り当てられる。割り当て用のバイナリコードの作成手順は次の通りである。
+各記号を生起確率の降順に並べる。ただし、同じ生起確率を持つ記号はどちらが先でも構わない。
+生起確率の最も小さい記号とその次に小さい記号を葉として、新たな節点を設ける。その節点にそれら2つの記号の生起確率の合計を与える。その節点から生起確率が小さい記号に向かう枝に1というラベルを、もう片方の枝に0というラベルを与える。
+ステップ2で作成した節点を新たな記号と見なして、新たに節点を作ることができなくなるまでステップ2を繰り返す。
+最上位の節点（根）から各記号に至る各枝に与えられたラベルの系列が、その記号のハフマン記号である。
例1：記号列aaaabbc（aが4文字、bが2文字、cが1文字）に対するハフマン木は次のようになる。
#img(http://security2600.sakura.ne.jp/main2/image3/huffman1.jpg)
#img(,clear)
このハフマン木から、各アルファベットのハフマン符号を導ける（上から枝のラベルを見ていけばよい）。
-aのハフマン符号：0
-bのハフマン符号：10
-cのハフマン符号：11
また、各アルファベットの生起確率は次のようになる。
-aの生起確率：P(a)=4/7
-bの生起確率：P(b)=2/7
-cの生起確率：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を作らなければならない。
#img(http://security2600.sakura.ne.jp/main2/image3/huffman2.jpg)
#img(,clear)
-xのハフマン符号：101
-yのハフマン符号：100
-zのハフマン符号：11
-uのハフマン符号：01
-vのハフマン符号：00
[補講]可変長のバイナリコードの場合は、ハフマン木が採用される。一方、固定長のバイナリコードの場合は、[[完全2分木]]が採用される。だから、各アルファベットのバイナリコードは同じビット長を持つわけである。
もし、例1のabcという文字列をまとめて圧縮したときのバイナリコード列は、01011（＝0・10・11）になる。このように変換することが''エンコード''である。一方、符合化された記号列を元の記号列に戻すことを''デコード（復号）''という。静的ハフマン符号の手法では、復号のために記号と符号の対応表が必要である。
**ハフマンアルゴリズム（Huffman's algorithm） [#u0fea6fd]
各記号を次のように定義する。
-C
--n個の文字の集合
-c
--Cの要素（c∈C）。即ち、Cに含まれる文字のこと。
-f(c)
--cの頻出頻度、即ちcの生起確率
-Q
--[[優先待ち行列]]（priority queue）
---優先度の大きいものから要素を取りだす仕組みになっているデータ構造。
ハフマン木を生成するハフマンアルゴリズムの主要関数Huffman(C)は次のように構成される。
#code(pascal){{
n←|C|
Q←C
for i←1 to n-1
z←Allocate-Node()
left[z]←Extract-Min(Q)
x←left[z]
right[z]←Extract-Min(Q)
y←right[z]
f[z]←f[x]+f[y]
Insert(Q,z)
return Extract-Min(Q)
}}
2行目で、Cに含まれる文字たちをQにセットする。~
for文で最小値と2番目に小さい値をQから取り出して、それぞれをx,yにセットする。そして、x,yの生起確率の和をzの生起確率としてセットする（zはあらかじめノードとして定義しておいた）。そのzをQに挿入する。これをn-1回繰り返す。~
最終的にハフマン木の根を返している。
最後に計算量を分析する。~
2行目のQの初期化において、QはバイナリヒープなのでBuild-Heapアルゴリズムを実行する。よって、&mimetex("O(n)");回になる。~
forループの中の各ヒープの操作に&mimetex("O(\log n)");回必要なので、forループ全体で見るとこれを|n|-1回繰り返す。よって、&mimetex("n \log n");回になる。~
総合すると、n個の文字の集合Cを処理するためには&mimetex("n \log n");回必要である。
***ハフマンアルゴリズムの完全性（correctness） [#g12e2c11]
[補題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より、成り立つ。 □
*ハフマン符号における圧縮率 [#dd7639a8]
圧縮率の定義から、ハフマン符号における圧縮率の公式を作ることができる。このとき、記号と符号の対応表の存在を忘れてはいけない。
（圧縮率）＝｛（ハフマン符号化された記号列のビット長）＋（記号と符号の対応表のビット数）｝/（原記号列のビット数）
なお、「記号と符号の対応表のビット数」の長さは、記号をM種類とすると、約&mimetex("M \log_2 M +2M");ビットになる。
*参考文献 [#kb01394f]
-『INTRODUCTION TO ALGORITHMS』
-『ソフトウェア開発技術者 大滝みや子先生のアルゴリズム教科書』
-『ソフトウェア開発技術者試験対策 コンピュータサイエンス補足資料＋午後演習問題』
