You have an 800-page novel in front of you. You compress it with gzip and it takes up a quarter of the space. Not a single letter has disappeared: decompressing returns the exact text. What actually happened? The file no longer stores what you wrote, but the repetitions it found. That is the heart of lossless compression and, more specifically, of DEFLATE, the format gzip uses.
Repeating is expensive: the starting idea
Normal text is full of recurring phrases: «the», «of», «chapter», spaces, punctuation. Storing every occurrence separately is wasteful. Compression simply describes the file in the fewest bits possible by exploiting that pattern, much like taking an acronym: if a long phrase appears forty times, better to write the short form once and keep a glossary.
DEFLATE —the algorithm behind .gz files, zip and the HTTP protocol— chains two techniques that work at different levels: LZ77, which catches repetitions at the level of byte sequences, and Huffman, which relabels symbols so frequent ones take fewer bits.
First pass: LZ77, a sliding dictionary
LZ77 does not analyze the whole file: it uses a sliding window, a region of the last 32 KB already read that acts as a dictionary. A pointer tracks the current byte and looks backward inside that window to see whether the sequence starting there appeared before.
When it finds a match, instead of writing the bytes literally it writes a reference: (distance, length), i.e. «this already appeared N bytes ago and lasts M bytes». If the repetition is long, a reference of a few bytes saves many. To keep the search fast, the compressor does not compare byte by byte: it maintains hash tables that index, for each position, the first three bytes (a 24-bit fingerprint) and only checks positions with the same fingerprint.
This scan produces two kinds of items, called «literals and distances», which mix in the stream: isolated bytes that do not repeat, and reference pairs pointing at repetitions. We have already shrunk the size some, but a second battle remains.
Second pass: Huffman, variable-length codes
The Huffman pass relabels each symbol with variable-length codes: the most frequent symbols get short codes and the rare ones get long codes. The word «the» could become the bit 010 while a rare character gets a longer code.
The catch is that these codes must decode unambiguously. They are built as a binary Huffman tree: take the symbols with their frequencies, repeatedly merge the two least frequent into a node, and the path from root to each leaf (0 left, 1 right) forms the code. That is why no code is a prefix of another: a single bit can never be interpreted two ways.
DEFLATE combines both trees (one for literals and lengths, one for distances). The outcome is the so-called compressed block, with three strategies: stored (raw data, for uncompressible stretches), fixed (a predefined Huffman tree, not transmitted) and dynamic (the tree travels with the data, improving compression but adding its cost).
From blocks to the final byte: the wrapper
All that logic happens at the block level; the format you actually handle is the gzip wrapper: a header with the 1f 8b magic, the method (deflate), a few flags, plus a CRC-32 checksum and the original size in the trailer, letting corruption be detected. The intermediate layer that fills, aligns to 16-bit blocks and adds CRCs is zlib.
This layered architecture explains why compression has an asymmetric cost: compressing is expensive (searching for repetitions across 32 KB, building trees), while decompressing is cheap (following references and walking trees). That is why web servers deliver already-compressed content (Content-Encoding: gzip) once, and thousands of browsers decompress it on the fly.
Why sometimes nothing compresses
All this engineering has a limit: if the data no longer repeats or has dominant symbols —an encrypted file, a JPEG image, an already-compressed video— LZ77 finds no matches and Huffman has nothing to reward. The compressor detects that the block is not shrinking and emits it «stored», sometimes making the file even larger than the original because of the header. Everyone hits this the first time they try to compress a second compression: the result is a file only slightly heavier than the first one.
The next time you see gzip’s reduction percentage, do not think of magic. Think of a 32 KB window packed with fingerprints, two binary trees and a list of repetitions. Compressing is, literally, finding what repeats and not writing it again.
