 LZ77

LZ77 is a family of lossless source coding methods that replace repeated data by references to previously decoded data in a sliding window. A reference specifies a backward distance and a match length; unmatched symbols are emitted literally. Some formulations additionally attach a following literal to each match, so the exact token format belongs to the particular codec.

For example, encode abcabcabc as literal abc followed by distance3,length6. Decoding copies sequentially from three positions behind the current output. The source and destination overlap: the first copied abc becomes available for the second copy. Copying the referenced region as one fixed pre-existing array slice would therefore be incorrect. DEFLATE combines LZ77-style matches with Huffman coding and explicitly allows overlapping references.^[ref] A match finder and a token-cost model determine which repetitions are profitable; a longer textual match is not automatically the cheapest encoded choice.