gzip に並ぶ

圧縮器は動き、そして穴を残した。fixed Huffman は gzip -9 のおよそ 2 倍のサイズを出した。その 2 倍は 照合の非効率でも出力のバグでもない —— それこそが dynamic Huffman の存在理由のすべてだ。固定の符号表は 何にでも間に合うよう事前に選ばれた妥協で、dynamic な表は目の前のブロックに合わせられる。実際によく 現れるシンボルに短い符号を割り当て、独自の表を伝送する費用は節約で何倍にも取り戻される。穴を埋めるとは、 その表を構成する機構を純 Mere で組むことであり、そして言語には構成に必要なものがすべて揃っていた。

node pool から Huffman 木を

最適な prefix 符号を組むのは古典の Huffman アルゴリズムだ。各シンボルを頻度で重み付けした葉と見なし、 最も軽い二つの節点を取ってその和を重みとする新しい親の下にマージし、節点が一つ残ったとき、各葉の深さが その符号長になる。私は木を並列 vector として実装した —— 頻度・左の子・右の子・葉のシンボルを持つ node pool —— マージが内部節点を作るごとに伸ばし、まだマージ候補の節点を alive フラグで印す。毎回最も 軽い二つを見つけるのは線形走査だ。本番の encoder は heap を使うが、これは使わない。アルファベットが 小さいからだ —— 286 のリテラル／長さシンボル、30 の距離シンボル —— そして定数倍より明快さが大事 だった。完成した木の深さ優先の巡回が符号長を読み出し、シンボルが 0 個と 1 個の退化ケースは各々の 短絡を持つ。

符号を canonical にし、そして符号化を符号化する

符号長はまだ符号ではない。DEFLATE は canonical Huffman 符号を要求する。各シンボルに割り当てた長さだけ から、両者が同じ規則で実際のビット列を導く —— 各長さを共有する符号がいくつあるか数え、各長さの最初の 符号を計算し、シンボル順に配っていく。これは decoder が逆に回した導出と同じで、仕様から転写すると inflater がそのまま受理する符号が出た。decode 側に対応物のない部分は、符号長の表そのものをブロック ヘッダへ圧縮せねばならない点だ —— 繰り返しとゼロの連なりのための独自の三つの特殊シンボルを持つ小さな run-length の仕組みで、その頻度が二つ目の、より小さな Huffman 符号を駆動し、その長さがヘッダに最初に 入る。圧縮器が自分の符号表を圧縮するというこの再帰的な構造は、仕様では大仰に読めるが、部品を名指せば すっきり落ちる。

fallback と、数字

canonical 符号には硬い上限がある。DEFLATE は符号あたり最大 15 ビットしか割り当てず、病的に歪んだ 頻度分布はそれより長いものを生みうる。本番の encoder は再分配する長さ制限のパスを走らせる。これは より単純で正しい道を取り、符号が 15 ビットを超えるものがあるか確認し、あればブロックを非圧縮で出す —— stored ブロック、常に有効、だからどんな入力も誤った出力を生めない。現実的なデータでは上限に近づく ことはないが、典型的な入力でだけ正しい圧縮器は正しくない。fallback を据えて、数字はアークが狙って いたところに着いた。fixed Huffman が 114 バイトにした冗長な散文ファイルが 102 バイトになり、gzip -9 の 113 に対して。低冗長のファイルは fixed をはるかに下回り gzip をわずかに下回った。実 20 キロバイトの README は gzip -9 の 3 % 以内に入った。繰り返しの多い入力では encoder は今や参照ツールを明確に上回り、 すべてが依然 system の gunzip と言語自身の inflater をバイト単位で round-trip する。

アークはここで閉じる。三回前、gzip 形式を読める解凍器で始まり、それを書ける圧縮器へ広がり、同じ中核の 上に建つ本物の画像形式に届き、そして圧縮器がみなのベンチマークするツールと互角の出力を出すことで 終わる —— すべて純 Mere で、すべて system ユーティリティとバイト互換で、そして圧縮の作業そのものの ためには言語を一度も変えずに。成熟した言語がこう測ってどう見えるかといえば、実形式の積み重ねと互角の 圧縮器が、普通のプログラムとしてその言語で書け、コンパイラは一度も動かなくていい、ということだ。