deflate

Deflate is a lossless data compression algorithm and format that combines LZ77-style sliding-window compression with Huffman coding. It is standardized as the DEFLATE format (RFC 1951) and has become a de facto standard in many file formats and network protocols, including ZIP, GZIP, and PNG.

In the DEFLATE process data is divided into blocks. Each block can be stored uncompressed, or compressed using either a fixed Huffman tree or a dynamically generated Huffman tree. The algorithm uses a 32-kilobyte sliding window for matching and can emit matches up to 258 bytes long, represented as length/distance pairs, alongside literals. Huffman codes are built for the literals, lengths, and distances within each block to achieve efficient encoding. This combination allows both fast decompression and strong compression for a wide range of data.

DEFLATE is often implemented with a wrapper around the raw compressed bitstream. For example, the zlib format adds a header and trailer around DEFLATE data, while gzip uses a different wrapper. PNG embeds DEFLATE-compressed data within its IDAT chunks. The algorithm’s balance of good compression ratio, speed, and broad compatibility has contributed to its widespread adoption since its introduction in the 1990s.

Deflate remains a core method for reducing data size in many contexts, particularly where cross-platform interoperability and efficient decompression are important.