実装してみました。 某プロジェクトに組み込んでやろうと思い、結構苦労して実装した割には LZH や ZIP に比べて圧縮率が期待したほど良くならなかったのが残念でした。 Adaptive Huffman や Lempel - Ziv などで、もっと改良しないと実用になりませんね．．． プログラムとソースはここからダウンロードできます。
プログラムの使い方は hc c inputfile outputfile で圧縮、 hc e inputfile outputfile で展開します。展開のとき inputfile に 圧縮されていないファイルを指定すると落ちますのでご注意ください。あと、 あまり小さなファイルを圧縮させないでください。こちらでは15バイトのファイル まで確認していますが、これくらいだと処理後の方が処理前よりも サイズが大きくなってしまいます。
以下はソースコードからの抜粋です。
/* [DEV NOTE] 15 bytes のファイルに、A〜Eの文字が次の個数だけあった場合、 符号化後のサイズはいくらになるか。 A = 5, B = 4, C = 3, D = 2, E = 1 Huffman木は次のようになる。 葉A 葉B 葉C 葉D 葉E [5] [4] [3] [2] [1] | | | | | | | | | 節 | | | | 0 +-- [3] --+ 1 | | | | | 節 | | 節 | 0 +-- [9] --+ 1 0 +----- [6] ----+ 1 | | | 根 | 0 +--------- [15] -------+ 1 Root から上に向かって左に分岐するときは 0、右に分岐するときは 1 のビットをとるように決めると、それぞれの文字は次のビット列で 一意に表現できる。 A: 00 (2-bit) B: 01 (2-bit) C: 10 (2-bit) D: 110 (3-bit) E: 111 (3-bit) 符号化後のサイズは、 5*2 + 4*2 + 3*2 + 2*3 + 1*3 = 33[bit] = 33/8[byte] 圧縮率は、 (33/8) / 15 = 33/120 = 0.275 → 27.5[%] ただし、符号化後のファイルには、複合化の際に Huffman 木を 復元できるように表を保存しておく必要があるので、 圧縮率はこれよりも悪くなる。 表のフォーマットは次のように決める。 + 0 --- raw data size [byte] (4-byte) + 4 --- total file length [bit] (4-byte) + 8 --- (# of characters used) - 1 (1-byte) + 9 --- character value (1-byte) +10 --- code bit length (2-byte) +12 --- code bit (?-byte) 符号化後の実際のファイルサイズは、 33 + 4*8 + 4*8 + 1*8 + (1+2)*8*5 + 5*8 = 265[bit] → (265+7)/8 = 34[byte] になる。 "BADACAABACBEBCD" --> 010011000100000010010011110110110 --> 32 02 C9 DB 00 [実装] 1. 根と葉は節の１種として考える → 同じ構造体を用いる。 2. 2*N-1 の要素からなる節配列を宣言する。 (葉の最大個数が N, 節(根含む)の最大個数が N-1 より) 3. それぞれの値の出現回数を数え、葉を作成する。 葉は配列の先頭から配置する。 4. 葉を出現回数の低い順にソートする。 5. 最初の２つの葉は出現回数が最も低い２つなので、 この２つの葉を束ねて節を作成する。節は葉の末尾の 次から配置する。 6. 配列の先頭 +2 から節の末尾までを出現回数の低い順にソートする。 7. 全ての葉を束ねるまで 5 と 6 を再帰的に繰り返す。 */
