Matching gzip
The fixed-Huffman compressor left about a factor of two on the table against gzip -9, and closing that gap is what dynamic Huffman is for: instead of a code table both sides agree on in advance, fit a custom one to each block's actual symbol frequencies and transmit it. That means building a Huffman tree in pure Mere — a node pool, repeatedly merging the two least-frequent nodes, reading each leaf's depth as its code length — making the codes canonical, and then run-length encoding the table of code lengths itself into the block header, with a stored-block fallback for the rare input whose codes would exceed the format's fifteen-bit limit. The result is competitive with the reference tool: within a few percent on real text, and ahead of gzip -9 on repetitive inputs. The arc that began by reading a format ends by writing it as well as the tool everyone compares against.
The compressor worked and left a gap: fixed Huffman produced output about twice the size of
gzip -9. That factor of two is not inefficiency in the matching or a bug in the output — it
is the entire reason dynamic Huffman exists. A fixed code table is a compromise chosen in
advance to be adequate for anything; a dynamic one is fitted to the block in front of you,
short codes for the symbols that actually occur often, and the cost of transmitting the
custom table is repaid many times over by the savings. Closing the gap meant building, in
pure Mere, the machinery that constructs that table — and it turned out the language had
everything the construction needed.
A Huffman tree from a node pool
Building an optimal prefix code is the classic Huffman algorithm: treat each symbol as a leaf weighted by its frequency, repeatedly take the two lightest nodes and merge them under a new parent whose weight is their sum, and when one node remains, the depth of each leaf is its code length. I implemented the tree as parallel vectors — a node pool with frequency, left child, right child, and leaf symbol — growing it as merges create internal nodes, with an alive flag marking which nodes are still candidates for merging. Finding the two lightest each round is a linear scan; a production encoder uses a heap, and this one does not, because the alphabets are small — two hundred and eighty-six literal/length symbols, thirty distance symbols — and clarity mattered more than the constant factor. A depth-first walk of the finished tree reads out the code lengths, and the degenerate cases of zero and one distinct symbol get their own short-circuits.
Making the codes canonical, then encoding the encoding
Code lengths are not yet codes. DEFLATE requires canonical Huffman codes: given only the length assigned to each symbol, both sides derive the actual bit patterns by the same rule — counting how many codes share each length, computing the first code of each length, and handing them out in symbol order. This is the same derivation the decoder ran in reverse, and transcribing it from the specification produced codes the inflater accepted directly. The part with no counterpart on the decode side is that the table of code lengths must itself be compressed into the block header — a small run-length scheme with its own three special symbols for repeats and runs of zeros, whose frequencies drive a second, smaller Huffman code, whose lengths go into the header first. A compressor compressing its own code table is the kind of recursive structure that reads as baroque in the spec and falls out cleanly once the pieces are named.
A fallback, and the numbers
Canonical codes have a hard limit: DEFLATE allots at most fifteen bits per code, and a
pathologically skewed frequency distribution can produce a longer one. A production encoder
runs a length-limiting pass to redistribute; this one takes the simpler correct route of
checking whether any code exceeds fifteen bits and, if so, emitting the block uncompressed —
a stored block, always valid, so no input can produce wrong output. On realistic data the
limit is never approached, but a compressor that is correct only on typical inputs is not
correct. With the fallback in place, the numbers landed where the arc was aiming: a redundant
prose file that fixed Huffman took to a hundred and fourteen bytes went to a hundred and two,
against gzip -9’s hundred and thirteen; a low-redundancy file went well below fixed and a hair
under gzip; a real twenty-kilobyte README came within three percent of gzip -9. On repetitive
inputs the encoder now beats the reference tool outright, and everything still round-trips
through system gunzip and the language’s own inflater byte for byte.
The arc closes here. It began three parts ago with a decompressor that could read the gzip format, extended to a compressor that could write it, reached a real image format built on the same core, and ends with the compressor producing output competitive with the tool everyone benchmarks against — all in pure Mere, all byte-compatible with the system utilities, and all without a single change to the language for the compression work itself. What a mature language looks like, measured this way, is that a stack of real formats and a competitive compressor can be written in it as ordinary programs, and the compiler never has to move.