Dictionary Coding

References repeated patterns using offset and length.

Sliding Window

Maintains a moving window for pattern matching.

Algorithm Base

Foundation for ZIP, GZIP, DEFLATE, and PNG.

How LZ77 Works

LZ77 maintains a sliding window of recently seen data. For each position, it searches the window for the longest matching substring. If found, it outputs a reference (offset, length, next character). If not found, it outputs a literal (0, 0, character). This replaces repeated patterns with short references, achieving compression.

LZ77 Example

Text: "ABCABCABC"
Window=4, Lookahead=4

Position 0: 'A' - no match
  → (0,0,A)

Position 1: 'B' - no match
  → (0,0,B)

Position 2: 'C' - no match
  → (0,0,C)

Position 3: 'ABC' - matches at offset 3
  → (3,3,A)

Position 7: 'BC' - matches at offset 3
  → (3,2,)

Output: (0,0,A)(0,0,B)(0,0,C)(3,3,A)(3,2,)