Your text file is 10 MB. You compress it and it is 2.5 MB. You decompress it and it is exactly the same file, bit for bit, without a single different letter. Nothing has been lost, and yet 75 % of the information is missing. That apparent miracle has a trick, and the trick is not statistical magic: a lossless compressor does not store your text, it stores the instructions to rebuild it. What gets written to disk is a recipe, and the better the recipe, the fewer ingredients it needs.
Compressing is looking for repetitions
The first engine in almost every modern compressor is an algorithm from the LZ77 family, described in 1977 by Lempel and Ziv. The idea is so simple it fits in one sentence: if something you already wrote shows up again, do not write it again, say where it was. The compressor keeps a sliding window over the last few kilobytes or megabytes already processed, and at each position it looks for the longest possible match inside that window. When it finds one, it emits a sequence: how many literal bytes come before the match, how many bytes the match is long, and how far back it sits. Those three numbers are known as literals, match length and offset.
The window size is the parameter that changes results the most. With 128 KB the compressor can only refer back to what was written a few paragraphs ago; with several MB it can point at something that appeared a hundred pages earlier. That is the real reason higher compression levels take longer: they are not magic, they search further away and with more candidates per position. The cost is CPU time, and in zstd, for instance, low levels use simple hash tables while high levels chain searches in trees or hash-chain lists.
Then those numbers have to be encoded
Having sequences is not enough. A 32-bit integer representing a small offset wastes three bytes if you store it as is. This is where entropy coding comes in: it assigns short codes to frequent symbols and long ones to rare symbols, and it is the only part of the process that resembles the compression people imagine.
The classic is Huffman: a binary tree is built from the observed frequencies and the bitstream is read leaf by leaf. Deflate, the format behind gzip and the historic HTTP responses, combines LZ77 with static or dynamic Huffman. The problem with Huffman is that it is limited to a whole number of bits per symbol: if a symbol shows up with 60 % probability, the ideal cost would be 0.74 bits, and Huffman spends 1 or 0.
Modern solutions are arithmetic and finite-state coders, such as rANS (range Asymmetric Numeral Systems) and the FSE (Finite State Entropy) used inside zstd. Instead of trees, they build automata with transition tables: each state consumes bits and jumps to another state, and each symbol’s frequency maps directly to a probability, not to a rounded number of bits. The gain over Huffman is 3 to 10 % on many streams and — this is what matters in production — decoding happens through in-memory tables at several gigabytes per second, without the unpredictable branches of a tree walk.
The format is part of the design too
A serious compressor is a format, not a loose algorithm. In zstd the stream is organised into frames and, inside them, into blocks of at most 128 KB, and each block chooses between three modes: store the data raw, repeat a single byte (RLE) or compress it. That decision is made per block and automatically, because some data simply does not compress: a JPEG, an already-encoded video or an encrypted key have high entropy and any attempt to compress them would make them larger. A compressor that cannot give up is a compressor that ruins your size.
Because blocks are independent, they can be compressed and decompressed in parallel, and they enable streaming: you can start decompressing without holding the whole file in memory. The frame also carries an optional checksum (XXH64), the content size when it is known in advance, and the parameters used, so the decoder knows exactly what to do without guessing.
Dictionaries: when your data is small but repetitive
If you compress a 400-byte message, the search window has barely had time to fill up and the result is poor. The answer is trained dictionaries: you feed the compressor thousands of representative samples from your domain (say, your API’s JSON responses, or log records) and a training algorithm — COVER in zstd, and recent variants such as fastCover — extracts the fragments that appear most often, weighted by frequency and coding cost, and packages them as a dictionary of tens of kilobytes. That dictionary travels once with the decoder, and afterwards each small message is compressed as if it were a continuation of the master sample. In APIs with many short, similar messages, the difference between 40 % and 90 % reduction lives exactly there, not in the compression level.
What is actually used today
Deflate is still everywhere for compatibility: HTTP, ZIP, PNG. Brotli ships its own static dictionary of common web words and rules small and medium static web content. Zstandard (zstd, RFC 8878) has taken over the rest: it picks a point on the speed/size curve almost at will, with levels ranging from compressing at over 500 MB/s to squeezing out the last byte, and it has a fast mode with negative parameters aimed at ephemeral data such as a write buffer or a network channel.
In the browser, zstd is already an accepted content-encoding alongside gzip and brotli; in Linux, the kernel uses it for zram (compressed memory instead of swap), for Btrfs and for SquashFS; in the data world, Parquet and Arrow use it as the default codec. The reason is not just ratio: it is that decompression is predictable and cheap. A compressor that wins 2 % but forces you to reserve memory proportional to the block size is a compressor that will never make it into a service handling thousands of requests per second.
What a compressor learns from your data
In the end, the lesson is the same as in other layers of computing: the compressor has not understood your text, it has found statistical structure in it. Exact repetitions, biased symbols, length patterns. When you compress data that is already compressed or encrypted, that structure has been deliberately removed and there is nothing left to squeeze. And when you apply a dictionary trained on the right samples, the system appears to understand your domain, even though all it has done is count better.
