How file compression actually works today (and how I beat zlib by 2.86% with graph theory)

Every file compressed today, a .zip, a .png image, an HTTP response with gzip, almost always runs on the same 35-year-old algorithm: DEFLATE, the one zlib implements. I wanted to actually understand how it works underneath, so I did what I know how to do: translate it from C to Rust with c2rust, prove the translation doesn’t change a single bit, then see if I could improve it. It turned out I could. 2.86% smaller than zlib at its highest compression level, verified byte for byte against the original C implementation. Along the way, by measuring and not reading, it became clear where the real limit of lossless compression sits and why that limit can’t be cheated.

The family of algorithms that compresses almost everything today

Before touching any code, a quick map of what uses what:

• LZ77 + Huffman (DEFLATE, the engine behind zip/gzip/PNG): looks for recent repeats (“this already appeared 200 bytes back, copy it”) and then encodes what’s left with variable-length codes, shorter for the most frequent symbols. Fast, old, universal.
• LZMA (the one behind 7-Zip and .xz): the same idea of repeats, but with an arithmetic range coder instead of Huffman, and a much larger history window. Compresses more, runs slower.
• BWT (the one behind bzip2): reorders each block (100 KB to 900 KB, configurable) so bytes with the same context end up together, turning a scattered repeat into a long run that’s easy to compress.
• PPM (also an option in 7-Zip): predicts the next byte by looking at the N previous ones, with a probability table that adapts on the fly.
• Context mixing (cmix, paq8px, the top entries in the serious rankings): instead of one model, runs dozens in parallel and combines them with weights learned bit by bit. This is what leads the Hutter Prize and the Large Text Compression Benchmark today, and it’s expensive (sometimes under 10 KB/s).

All of them, without exception, run into the same limit: no lossless compressor can shrink every possible file of a given size, however clever it is. This can be proven by counting, not guessing: if there are 1,024 possible 10-bit files and the compressor is reversible (it has to recover the original), it has to give each one a distinct output. There’s no way to fit 1,024 inputs into fewer than 1,024 distinct outputs, so on average the output can’t be shorter than the input. That’s the counting (pigeonhole) argument, and it’s the intuitive version of what Shannon formalized for a source with a given probability distribution: there’s a limit to how much you can shrink things on average, even though a particular file, if it has a lot of structure, really can compress far below its size. The only thing a better algorithm can do is get closer to that average, by finding structure a simpler one misses.

The experiment: translate zlib and prove nothing broke

I took zlib 1.3.1’s official source (the same one half the internet uses) and ran it through c2rust, a mechanical C-to-Rust translator. The translation comes out ugly: raw pointers, manual arithmetic, zero Rust type safety. But it compiles and runs.

Before touching a single line, I needed to prove the translation didn’t change behavior. I built a harness that compiles the original C zlib alongside it and compares: compress with the translated version, decompress with the real C, does it give back the exact original file? Compress with the real C, decompress with the translated one, same question? And the strictest check: are the compressed bytes identical, not just “both work”?

I ran this against more than 15,000 generated inputs (random, repetitive, with short patterns, with already-compressed data) and against the standard compression corpora: the 11 files of the Canterbury corpus and 18 from the Calgary corpus (the 14 its official site maintains today, plus paper3–paper6, four files the collection used in earlier evaluations), at several of zlib’s compression levels (of the 10 that exist, 0 to 9). Bit-exact in 100% of the cases tested. In everything I ran, the mechanical translation didn’t change behavior by a single bit.

The automatic translation didn’t come out perfect on the first try. Four real stumbles, among the most instructive:

• A cleanup script that deleted entire files. To strip the nightly feature attributes c2rust adds (#![feature(extern_types)] and similar), I first used a sed command that deleted from the start of the file to the first match of the pattern. In files that didn’t have that attribute, the pattern never appeared and the deletion range ate the whole file. I replaced it with a Python script that tracks bracket depth across multi-line #![...] attributes.
• A memcpy with the wrong pointer type. In the translated CRC32, one call passed a *const u8 where the signature expected *const c_void; c2rust doesn’t add that cast automatically. One line of manual cast, documented as the only real intervention in that file.
• PPMd7 crashing with SIGABRT from memory corruption. The CPpmd7Head struct, hand-translated for lack of a direct Rust equivalent, reserved only 4 KB of trailing padding when the real one needs close to 20 KB for its lookup tables. Bumping the buffer to 64 KB fixed it.
• Nested C repositories, without noticing. I cloned zlib and xz without deleting their inner .git before adding them to the experiment’s repository, so Git recorded them as broken references (gitlinks) instead of real files. Fixed by deleting the nested .git and re-adding the content.

Where zlib leaves money on the table

With the base translated and tested, I went to look at how zlib decides what to compress. Here’s the interesting part.

DEFLATE bundles two decisions into every byte: write it as-is (a “literal”), or say “this already appeared, copy it from there” (a “match”)? A match is encoded as a backward distance plus a length to copy, always looking at a window of recent history (up to 32 KiB).

That decision, made byte by byte across the entire file, is literally a shortest path in a directed graph problem: every file position is a node, every possible match from there is an edge with a cost in bits, and a literal is the default edge to the next node.

zlib never solves this exactly. Its algorithm (deflate_slow, the one used at high levels) is greedy with one symbol of lookahead: it looks at the current match, looks one more step ahead, and decides from that. It never looks further. It’s fast, and for most data it works reasonably well. But it isn’t optimal.

I replaced that heuristic with dynamic programming: for a fixed cost table (the current Huffman tree), compute the minimum cost to reach the end of the file from every position, working backward, so that by the time I reach a position I already know the real cost of every decision I can make there. It’s exact for that particular cost table, not a global optimum over the whole stream (that would also mean picking the ideal Huffman tree at the same time, a considerably more expensive problem); the next section covers how iterating gets closer to that. It’s the same algorithm that solves shortest paths on a map, applied to compression decisions.

The Huffman tree can also be improved on the fly

It doesn’t stop there. DEFLATE doesn’t just choose what to copy; it also builds a Huffman tree per block, giving shorter codes to the most frequent symbols.

The problem is circular: the optimal parse depends on knowing how much each symbol costs, and that depends on the tree. But the tree depends on which symbols the parse chose.

The fix is to iterate: parse with an approximate cost, count which symbols were actually used, build a real tree from those frequencies, recompute the exact costs under that tree, reparse with the improved cost, and repeat until it stops improving.

Along the way I found a real bug: my first version of the clamp for Huffman codes that came out too long (over 15 bits, the format’s maximum) left the tree incomplete: the Kraft sum (the inequality any variable-length code table has to satisfy to be decodable) came out below 1 instead of exactly 1. A code with Kraft under 1 isn’t necessarily ambiguous in the abstract, but the DEFLATE format requires a complete one, and zlib rejects the table while building its decode tables (Z_DATA_ERROR), not partway through reading some symbol. Only large, varied files triggered it (768 KB of varied English text reaches 18-bit-deep trees before clamping); the small files in the test corpus never activated it, so it went unnoticed until I ran the full corpus. It’s fixed by checking that the Kraft sum equals exactly 1, not less, shortening the longest code whenever there’s margin to spare.

Splitting the file into blocks, each with its own tree

A single Huffman tree for an entire file is a compromise: if the first pages of a book use different words than the last ones, one tree doesn’t fit either part well. The fix, which Google’s zopfli tool has used for years, is to split the file into several DEFLATE blocks, each with a tree fitted to that section.

I implemented a recursive splitter: it tries candidate cut points, computes the exact cost of treating the range as one block versus two with separate trees, and only splits if the gain pays for the second tree’s cost (a new tree’s header isn’t free).

The result, measured and verified

Across those 29 files (6,062,277 bytes total), the final result is 2.86% smaller than zlib at its highest compression level. The best case, a binary spreadsheet, improves by 11.5%. The only two that get worse are the same binary image repeated across both corpora, and only by 0.5%.

All 29 files decode exactly with the original C zlib. None of this is worth anything if the compressed file doesn’t turn back into the exact original, byte for byte.

Calibrating expectations: this isn’t a discovery

Here’s the honest part that usually isn’t in “I beat algorithm X” posts. What I did is, in essence, a replica of what Google’s zopfli already does, which typically gets between 3% and 8% against zlib because it has a more thorough match finder and years of fine-tuning. My 2.86% lands at the low end of that range. I didn’t invent anything new; I built, measured and verified a technique that already existed, and the number that came out is consistent with what the literature already knew.

A separate experiment, more interesting for understanding the real limit: I tested whether a version of the same trick works on LZMA, the 7-Zip algorithm. Specifically, what I tried was hand-changing the arithmetic coder’s starting probabilities using statistics from a previous pass, instead of the fixed neutral value it always starts at. It doesn’t work: the file comes out unreadable for any standard decoder, because the format never transmits that state in the compressed file — encoder and decoder rebuild it independently, in parallel, byte by byte, and they have to start out identically or lose sync. That doesn’t mean no adjustment is possible in an adaptive coder: Zstandard, for example, does implement a real two-pass strategy that collects statistics for the next pass, without touching how its probabilities start out. What is scoped to this one case is the specific technique I used for DEFLATE (adjusting the initial state from the outside): that doesn’t transfer to a format that never transmits it.

I also tested LZMA’s most obvious knob (the EXTREME preset, which raises the accepted match length and search depth) against normal preset 9: -0.084% aggregate, with one file even getting 5.6% worse. And in bzip2 I tested raising the rounds of the EM loop that builds its alternate Huffman tables from 4 (the fixed value since 1999) to 50: -0.047% aggregate. Neither has the easy margin DEFLATE had; bzip2 because its multi-table selection has already been doing something like the block splitting DEFLATE was missing, for 25 years, and LZMA because its compact format leaves no room to declare any per-file adjustment.

What this teaches about compressing data, in general

Three ideas worth more than the final number:

1. Shannon entropy is a floor, not a technical challenge. No algorithm, however clever, compresses below the real information content of the data without losing something. The only thing that can improve is how close to that limit you get, and that depends on how well the model understands the data’s structure.
2. Fast heuristics (greedy) leave money on the table, usually not much. zlib uses a 30-year-old heuristic because it’s fast and works reasonably well. Solving it exactly (shortest path, dynamic Huffman, block splitting) gives a real but modest improvement: a few percentage points, not a change of category.
3. The compressed file’s format decides which optimizations are possible. A format that transmits more metadata (like DEFLATE’s Huffman tree) opens the door to tuning it per file. A more compact format (like LZMA’s internal state) closes that door in exchange for less overhead. There’s no option that’s simply better: they’re different trade-offs, and knowing which is which tells you in advance what’s worth trying.

If a genuinely large jump exists, it’s in the context mixing family, which mixes dozens of models with weights learned bit by bit instead of one model with one heuristic. That does change category, at the cost of being orders of magnitude slower. But that’s another story.

When this is worth it, and when it isn’t

Concretely, so this is more than curiosity:

• Compressing once and decompressing many times (a site’s assets, a release’s packages, static images) is the case where optimal parsing is worth it: the extra cost of compressing is paid once, and the file stays 2-3% smaller forever. Zopfli already does this in production for exactly this case.
• Compressing on the hot path of a request (real-time gzip of an HTTP response) is the case where it isn’t worth it: the dynamic programming and iterative reparsing are several times slower than zlib’s greedy, and there latency matters more than 3% of size.
• If the format is already LZMA, the specific adjustment tested here (changing the probability start-up from the outside) doesn’t transfer, for the format reason already covered; but the underlying principle does: asking whether the algorithm in use solves its decision exactly or with a single-pass heuristic usually reveals margin nobody went looking for. Zstandard is a good example that the general principle (a second pass with more information helps) can apply to an adaptive coder, as long as it doesn’t touch the state that never gets transmitted.

Sources

• Deutsch, P. “DEFLATE Compressed Data Format Specification version 1.3.” RFC 1951, IETF, 1996. Section 3.2.7 (run-length encoding of code lengths). rfc-editor.org/rfc/rfc1951
• zlib, official source code (Mark Adler). github.com/madler/zlib
• Zopfli, Google’s DEFLATE compressor. github.com/google/zopfli
• Calgary and Canterbury corpora, official descriptions and download. corpus.canterbury.ac.nz/descriptions
• Pavlov, I. LZMA SDK and LZMA format specification. 7-zip.org/sdk.html
• c2rust, C-to-Rust translator (Immunant). github.com/immunant/c2rust