デビット・ハフマンによって開発された符号で、データの可逆圧縮に利用されます。出現頻度の高いデータに短いビット列を、逆に出現頻度の低いデータに長いビット列を割り当てることで、データ全体でのデータ量の削減を実現します。ハフマン符号のアルゴリズムは古典的(代表的)な圧縮アルゴリズムであり、ZIPやJPEGといった圧縮フォーマットでも利用されています。ハフマン符号でデータの符号化(圧縮)を行う場合、出現頻度を知るために全データを一度調べてから、符号の割当を行う必要があります。その後全データを先頭から対応する符号に置き換えていくことになるので、計2回のデータ走査が必要になります。このデータを2回走査し、静的な符号に変換するアルゴリズムを、静的ハフマン符号といいます。このページで「ハフマン符号」として紹介するのはこのアルゴリズムです。上記の2回データを走査する方法は、データサイズが大きくなると処理効率の面で問題が生じる可能性があります。ハフマン符号は可変長符号です。固定長符号として扱われます。通常のASCIIコードでは5文字のデータは以下のように符号化されます。全256文字表現できます。この文字列に限って言えば、出現する文字種類はたった5種類です。あれば全データを表現することができます。以下の表のようにです。101この時点でいくらかのデータ圧縮がなされていますが、そもそも出現する文字種類にも出現頻度(回数)に偏りがあることが分かります。したがって、よく出現するデータにより短いビット列を、あまり出現しないデータには逆に長いビット列を割り当てることでさらにデータ量圧縮を図ります。1この割り当てた符号をハフマン符号といいます。符号を割り当てています。29bitとなり、固定長での割り当て(45bit)よりさらに圧縮されていることが確認できます。ハフマン符号は、元の符号より必ず短くかつ常に最適(最短)の割り当てがなされることが証明されています。接頭符号ハフマン符号は接頭符号呼ばれる符号です。接頭符号は任意の符号が、ほかの符号の接頭部にならないような符号のことです。接頭部分に当てはまるので接頭符号とは言えません。上で示したハフマン符号の表を確認してもらえると、どの文字に対応する符号も、他の符号の接頭部分に対応していないことが分かります。瞬時復号可能という2つの性質を与えてくれます。一意複合可能とは、ある圧縮されたデータを複合する際に複合結果が一意に定まるということです。なるか一意に決めることができません。符号化に一意複合可能なことは必須の要件です。瞬時復号可能とは、ある圧縮されたデータがビット列として与えられた場合に、各符号の最後のビットが読み込まれた時点でその符号を確定できるというような性質です。ビット列を最後まで読まなくても先頭から順に復号していくことができるという意味で、瞬時復号可能といいます。瞬時復号可能ではない符号では、複合処理が複雑になり効率性に影響してしまいます。符号化アルゴリズムハフマン木と符号化ハフマン符号を得るためには、ハフマン木という2分木を作成する必要があります。生成したハフマン木をたどることで符号化を行います。ハフマン木のノードを保持するリスト(Q)を生成します。データ種類と出現回数を持つ葉ノードを生成し、リスト(Q)に追加します。節ノード(N)を生成しQに追加します。Qから最小の出現回数を持つノード(R)を取り出します。Qから最小の出現回数を持つノード(L)を取り出します。Nの左の子ノードにLを、Nの右の子ノードをにRを、出現回数に左右の子ノードの持つ出現回数の和を設定します。手順をQの個数が1になるまで繰り返します。Qに残ったノードがハフマン木のルートノードになります。ハフマン木のノードが子ノードを保つ場合、必ず左右に子ノードを持ちます。ルートノードのみで子ノードを持たないのは許されません。したがって、データが1種類のみしか出現しない場合には別で制御しなければなりません。ダミーのルートノードを用意し、その左右の子ノードにルートをもたせておけばよいでしょう。リスト(Q)は最小値が取り出せればよい(ソートされてなくてもよい)ので、2分ヒープを使うと効率的です。ファイルの圧縮を行う場合、ファイルのデータをバイト単位で出現回数を調べますが、わかりやすくここでは文字列の符号化を考えます。単位なので同じように考えられます。符号化を行うと以下のようなハフマンツリーが得られます。ハフマン木からそれぞれのデータに対応する符号を得るのは簡単です。とることで、対応する符号が得られます。それぞれ符号が割り振られるといった仕組みです。重要なハフマン符号のアルゴリズムは以上です。実際にファイルをこのアルゴリズムのみで圧縮・復号するには、更に以下事項も考えなければなりません。ハフマン木自体の符号化ここまでの手順でわかるのは、圧縮データを復号する際にもハフマン木が必要になります。圧縮データには、圧縮に使用したハフマン木自体の情報も入れなければ行けません。圧縮されたデータということになります。ハフマン木の作成にはデータの種類と出現頻度(回数)を必要とします。したがってそれらすべてを記録保持しておく方法が考えられます。それよりも単純に木構造自体をビット列化してしまう方が、短いデータ量で表現できるので、その方法をまとめます。ハフマン木自体をビット列化するのは、手順としては以下のように行います。ハフマン木を深さ優先で探索します。(左の子ノード優先)探索しているノードが節ノードの場合、0を出力します。探索しているノードが葉ノードの場合、1を出力し、対象データ8bitを出力します。Zには対応するデータ8bit分が出力されると考えてください。ちなみにこの手法で生成されるデータは可変長ですが、瞬時復号可能なので問題ありません。右の子ノードが葉ノードのタイミングでハフマン木の再構成が完了します。圧縮データの構成ハフマン符号は可変長符号のため、復号の際に何byte分出力して完了なのかを知っておく必要があります。したがって元データのファイルサイズもデータの先頭に保持することにします。符号化されたデータとします。ハフマン木も符号化されたデータも可変長のデータです。圧縮率についての細かい数学的な話はしませんが、圧縮率はデータの偏り具合によってはうまく圧縮できません。完全にランダムなデータ(すべてのデータ出現回数が等しいなど)については、全く圧縮できなかったりします。サンプルコード圧縮はそれなりの速度でできますが、復号が結構時間がかかります。環境にもよるのですが、うまく高速化できる方法があれば誰か教えてください。ファイルだけでなく、ASCII文字列データの圧縮もできるようにしてます。Haffmanクラスを生成し、Encode(Decode)メソッドにファイル名を渡します。文字列で試す場合は、DebugStringメソッドに文字列を渡します。