Time Complexity
Best: O(n)
Avg: O(n · W)
Worst: O(n · W)
LZ77 is a dictionary compressor invented by Abraham Lempel and Jacob Ziv in 1977. Instead of a fixed codebook, it uses a sliding window of recently seen data as a dynamic dictionary.
How it works:
1. Maintain a search buffer (already encoded window) and a look-ahead buffer
2. Find the longest prefix of the look-ahead that also appears in the window
3. Emit a triple (offset, length, next):
- offset — how far back the match starts
- length — how many characters to copy
- next — the literal character that follows the match (or empty at EOF)
4. Slide the window forward by length + 1 and repeat
Why it works:
Repeated phrases (words, patterns, substrings) are common in text and structured data. Pointing back into the window stores a long sequence as a short reference. No code is a prefix of another in the stream of triples, so decoding is unambiguous: copy from offset, then append the literal.
Time Complexity:
Best: O(n) with rolling hashes / advanced matchers
Average: O(n · W) naive scan (W = window size)
Worst: O(n · W)
Space Complexity: O(W) for the window
Properties:
- Lossless dictionary method with a sliding window
- Foundation of DEFLATE (gzip, ZIP, PNG) which pairs LZ77 with Huffman
- Window size trades compression ratio for memory and search cost
- Handles repeated substrings well; pure randomness does not compress
LZ77 turned "look for repeats nearby" into the practical engine behind most everyday lossless archives.
Related algorithms
Frequently asked questions
- What is LZ77?
- LZ77 is a dictionary compressor invented by Abraham Lempel and Jacob Ziv in 1977. Instead of a fixed codebook, it uses a sliding window of recently seen data as a dynamic dictionary.
- What is the complexity of LZ77?
- Time (average): O(n · W) naive scan (W = window size) · Space: O(W)
- Who is this LZ77 visualizer for?
- The LZ77 visualization targets intermediate-level learners in the Compression category. Useful for students, interview prep, and hands-on review.
- What algorithms are related to LZ77?
- In the same category (Compression) you can explore: Run-Length Encoding, LZW, Huffman Coding. Each has an interactive visualization.