LZ77

LZ77 is a lossless compression algorithm developed by Abraham Lempel and Jacob Ziv in 1977. It is the foundational algorithm of the Lempel-Ziv family and underlies the widely used DEFLATE format employed by ZIP, gzip, and PNG.

LZ77 operates by maintaining a sliding window of previously seen data and replacing repeated sequences with back-references consisting of a distance (how far back the match begins) and a length (how many bytes match). The algorithm requires no explicit dictionary; instead, it builds an implicit one from the input history. This streaming design makes LZ77 ideal for compressing data where the structure is unknown in advance and may vary over the course of the input.

The algorithm's efficiency depends critically on the size of the sliding window and the speed of string matching. Modern implementations use hash chains or suffix arrays to find matches in constant or logarithmic time, enabling compression of large files in memory-constrained environments.