圧縮器を書く

解凍器は形式を読んだ。次の自然な問いは、言語がそれを書けるかだ。圧縮ストリームの読みと書きは 対称な作業ではない —— 復号は機械的で、選択の余地のない仕様に従うだけだが、符号化はあらゆる判断が 宿る場所だ —— けれど両者は形を共有している。inflater が分解したすべての構造を、deflater は組み立て 直さねばならない。同じブロック、同じ符号表、同じビット単位の詰め込み。解凍器のあとに圧縮器を書くのは、 新しい建築というより、すでに建っている何かの鏡像を建てる作業に近かった。

bit writer は bit reader の逆回し

inflater の中核は bit reader だった。バイトカーソルと小さなバッファを持ち、DEFLATE が詰める順序に 合わせてバイト境界を跨いで最下位ビットから配っていく。deflater にはその厳密な逆が要る —— 値と幅を 受け取り、同じ順序でそのビットを出力ストリームへ押し込み、8 ビット溜まるごとにバイトを flush し、 最後の一つはゼロで埋める bit writer だ。二つはあまりに互いの鏡像なので、二つ目を書くのは、一つ目を 読んで代入の向きをすべて反転させる作業がほとんどだった。名指しに値する唯一の非対称は、Huffman 符号は 最上位ビットから出さねばならないのに、extra ビットは最下位から出す点だ。だから writer は各符号を あらかじめ反転させる —— reader が逆向きに符号を消費していたために必要としなかった、あのビット反転だ。

greedy な照合

reader はストリームの中に見つけた後方参照にただ従えばよかったが、writer はそれを発明せねばならない。 これが圧縮器の本当の仕事だ。各位置で、window を後ろに辿ってここに繰り返される最長のバイト列を探し、 それが 3 バイト以上なら、リテラルの代わりに長さ／距離の組を出す。実装は素朴な window 走査だ —— 32 キロバイトの上限まで後ろへ歩き、各候補で照合長を測り、最長を残す。本物の圧縮器は再走査を避ける ために hash chain を使うが、これは使わない。素直な greedy 照合で、ネイティブでは十分速く、 インタプリタでは遅い。まさにこのトレードオフを、probe は隠すのでなく可視化すべきだ。照合した長さと 距離は、reader が復号に使ったのと同じ base + extra ビットの符号化表を、逆に回して通す。

fixed Huffman と、それが残す穴

最初の版は fixed-Huffman 表を使った —— 両者がすでに合意している仕様組み込みの符号長で、木について 何も伝送しなくていい。これは最も単純な正しい符号化器で、ちゃんと動く。冗長な 18 キロバイトの テキストファイルが 0.06 秒で 138 バイトに圧縮され、system の gunzip も前回の inflater も、一致する チェックサム付きでバイト単位に復元した。だが同じ入力に対し gzip -9 は 66 バイトを出した。この差は バグではない —— それこそが dynamic Huffman の存在意義で、固定の表を使う代わりに各ブロックの実際の シンボル頻度に合わせた符号表を作る。fixed Huffman に greedy 照合を足すとおよそ 2 倍の余地を残し、 その穴を正確に名指すこと —— 出力の欠陥ではなく符号化器の完成度の穴 —— が次の一歩を用意した。

そもそも圧縮器が書けたのは、必要なものがすべて別の理由で先に揃っていたからだ。bitwise 演算子、 バイナリ安全なファイル読み書き、以前の probe で作ったチェックサム。バイトから圧縮バイトへ、そして 戻すループを閉じるのに、言語へ新しく足すものは一つも要らなかった。符号化器はコンパイラを一行も 変えずにコンパイルが通り、有効な gzip を出した —— 解凍器と圧縮器、どちらも純 Mere で、system tool とも互いとも相互運用できる。残った穴は圧縮率についてであって正しさではなく、そしてそれは埋め方を 知っている穴だった。