CoreSource checked

LZ77

Compresses repeated substrings by referring back to earlier bytes in a sliding window.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Compression
Difficulty: Intermediate
Family: Dictionary Compression
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 8
Code example: Not ready
Visualization: Ready

Overview

LZ77 scans input while maintaining a window of recently seen data. When the next bytes match earlier bytes, the encoder emits a distance and length instead of repeating the literal bytes.

Core Concepts

sliding windowdictionary referencedictionary compressionsymbol representationlossless decodingstream encoding

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(nw)

Worst

O(nw)

Space

O(w)

When to Use

Use when repeated sequences tend to appear near each other.
Use as a dictionary stage before entropy coding.

When Not to Use

Avoid expecting strong compression on random or encrypted data.
Avoid when match searching is too expensive for the latency budget.

What It Does

Maintains a sliding history window
Finds the longest useful previous match
Emits literals or length-distance references

Use Cases

Lossless byte compression
Preprocessing before entropy coding
Data with local repeated substrings

Inputs

Byte or symbol stream
Window size

Outputs

Literals and back-references

Key Formulas (1)

Back-reference token

token = (offset, length, next_symbol)

token = (offset, length, next_symbol)

Represents a repeated phrase by pointing backward into the sliding window.

Pseudocode

1.Initialize an empty sliding window
2.At the current input position, find the best match in the window
3.If the match is long enough, emit distance and length
4.Otherwise emit the next literal byte
5.Advance input and update the window

Canonical Example

Input: 'ABCABCABC'
Output: literal 'ABC' plus a reference to repeat the previous three bytes twice
Explanation: The later 'ABC' runs are encoded as backreferences into the sliding window.