LZ77 Explained: How Sliding-Window Compression Finds and Reuses Repeated Data

LZ77 is the algorithm that taught modern compressors how to spot repetition. Instead of encoding every byte from scratch, it slides a window back through data it has already seen and replaces repeated sequences with a simple pointer, laying the groundwork for formats like DEFLATE, gzip, and PNG.

Iman Atarof • imaarov

Computer Engineering student focused on systems programming, Linux, data compression, binary file formats and software written in C.

Updated July 27, 2026
25 views

Table of Contents

Introduction to LZ77

LZ77 is a lossless compression algorithm published by Abraham Lempel and Jacob Ziv in 1977. Instead of assigning shorter codes to frequent symbols the way Huffman coding does, LZ77 attacks redundancy from a different angle: it replaces a repeated chunk of data with a small reference that says "copy this many bytes from that far back." If a phrase has already appeared in the stream, LZ77 never stores it twice (well in the most part that's true).

This one idea turned out to be enormously influential. LZ77 and its close variant LZSS sit underneath gzip, zip, PNG, and other formats through the DEFLATE algorithm, and its descendants (LZMA, Brotli, Zstandard) power modern archivers and web compression. Understanding LZ77 is really understanding the ancestor of most general-purpose compression in use today.

The core idea

LZ77 keeps two views of the data at once: the part it has already processed, and the part it hasn't seen yet. When it's about to encode the next byte, it asks a simple question: "does the upcoming data match something I've already emitted (seen)?" If yes, it emits a back-reference instead of raw bytes. If no, it emits the byte itself, literally. That's the whole algorithm, the interesting engineering is entirely in how efficiently you can answer "does this match something I've already seen?"

Why not just store everything literally?

Consider the string "abcabcabcabc". Stored literally that's 12 bytes. But after the first three characters, the encoder has already seen “abc”, every later occurrence can be described as "go back 3 bytes, copy 3 bytes" instead of 3 fresh bytes. On highly repetitive data this collapses the output dramatically, which is exactly why LZ77-based compressors do so well on text, source code, and structured binary formats.

What Is a Sliding Window?

LZ77 doesn't search the entire history of the input for matches, that would get slower and slower as the file grows, and matches from a million bytes ago aren't cheap to reference anyway. Instead it limits itself to a fixed-size window that moves forward as encoding progresses. The window is split into two regions:

  • The search buffer (sometimes called the dictionary): bytes that have already been encoded, and are therefore available as copy sources.
  • The look-ahead buffer: the next few bytes waiting to be encoded, which the algorithm tries to match against the search buffer.

Window layout

|<--- search buffer --->|<--- look-ahead buffer --->|
|  already encoded data |   data waiting to be read  |
                          ^
                    current position

Encoding one token means: look at the bytes currently sitting in the look-ahead buffer, scan the search buffer for the longest prefix of the look-ahead buffer that already exists somewhere in it, and emit a reference to that match. Once a token is emitted, the window slides forward by however many bytes were just consumed, the oldest bytes fall off the back of the search buffer, and fresh bytes enter the front of the look-ahead buffer from the input stream.

Why the window is bounded

A fixed window size caps both the cost of searching (you only ever compare against, at most, window_size candidates) and the size of a distance value in the output (a match can never point further back than the window is wide, so the distance field has a known, small maximum). This is a deliberate trade-off, a bigger window can find more distant matches and compress better, but it costs more time to search and more bits to encode the distance. DEFLATE, for instance, fixes its window at 32 KB, a number chosen decades ago to balance compression ratio against the memory and CPU budgets of the era.

The (Distance, Length, Character) Triple

Classic LZ77 output is a sequence of triples: (distance, length, character).

  • distance : how many bytes back the match starts, measured from the current position.
  • length : how many bytes the match covers.
  • character : the literal byte that comes immediately after the match.

When no match is found, the encoder still emits a triple, just with distance = 0 and length = 0, and the character field carries the raw literal byte. This is what a "literal token" looks like in the reference code further down, a triple that degenerates into "no copy, just this one byte."

The trailing character field is a small but important detail. It guarantees that every token consumes at least one new byte from the input, even in the pathological case where the look-ahead buffer matches the search buffer exactly and there's nothing left to differentiate, the encoder always has a way to make forward progress and always has something to say about the very next never-before-seen byte.

Worked Example: Encoding "ABCABC"

To see the sliding window in motion, let's encode the 6-byte string "ABCABC" with a search buffer of 3 bytes and a look-ahead buffer of 3 bytes.

Position 0

search buffer:      [ _ , _ , _ ]      (empty, nothing encoded yet)
look-ahead buffer:  [ A , B , C ]

No candidates in the search buffer -> no match possible.
Emit: (0, 0, 'A')
Slide the window forward by 1.

Position 1

search buffer:      [ A ]
look-ahead buffer:  [ B , C , A ]

'A' does not match 'B' -> no match.
Emit: (0, 0, 'B')
Slide forward by 1.

Position 2

search buffer:      [ A , B ]
look-ahead buffer:  [ C , A , B ]

Neither 'A' nor 'B' matches 'C' -> no match.
Emit: (0, 0, 'C')
Slide forward by 1.

Position 3

search buffer:      [ A , B , C ]
look-ahead buffer:  [ A , B , C ]

Compare from search buffer offset 0:
  'A' == 'A', 'B' == 'B', 'C' == 'C'  -> match length 3
Distance from current position back to that match = 3.
Input is now exhausted, so there is no trailing literal.
Emit: (3, 3, -)

Final output stream: (0,0,'A') (0,0,'B') (0,0,'C') (3,3,-). Three literal tokens cover the first appearance of "ABC," and a single match token reconstructs the second appearance by pointing 3 bytes back and copying 3 bytes forward. Six input bytes became four tokens, a small example, but it's exactly the mechanism that lets LZ77 collapse megabytes of repeated data into a handful of back-references.

Reference Implementation in C

The following is a compact, single-file LZ77 encoder written in C. It's deliberately close to the textbook description: a fixed-size window array, a search buffer, a look-ahead buffer, and a brute-force match finder. It's not the fast version, that comes later, but it maps directly onto the concepts above.

Header: constants and structures

#include <stdbool.h>
#include <stdint.h>

#define SEARCH_BUFFER_SIZE     7
#define LOOK_AHEAD_BUFFER_SIZE 6
#define WINDOW_SIZE            SEARCH_BUFFER_SIZE + LOOK_AHEAD_BUFFER_SIZE
#define DATA_SIZE              17
#define MATCH_TOKEN            1
#define UNMATCH_TOKEN          0

typedef struct {
    uint32_t longest_match_len;
    int32_t  longest_match_index;
} longest_match_t;

typedef struct {
    uint32_t distance;
    uint32_t length;
    uint32_t character;
} lz77_t; // triple (D, L, C), e.g. (0,0,C)

void init_look_ahead_buffer();
bool shift_window(int skip);
longest_match_t find_match();
void print_lz77_encode_data();

window is a single array of size WINDOW_SIZE. The first SEARCH_BUFFER_SIZE slots act as the search buffer, and the remaining LOOK_AHEAD_BUFFER_SIZE slots act as the look-ahead buffer, there's no separate array for each, just one contiguous block that gets shifted.

Filling the look-ahead buffer for the first time

void init_look_ahead_buffer() {
    for (int i = SEARCH_BUFFER_SIZE, j = 0; i < WINDOW_SIZE; i++) {
        window[i] = data[j++];
    }
}

Before the first byte is ever encoded, the search buffer is empty (zero-initialized) and the look-ahead buffer is pre loaded with the first LOOK_AHEAD_BUFFER_SIZE bytes of input. This is why the very first tokens in any LZ77 stream are always literals, there's nothing in the search buffer yet to match against.

Finding the longest match

longest_match_t find_match() {
    int longest_match_len = 0;
    int longest_match_index = -1;
    int match_len = 0;
    for (int search_index = 0, look_ahead_index = SEARCH_BUFFER_SIZE;
         search_index < SEARCH_BUFFER_SIZE && look_ahead_index < WINDOW_SIZE;
         search_index++) {
        int s = search_index;
        int l = look_ahead_index;
        while ((window[s] == window[l]) && (s < SEARCH_BUFFER_SIZE) &&
               (l < WINDOW_SIZE)) {
            ++match_len;
            ++l;
            ++s;
        }
        if (match_len > longest_match_len) {
            longest_match_len = match_len;
            longest_match_index = search_index;
        }
        match_len = 0;
    }
    longest_match_t match;
    match.longest_match_index = longest_match_index;
    match.longest_match_len = longest_match_len;
    return match;
}

This is the brute-force part: for every single position in the search buffer, try to extend a match as far as possible into the look-ahead buffer, and remember whichever starting position produced the longest run. It always finds the correct longest match, the cost is that it tries every position, every time.

Sliding the window

bool shift_window(int skip) {
    if (data_pointer >= DATA_SIZE + LOOK_AHEAD_BUFFER_SIZE)
        return false;
    for (int i = 0, s = skip; s < WINDOW_SIZE; i++, s++)
        window[i] = window[s];
    for (int i = skip; i > 0; i--) {
        window[WINDOW_SIZE - i] = data[data_pointer];
        if (data_pointer >= DATA_SIZE + LOOK_AHEAD_BUFFER_SIZE) {
            return false;
        }
        ++data_pointer;
    }
    return true;
}

After a token is emitted, the window shifts left by skip positions, 1 for a literal, or match_length + 1 for a match (the "+1" accounts for the trailing character in the triple). Shifting left discards the oldest bytes from the search buffer and pulls fresh bytes from data[] into the tail of the look-ahead buffer, one byte at a time, until the whole window has moved forward.

Github link of above code [here]

Decoding LZ77 Output

Decoding is the cheap half of LZ77, and it's the reason the algorithm is so attractive: the decoder never has to search for anything. For each triple it reads, it does one of two things:

  1. If distance == 0, it's a literal, append character to the output and move on.
  2. Otherwise, it's a match, walk back distance bytes into the output that's already been produced, copy length bytes forward from there (appending as you go, so overlapping copies like distance 1 / length 5 correctly produce a run of the same byte repeated five times), then append the trailing character.

Because every copy source is data the decoder itself already reconstructed, decoding is a single linear pass with no comparisons and no searching, which is exactly why decompression is so much faster than compression for LZ77-family algorithms.

Why Naive LZ77 Is Slow

Look again at find_match() above. For every single byte position in the input, it walks the entire search buffer, and for every candidate position in the search buffer it walks forward comparing bytes until a mismatch. That's two nested loops running for every token the encoder emits.

In big-O terms, if W is the search buffer (window) size and L is the average match length being compared, a naive scan costs roughly O(W × L) per token, and O(n) tokens are emitted for an input of size n, so total work scales with O(n × W × L) in the worst case. For a toy 7-byte search buffer that's nothing. For a real-world compressor with a 32 KB window, like DEFLATE uses, that same brute-force approach means comparing against up to 32,768 candidate positions for every single output byte. That's the difference between a demo program and something you'd actually want to run on a multi-megabyte file.

The fix isn't a smarter comparison loop, it's avoiding most of the comparisons altogether by only checking positions that have a real chance of matching.

Speeding It Up With Hash Chains

The standard trick, used by zlib's DEFLATE implementation among others, is to index the search buffer by content instead of scanning it linearly. Every position in the window gets hashed based on its first few bytes, and the encoder only checks positions that hash to the same bucket as the current look-ahead data, because those are the only positions that could possibly produce a match of any useful length.

Hashing three bytes at a time

static inline size_t hash3(const byte *data, uint32_t pos, uint32_t data_len) {
    if (pos + MIN_MATCH_LENGTH > data_len) {
        return 0;
    }
    size_t hash = data[pos];
    hash = ((hash << HASH_SHIFT) ^ data[pos + 1]) & HASH_MASK;
    hash = ((hash << HASH_SHIFT) ^ data[pos + 2]) & HASH_MASK;
    return hash;
}

Since the minimum useful match length is 3 bytes (a shorter match wouldn't even beat the cost of encoding the triple itself), hashing exactly 3 bytes is enough to group positions that are worth comparing against.

A hash table of chains, not a single bucket

Multiple positions can share the same 3-byte hash, so each bucket doesn't store one position, it stores the most recent one, plus a link (prev) back to the position before it with the same hash, forming a chain:

static inline void hash_insert(hash_chain_t *hash_chain, const byte *data, uint32_t pos,
                                uint32_t data_len) {
    if (pos + MIN_MATCH_LENGTH > data_len)
        return;
    uint32_t hash          = hash3(data, pos, data_len);
    hash_chain->prev[pos]  = hash_chain->head[hash];
    hash_chain->head[hash] = (int)pos;
}

head[hash] always points to the newest position with that hash, and prev[pos] points to whatever used to be there before it, a classic linked list threaded through a plain array, which avoids any per-node allocation.

Walking the chain instead of the whole window

int32_t candidate = hash_chain->head[hash];
uint32_t chain_length = 0;
while (candidate != HASH_INIT_VALUE && chain_length < MAX_CHAIN_LENGTH) {
    chain_length++;
    if (data_pointer - candidate > SEARCH_BUFFER_SIZE || candidate >= data_pointer) {
        candidate = hash_chain->prev[candidate];
        continue;
    }
    // compare bytes starting at candidate against the look-ahead data
    candidate = hash_chain->prev[candidate];
}

Instead of checking every position in the window, the encoder now only checks positions that already share a 3-byte prefix with the current look-ahead data, and it stops after MAX_CHAIN_LENGTH candidates even if the chain is longer. That cap is the actual speed/ratio knob real compressors expose to you: zlib's compression levels 1 through 9 are, in large part, different values for exactly this kind of chain-length limit, a short chain is fast and settles for a decent match, a long chain is slower but more likely to find the best possible one.

On top of hash chains, production encoders typically add lazy matching: after finding a match at the current position, check whether starting one byte later would produce an even longer match, and if so, emit a literal now and take the better match next time. It's a small lookahead that often improves the ratio for a modest extra cost, and it's one of the reasons zlib's higher compression levels are noticeably slower than its lower ones.

LZ77 and the DEFLATE Algorithm

LZ77 by itself only removes redundancy that shows up as repeated sequences, it says nothing about how to pack the remaining literals and match parameters efficiently into bits. That's where DEFLATE comes in: DEFLATE is LZ77 (a 32 KB sliding window, LZSS-style output where matches shorter than 3 bytes are never emitted, hash-chain based match finding, and lazy matching) followed by Huffman coding of the resulting token stream. Literals, match lengths, and match distances each get their own Huffman-coded alphabet, so the back-references LZ77 produces are then compressed a second time on top of the first pass.

If you want the full breakdown of how the Huffman stage works and how the two techniques fit together bit-for-bit, see our DEFLATE algorithm article. DEFLATE itself is formally specified in RFC 1951, available at RFC 1951 – DEFLATE Compressed Data Format Specification.

It's worth being precise about where DEFLATE sits relative to related formats: zlib wraps a raw DEFLATE stream with a small header and an Adler-32 checksum (see our Adler-32 article for how that checksum is computed), while gzip and ZIP wrap the same raw DEFLATE stream with different headers and a CRC-32 checksum instead. In every case, the LZ77-plus-Huffman core doing the actual compression is the same algorithm.

Limitations of LZ77

LZ77 is fast to decode and conceptually simple, but it has real limits:

  1. The window is a hard horizon. A repeated phrase that first appeared further back than the window size simply cannot be referenced, DEFLATE's 32 KB window means anything beyond that distance has to be re-encoded from scratch, no matter how identical it is to something seen earlier.
  2. It does nothing for data without repeated sequences. High-entropy or already-compressed data (encrypted files, JPEGs, previously zipped archives) has few or no matches to find, so LZ77 degenerates into mostly literal tokens and buys you little to nothing.
  3. Greedy matching isn't always optimal. Taking the longest match available right now can sometimes block an even better match one byte later, which is exactly the gap that lazy matching exists to close, at the cost of extra search work.

This is why later algorithms extended the same core idea rather than replacing it: LZMA uses a much larger window (often measured in hundreds of megabytes) and a range coder instead of Huffman coding, Brotli adds a static dictionary of common byte sequences, and Zstandard pairs a large window with a modern entropy coder (FSE/ANS) and highly tuned match finders. All of them are still, at heart, doing what Lempel and Ziv described in 1977: find what you've already seen, and stop paying to store it twice.

Conclusion

LZ77 reduces to one repeated question, asked at every position in the input: "have I seen this before, and if so, where?" The sliding window defines how far back the algorithm is allowed to look, and the distance/length/character triple is simply the answer written down in a compact form.

The naive brute-force search answers that question correctly but slowly, checking every candidate in the window one by one. Hash chains answer the same question by only checking candidates that already share a real prefix with the data you're trying to match, which is the difference between an encoder that's fine for a 17-byte demo and one that can compress megabytes per second.

A quick way to decide which version of this idea fits your situation:

  • For learning the algorithm or matching it against a spec by hand, the brute-force window scan is the clearest implementation to read and trust.
  • For anything that has to compress real files at real speed, hash chains (or an even richer structure like a binary tree or suffix array) aren't optional, they're what makes the search sub-quadratic.
  • For the best possible ratio regardless of window size, look past classic LZ77 to its descendants, LZMA, Brotli, or Zstandard, which keep the same back-reference idea but remove the constraints that a 1977 algorithm had to accept.

Once you see LZ77 as "hash the recent past, then reference it instead of repeating it," the rest of the compression landscape, DEFLATE, gzip, PNG, LZMA, reads less like a pile of separate formats and more like variations on the same one idea.