DEFLATE is a lossless data compression algorithm that combines LZ77 (Lempel-Ziv 1977) sliding-window compression with Huffman coding. It was originally designed by Phil Katz for PKZIP and later formalized in RFC 1951. DEFLATE is widely used in file formats such as gzip, PNG, and ZIP, as well as in network protocols like HTTP (content-encoding: deflate). The algorithm offers a good balance between compression ratio and speed, making it a staple of modern data storage and transmission.

1 History

1.1 Development by Phil Katz

In the late 1980s, Phil Katz, founder of PKWare, sought to create a compression algorithm that improved upon existing methods used in early archivers such as ARC and LHA. Katz combined LZ77 matching with Huffman coding, producing a more efficient yet patent-free (at the time) algorithm. This work led to the implementation now known as DEFLATE.

1.2 Inclusion in PKZIP 2.0

PKZIP version 2.0, released in 1993, was the first major software to adopt DEFLATE as its default compression method. This replaced the earlier "shrinking" and "reducing" algorithms used in PKZIP 1.0, offering significantly better compression ratios while maintaining acceptable speed. The success of PKZIP 2.0 popularized DEFLATE across the PC software ecosystem.

1.3 Standardization via RFC 1951

In 1996, the Internet Engineering Task Force (IETF) published RFC 1951, which formally specified the DEFLATE compressed data format. This standardization enabled wide adoption in open-source tools and network protocols. RFC 1951 remains the authoritative reference for the algorithm.

2 Algorithm

2.1 LZ77 stage

The first stage of DEFLATE applies LZ77 compression, which replaces repeated sequences of bytes with references to earlier occurrences. The encoder maintains a dictionary of previously seen data and outputs either a literal byte or a length–distance pair.

2.1.1 Sliding window (32 KB default)

DEFLATE uses a sliding window of 32,768 bytes (32 KB) as the maximum dictionary size. The encoder only looks back within this window for matches, limiting memory usage and search complexity. Smaller window sizes (e.g., 256 bytes) can be enforced in some implementations.

2.1.2 Match finding and length–distance pairs

When a sequence of at least three identical bytes (a match) is found in the window, the encoder emits a length–distance pair. The length is in the range 3–258, and the distance is 1–32,768. These values are encoded using special codes in the subsequent Huffman stage. Shorter matches may be discarded if they do not save space.

2.1.3 Literal bytes and end-of-block

If no suitable match is found, the byte is output as a literal (0–255). A special end-of-block (EOB) symbol (value 256) marks the termination of the current block. Literals and the EOB are encoded along with length codes in a single Huffman tree.

2.2 Huffman coding stage

After LZ77 processing, DEFLATE applies Huffman coding to the sequence of literals, lengths, distances, and EOB symbols. This stage reduces the size by using variable-length codes for more frequent symbols.

2.2.1 Code tree construction

The Huffman trees are built from the frequencies of symbols that appear in the block. The algorithm assigns shorter codes to more frequent symbols, following the standard Huffman procedure. For distance codes, the tree is constructed separately.

2.2.1.1 Canonical Huffman codes

DEFLATE uses canonical Huffman codes, where the bit-length assignments are preserved but the code values are assigned in a standard numeric order. This allows the decoder to reconstruct the tree using only the code lengths, reducing the overhead of storing the tree.

2.2.2 Static vs dynamic Huffman tables

DEFLATE supports two modes for Huffman tables. In static mode, predefined code length tables are used, which are always the same and require no extra data in the compressed stream. In dynamic mode, the encoder computes custom tables based on the actual symbol frequencies and sends the code lengths (compressed further) as part of the block header. Dynamic tables are more efficient but add overhead.

2.2.3 Code length sequences (Run-length encoding)

To store dynamic Huffman code lengths compactly, DEFLATE applies run-length encoding. Special codes represent runs of repeated lengths, zero runs, and re-use of the previous length. This reduces the space needed to describe the tree, especially when many symbols have the same length (e.g., many zero lengths for unused symbols).

2.3 Block structure

A DEFLATE stream is composed of a sequence of blocks. Each block is independently decodable and can use one of three compression types.

2.3.1 Stored (no compression) blocks

These blocks contain raw, uncompressed data. They are used when compression would not reduce size (e.g., already compressed or random data). The block header includes the data length and its one's complement for integrity checking.

2.3.2 Compressed blocks with fixed Huffman codes

Fixed Huffman blocks use predefined static code trees for literals/lengths and distances. The trees are defined in the RFC and are always the same. This mode avoids the overhead of transmitting code tables and is efficient for data that matches the fixed distribution.

2.3.3 Compressed blocks with dynamic Huffman codes

Dynamic Huffman blocks use custom trees built from the actual data. The trees are transmitted as code length sequences at the start of the block. This mode adapts better to the data and usually provides better compression than fixed mode.

2.3.4 Final block flag

Each block header contains a one-bit "BFINAL" flag. When set to 1, it indicates that the current block is the last block of the stream. This allows streaming decompression without needing prior knowledge of the total compressed size.

3 Variants and implementations

3.1 zlib wrapper (RFC 1950)

The zlib library wraps raw DEFLATE data with a simple header and trailer. The header indicates compression method, compression level, and optional dictionary ID. The trailer contains an Adler-32 checksum of the original uncompressed data. This wrapper is used by the PNG format and many network protocols.

3.2 gzip wrapper (RFC 1952)

gzip wraps DEFLATE with a header containing a magic number, timestamp, optional filename, and an operating system identifier. The trailer includes a CRC-32 checksum and the original uncompressed size. gzip is commonly used for file compression (.gz) and in HTTP content-encoding.

3.3 Optimized libraries

3.3.1 zlib

The reference implementation of DEFLATE, authored by Jean-loup Gailly and Mark Adler, is known as zlib. It provides a portable, standard-compliant library for compression and decompression. zlib is widely used in operating systems, embedded software, and many applications.

3.3.2 zlib-ng

zlib-ng is a fork of zlib focused on modern performance optimizations. It improves throughput and compression ratio by using newer CPU instructions (e.g., SSE, AVX), better memory management, and faster hash functions. It maintains full compatibility with zlib.

3.3.3 CloudFlare zlib

CloudFlare developed a heavily optimized version of zlib for web serving. It adds several algorithmic improvements, such as a faster match finder and better handling of small files. It is used in CloudFlare's infrastructure to reduce latency and improve compression speed.

Brotli, developed by Google, uses a similar LZ77+Huffman approach but adds a static dictionary, larger window sizes, and context modeling for better compression of web content. Zstandard (zstd), from Facebook, offers faster compression/decompression and higher ratios by using a finite-state entropy coder (tANS) and advanced match finding. Both are considered successors to DEFLATE in many applications.

4 Applications

4.1 File formats

4.1.1 ZIP archives

The ZIP format uses DEFLATE as its primary compression method (method code 8). ZIP files store compressed data as DEFLATE streams within local headers, with central directory structures for metadata.

4.1.2 gzip compression (.gz)

The gzip tool compresses single files into .gz archives using DEFLATE with a gzip wrapper. It is commonly used on Unix-like systems for compressing logs, backups, and software distributions.

4.1.3 PNG image format

Portable Network Graphics (PNG) uses DEFLATE (via the zlib wrapper) for lossless image compression. The IDAT chunks contain compressed pixel data, and the header/filtering stage precedes DEFLATE to improve compression.

4.1.4 TIFF (optional)

The Tagged Image File Format (TIFF) supports DEFLATE as one of its compression options (tag 32946). It is used for storing large images losslessly, often replacing older LZW compression.

4.2 Network protocols

4.2.1 HTTP content-encoding

HTTP allows servers to compress response bodies using the Content-Encoding: deflate header. This indicates that the body is a raw DEFLATE stream (per RFC 1951, not zlib- or gzip-wrapped). However, many implementations incorrectly use zlib wrapping, leading to interoperability issues. For this reason, gzip is often preferred.

4.2.2 TLS compression (deprecated)

Transport Layer Security (TLS) once supported a compression step using DEFLATE. This was found to be insecure (e.g., CRIME attack) and was disabled in TLS 1.3. Current TLS implementations no longer enable compression.

5 Performance and trade-offs

5.1 Compression levels (1–9)

Most DEFLATE implementations (notably zlib) offer compression levels from 1 (fastest, least compression) to 9 (slowest, best compression). Level 1 uses minimal searching for matches, while level 9 exhaustively searches the window and may use lazy matching. Level 6 is the default, balancing speed and ratio.

5.2 Memory footprint vs speed

DEFLATE's memory usage is dominated by the sliding window (32 KB) and the hash tables for match finding. Higher compression levels increase the hash table size and search depth, raising memory consumption. Decompression requires only the sliding window and Huffman tables, so its memory footprint is small (under 100 KB). Speed varies widely with levels: level 1 can compress over 200 MB/s, while level 9 may drop to 5–10 MB/s on modern CPUs.

5.3 Comparison with other algorithms (LZMA, bzip2)

Compared to LZMA (used in 7z) and bzip2, DEFLATE offers a middle ground. LZMA achieves higher compression ratios (often 20–40% better) but is slower in both compression and decompression. bzip2 uses block-sorting (Burrows–Wheeler transform) and is slower than DEFLATE in decompression, though it can compress better on text. DEFLATE remains dominant where decompression speed is critical, such as in web serving and embedded systems.

6 See also

  • Lossless compression
  • Lempel–Ziv–Welch (LZW)
  • LZ77 and LZ78
  • Huffman coding
  • zlib
  • gzip
  • PNG
  • Zip (file format)
  • Brotli (compression algorithm)
  • Zstandard