DEFLATE

DEFLATE is a lossless compression algorithm that combines LZ77 dictionary-based matching with Huffman coding of the resulting tokens. It was designed by Phil Katz in 1993 for the ZIP file format and has since become one of the most widely deployed compression algorithms in the world, underlying not only ZIP but also the PNG image format, the gzip utility, and modern web protocols.

The algorithm operates in two stages. First, LZ77 parsing replaces repeated byte sequences with back-references. Second, Huffman coding compresses the stream of literal bytes and back-reference tokens by exploiting their non-uniform frequency distribution. A dynamic Huffman table, computed per-block, allows DEFLATE to adapt to local statistics within a file.

DEFLATE's design reflects a pragmatic insight: no single technique is optimal for all data types, but the combination of dictionary matching and entropy coding handles a broad range of real-world inputs efficiently. It remains the baseline against which newer algorithms are measured.