さて、固定方式のハフマン圧縮ができあがった。
文字/長さと距離の情報を固定ハフマンコードで圧縮するのだが、これまでに作ってきた伸長プログラムを逆にプログラムすればよいので、いくぶん気楽な面がある。但し、圧縮でバグがあると伸長できないファイルになるため注意が必要。
前回は過去に出てきた文字列を[Position/Length]で置き換えて表示するプログラムだったが、文字数は逆に増えているような状態だった。今回はハフマン圧縮で改良して現実的な圧縮の効果がでるようにしたいと思う。フロントパネルは下のような具合だ。
このサブVIはループの中に入れて、シフトレジスターに接続して使用する。outという名前のクラスターのcompressed dataという配列に圧縮後のデータを保存する。ハッシュを使った検索で過去に出てきた文字列の場合はLengthとDistanceを見つけこのサブVIに出力する。過去に使われていなかった場合は文字alphabetをそのままこのサブVIに出力する。固定ハフマンコードはループの外で一度だけ作成しこのサブVIに出力する。
このダイアグラムは見覚えがあるかもしれないが、前回作成したVIをもとにハフマン圧縮に改造した。ハッシュテーブルは速度的にも有利だった２次元配列を使うことにした。左上の固定ハフマンコードは伸長プログラムの時に作ったものをそのまま使っている。
ブロックヘッダーはとりあえず最終ブロックを示す１（BFINAL）、固定ハフマンコードを示す０１（BTYPE）を出力するようにしている。ZIPではビット単位で操作するためビットの並べ方について注意しておかなければならないので仕様の一部を書き出してみよう。
<<<<<<<< 仕様の一部開始>>>>>>>>>>>>>
*データ要素のバイトへのパッキングは、バイトの中でビット番号が大きくなる方向に行う。すなわち、バイトの最下位ビットからスタートする。
*ハフマンコード以外のデータ要素は、データ要素の最下位ビットから詰める。
*ハフマンコードはコードの最上位ビットから詰める。
<<<<<<<< 仕様の一部終了>>>>>>>>>>>>>
これに従うとビット０から１１０の順番で詰めていくことになる。
このように詰めたビット配列からバイトに変換するために、putBits.viを作成した。このVIではクラスターのビット配列（bit array in）の大きさが８以上になったときに下位から８個のビットを取り出してバイト値に変換して同じくラスターのデータ配列（data）に付け加える。コードによっては８ビット以上の要素が出力されるので残りがビット未満になるようにホワイルループに入れて繰り返し処理を行っている。
putBits.viのおかげでエンコード部分は単にビット列を出力すれば良い。固定ハフマン圧縮のVIは次のダイアグラムとなっている。
過去の文字列に同じものが見つからなかったときNotLiteralはFalseとなる。その場合にはその文字コード0-255の数値がAlphabet(U8)に入ってくるため、それに対応するハフマンコードを取り出して必要なビット長分を切り取って出力する。ここで、ハフマンコードは先頭から詰めるという規則を適用させてビット配列の反転を行っている。
過去の文字列に同じものが見つかったときNotLiteralはTrueとなる。その場合、長さはハフマンコードと追加ビット、距離は固定長の距離コードと追加ビットになるため、それらをまとめてビット配列に出力する。
長さと距離はコードと追加ビットで指定される。例えば距離が13から16はコード7と2ビットの追加ビットで表現される。コードの始めの数値（CodeBaseと名付けた）の配列と、そのコードの追加ビット長の配列をもとに、コード化するのだが、長さと距離ではCodeBase配列とExtraBit配列の数値が異なるので、共通で使えるLengthDistCoder.viを作った。CodeはThreshold 1D array.viで見つけることができる。追加ビットはベースとの差をビット配列に直し必要なビット数のみを出力している。
これをサブVIとして長さと距離それぞれのハフマンコードと追加ビットを得ている。長さコードは257から始まるのでその分オフセットが必要だ。
さて、圧縮性能だが、14086字の英文が7921字に圧縮されていたので圧縮率は43%だ。動作時間はタンジェリン色のiBookで2.23秒だったから用途によっては使い物になるかもしれない。コード化に1.14秒かかっている。圧縮率を上げるにはダイナミックハフマンコードを使うのがよさそうだが、それは後の楽しみに取っておこう。
次回はZIPで読めるようにファイルヘッダーを作ってみよう。読むときには無視していたチェックサムも他のソフトで読んでもらうためには必要かもしれない。