LZ77, LZW and Deflate

In short: LZ77 and LZW are dictionary methods of compression: they replace repetitions with short references to data already seen. Deflate combines LZ77 with Huffman coding.

In more detail: Deflate is inside ZIP, gzip, PNG and HTTP compression. It is the most widely used compression method of all.

In Depth

• LZ77: Keeps a “window” of the last kilobytes. When the encoder meets a repetition, it writes (distance, length) instead of the bytes. abcabcabc becomes abc plus “copy 6 characters from 3 back”.
• LZW: Builds a dictionary of character sequences while running and outputs only indexes. Used in GIF and early TIFF. Patent questions once slowed its spread.
• Deflate: LZ77 yields literals and references, then Huffman encodes frequent symbols short. Window 32 KiB.
• Successors: Zstandard and Brotli reach better ratios at higher speed, see Brotli and Zstandard.
• Compression limit: Random or already compressed data can hardly be shrunk.

See also: Compression