LZ77 (source code)
= LZ77
{c}
<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.<DEFLATE Compressed Data Format Specification version 1.3 by L. Peter Deutsch>[§§3.2.3 and3.2.5, length/distance pairs and overlap]{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.
Back to article page
