LZ77
LZ77 is a lossless dictionary-compression approach that represents repeated data with references into a moving history buffer.
Origins: Ziv and Lempel's 1977 paper describes reconstructing data by copying from recent output. Its theoretical bounds concern an explicit coding model, not guaranteed savings for every finite file. Modern literal/match formats should not be confused with that paper's exact representation. [1]
Format: LZ77 is not a single interoperable file format. DEFLATE combines history references with Huffman coding; LZ4 blocks use a byte-oriented representation without an entropy-coding backend. Sharing the copying idea does not make their streams interchangeable. [2] [3]
Copying: A match specifies how far back to look and how many bytes to emit. It can overlap its own output: after XY, length 5 at distance 2 appends XYXYX. Newly produced bytes supply later bytes of the same match; a frozen slice of the original history is insufficient. [2]
Limits: DEFLATE permits backward distances through 32768 bytes, while the LZ4 block offset field permits values through 65535 and rejects zero. These are different format limits, not a universal LZ77 window size or a maximum file size. [2] [3]
Recovery: Zstandard sequence execution also consumes literal lengths, offsets and match lengths; a dictionary can supply earlier match data. Its frame and dictionary metadata are additional context, not properties established by the LZ77 label. Preserve the concrete format and required decoder state with the bytes. [4]
Encoder choices: A DEFLATE encoder can use a smaller history window or fewer match searches while remaining conformant. A compliant decoder must accept the full defined range. The format limit does not establish an encoder's actual search policy. [2]
Relations
- related
- Lossless compression, DEFLATE, LZ4 frame, Zstandard
Limitations
- A block boundary alone does not ensure independent decoding: DEFLATE references may reach earlier blocks. [2]
- An LZ4 block omits framing metadata such as its size; enclosing formats or the calling application must supply the required boundaries. [3]
Citations
- Ziv and Lempel. A Universal Algorithm for Sequential Data Compression. IEEE Trans. Inf. Theory 23(3), 337-343 (1977). DOI: 10.1109/TIT.1977.1055714.
- RFC 1951: DEFLATE, sections 2, 3.2.3, 3.3 and 4, history references, overlapping copies and compliance (Informational, May 1996).
- LZ4 v1.10.0: Block Format Description, offset encoding, metadata and safe decoding.
- RFC 8878: Zstandard, sections 3.1.1.4-3.1.1.5 and 5-6, sequence execution and dictionaries (Informational, February 2021).
Further reading
Sources & caveats
- Primary-source synthesis. The 1977 date is the cited publication date, not a claim about the first implementation. The overlapping-copy illustration is specified in RFC 1951; no new compression benchmark or error-rate measurement is claimed.