How Data Compression Works: LZ77, Huffman, gzip, Brotli and Zstandard

Lossless vs. lossy: what "compression" means here

There are two families. Lossy compression, used by JPEG photos and most video, throws away detail your eyes are unlikely to notice. Lossless compression keeps every bit, so the output after decompression is identical to the input. Code, documents, databases and web pages must be lossless, because a single changed byte can break a program or corrupt a record.

Lossless compressors work by finding and removing redundancy. Real data is full of it, and it comes in two forms:

• Repetition: the same strings show up again and again, like <div class= in HTML or function in JavaScript.
• Uneven frequency: some symbols are far more common than others. In English text, e and spaces appear constantly while z and q are rare.

Each form has its own classic fix, and almost every popular compressor combines both.

Idea 1: LZ77 replaces repeats with back-references

In 1977, Jacob Ziv and Abraham Lempel published a method now called LZ77. The compressor reads the input from start to end while remembering a recent stretch of it, called the sliding window. When it meets a run of bytes it has already seen inside that window, it writes a short pointer instead of the bytes themselves: "go back distance bytes and copy length bytes."

Input:   the cat sat on the mat with the cat
Output:  the cat sat on [back 15, copy 4]mat with [back 28, copy 7]
         "the " was seen 15 bytes earlier; "the cat" was seen 28 bytes earlier

The decoder is simple and fast: it just copies bytes it has already rebuilt. The hard, slow part lives in the encoder, which must search for the longest useful match. That asymmetry explains why "compression level" settings mostly change how hard the encoder searches, while decompression speed stays roughly the same.

Idea 2: Huffman coding gives common symbols shorter codes

Normal text stores every character in a fixed number of bits. David Huffman's 1952 method does better by building a code where frequent symbols get short bit patterns and rare symbols get long ones. Morse code uses the same intuition: the common letter E is a single dot.

Huffman codes are prefix-free, meaning no code is the start of another, so the decoder always knows where one symbol ends and the next begins without any separators. After LZ77 has removed the repeats, Huffman coding squeezes the leftover literals and pointers further.

Huffman has one limitation: every symbol must cost a whole number of bits. Newer entropy coders, such as the asymmetric numeral systems used in Zstandard, can effectively spend fractions of a bit, which helps when one symbol is extremely common.

DEFLATE and gzip: the classic combination

DEFLATE, specified in RFC 1951, is LZ77 plus Huffman coding, and it sits inside gzip, zlib, ZIP files and PNG images. Its limits are modest by today's standards:

• Back-references can reach at most 32 KB into the past.
• Matches are between 3 and 258 bytes long.
• Data is split into blocks that are either stored raw, coded with a fixed built-in Huffman table, or coded with a custom table sent at the start of the block.

The gzip format (RFC 1952) wraps DEFLATE data in a small header that begins with the bytes 1f 8b, and a trailer holding a CRC-32 checksum and the original size so the receiver can detect corruption. That 32 KB window is the main thing newer formats improve on: a repeat that last appeared 100 KB earlier is invisible to DEFLATE.

Brotli and Zstandard: the modern formats

Brotli

Brotli, published by two Google engineers as RFC 7932 in 2016, keeps the LZ77-plus-Huffman core but adds three upgrades. Its window can grow to nearly 16 MB. It chooses among Huffman tables based on the previous two bytes, a technique called context modeling. And it ships with a built-in dictionary of common words and phrases, so even a small file can point at strings the decoder already knows. The RFC states the aim of being considerably denser than gzip while decompressing faster than LZMA. Brotli is also the compression inside WOFF 2.0 web fonts.

Zstandard

Zstandard (zstd), designed by Yann Collet and described in RFC 8878, also uses LZ-style matching but pairs Huffman coding for literals with a finite-state entropy coder for everything else. It offers a very wide range of speed and ratio settings, and supports trained dictionaries: you feed it samples of small, similar messages, such as JSON API responses, and it learns their shared structure ahead of time. The RFC recommends that encoders avoid windows above 8 MB for broad compatibility.

Comparing data compression formats for the web

Browser support has caught up. According to the Web Platform features explorer, zstd content encoding shipped in Chrome 123 and Firefox 126 in 2024 and reached Safari 26.3 in February 2026, making it Baseline "newly available." Brotli has been supported in all major browsers for years.

How compression is negotiated over HTTP

Browsers announce what they can decode in an Accept-Encoding request header. The server picks one and labels the response with Content-Encoding:

# Ask for compressed responses and see what the server chose
curl -sI https://example.com/ -H 'Accept-Encoding: zstd, br, gzip' | grep -i content-encoding

# Compress a file three ways and compare sizes
gzip -9 -k app.js && brotli -q 11 -k app.js && zstd -19 -k app.js
ls -l app.js*

Because the same URL can now come back in several encodings, shared caches need Vary: Accept-Encoding so they never hand a Brotli file to a client that only understands gzip. That ties directly into how HTTP caching works.

A practical playbook

1. Pre-compress static assets at build time with Brotli at a high level. You pay the slow encoding once, and every visitor gets the smaller file.
2. Use a fast setting for dynamic responses. For HTML and API output generated per request, moderate zstd or Brotli levels keep server CPU low.
3. Keep gzip as the fallback for older clients, bots and tools.
4. Minify first, then compress. Removing comments and whitespace helps, though compression already handles much of the repetition.
5. Mind your text encoding. Compressors work on bytes, so a consistent UTF-8 encoding keeps repeated words as identical byte sequences.

Frequently asked questions