LZ77

05 Sep 2026

Jacob Ziv and Abraham Lempel were both faculty at the Technion in Haifa, Israel, when in 1977 they published a paper called A Universal Algorithm for Sequential Data Compression in which they described a compression algorithm which, unlike Huffman coding, doesn’t rely on knowing the frequency of symbols upfront.

Ziv was an information theorist from the Electrical Engineering department while Lempel was part of the Computer Science department. They met due to their interest in lossless compression and Ziv said [1] that their skills complemented each other well:

I knew all about information theory and statistics, and Abraham was well-equipped in Boolean algebra and computer science.

This algorithm is now known as LZ77 (their last name initials + the year the paper was published). A popular algorithm called DEFLATE combines LZ77 with Huffman and is used by tons of software including gzip, git, png, etc.

In this post we’ll cover the LZ77 algorithm.

Intuition

Suppose we have a programming language with only two instructions: literal <symbol> and copy <rewind> <length>. The program starts with an empty output buffer. The instruction literal <symbol> adds <symbol> to the buffer. copy moves the cursor back <rewind> positions and copies the symbol under the cursor to the end of output <length> times.

Let’s do an example:

literal a; // a
literal b; // ab
literal c; // abc
copy 2 1;  // abcb
copy 2 2;  // abcbcb

The comments explain what’s going on. For the literals, we see it’s just adding symbols to the end of the output. For copy 2 1, we rewind the cursor to a[b]c and then copy it to the output abcb. We now rewind the cursor to ab[c]b and then copy the next two symbols to the end, abcbcb.

Here’s another example to highlight the overlap effect:

literal a; // a
literal b; // ab
literal c; // abc
copy 3 6;  // abcabcabc

The literals are the same as before. When we get to copy 3 6, and rewind 3 positions we have [a]bc. How is it possible to have <length> > <rewind>? The key thing is that we’re moving the cursor on a string that is growing at the same time, so when we add a to the output, we end up with a[b]ca, then ab[c]ab, then abc[a]bc, abca[b]ca, abcab[c]ab and finally abcabc[a]bc.

It would be a bit clearer if this language had, say, a rewind <rewind> command that moved the cursor <rewind> positions back and copy just copied the current symbol to the end and moved the cursor by one unit. Then our previous example would be:

literal a; // a[]
literal b; // ab[]
literal c; // abc[]
rewind 3;  // [a]bc
copy;      // a[b]ca
copy;      // ab[c]ab
copy;      // abc[a]bc
copy;      // abca[b]ca
copy;      // abcab[c]ab
copy;      // abcabc[a]bc

But this version is much more verbose. Even the original one we provided is very verbose. We can get away with having the literals as a single string, abc in our example, and copy now takes 3 arguments: lit_cnt, length and rewind. The only new one is lit_cnt which counts after how many literal instructions we inject this copy.

The previous example could be encoded as:

literal abc;
copy 3 6 3;

We’re basically saying the copy appears after all 3 literals which is not very instructive. Let’s consider a more complicated example with literal and copy interleaved:

literal a; // a
literal b; // ab
copy 2 2;  // abab
literal c; // ababc
copy 4 3;  // ababcbab
literal d; // ababcbabd

This could be represented more compactly as

literal abcd;
copy 2 2 2;  // inserted after 2 literals: a and b
copy 1 3 4;  // inserted after 1 literal: c

This is essentially the LZ77 encoding! The decoding part consists in “running” this program. The tricky part is the encoding, so let’s cover that.

Encoding

We’ll start with a greedy algorithm. We iterate over each character on the input. At a given position i, we try rewinding r positions and find the maximum prefix between a string starting at i and at i - r.

If the longest prefix found is at least 3 (this is because each copy requires 3 integers, so to be worth using it it must replace at least 3 characters) we emit a copy command for that prefix. Otherwise we emit the current position i as a literal.

In Python it could look like this:

def longest_prefix(s, i, j):
    """
    Finds the length of the longest common prefix
    between s[i:] and s[j:]. Assumes i >= j
    """
    p = 0
    while i + p < len(s) and s[i + p] == s[j + p]:
        p += 1
    return p

def best_rewind(s, i):
    """
    Finds the r such that the longest common prefix between
    s[i:] and s[i-r:] is the longest. Return r and the prefix
    length.
    """
    best_l = 0
    best_r = -1

    for r in range(1, i + 1):
        l = longest_prefix(s, i, i - r)

        if l > best_l:
            best_l = l
            best_r = r

    return best_r, best_l

def encode(input):
    i, prev_i = 0, 0
    lits, cps = '', []

    while i < len(input):

        best_r, best_l = best_rewind(input, i)

        if best_l >= 3:
            cps.append((i - prev_i, best_l, best_r))
            prev_i = i
            i += best_l

        else:
            lits += input[i]
            i += 1

    return lits, cps

The comments and code are easy to follow. The only observation is that when we append the triple (i - prev_i, best_l, best_r), we don’t store the current length of the literals but how many literals appeared between the current copy instruction and the previous one.

If $n$ is the length of the input, this algorithm is $O(n^3)$ in the worst case. We can bound this complexity by capping how far back we rewind in best_rewind() by changing:

for r in range(1, i + 1):
  ...

for r in range(1, min(i + 1, window)):
  ...

There’s another practical consideration in that we can’t afford to load the entire input into memory, so we can’t look forward or backward too far, so we can also limit how far longest_prefix() scans.

Decoding

Decoding is a bit simpler. As we discussed, it consists in running the program:

def decode(lits, cps):
    out = ''
    prev = 0
    for cnt, l, r in cps:
        out += lits[prev:prev + cnt]
        prev += cnt

        for _ in range(l):
            out += out[len(out) - r]

    out += lits[prev:]
    return out

Note that inside the innermost loop, len(out) changes as we append characters to it.

As for complexity, decoding is linear on the output, which we must emit anyway, so we can’t expect to do better than that.

Composition

As we mentioned at the start, LZ77 is typically not used on its own but rather combined with other encoders for further compression. We cover two popular composite encoders that use LZ77: DEFLATE and zstd.

At a very high level, DEFLATE applies LZ77 but uses the less compact form, the one that interleaves literals and the copy instructions. It counts the frequency of symbols and instructions on this output and then it applies Huffman coding.

The zstd algorithm applies LZ77 first using the compact form. It then either uses run-length encoding or Huffman coding for the literals and a variant of ANS called FSE (Finite State Entropy) for the copy instructions.

LZW

When I ran into LZ77, I could swear I had heard of Lempel Ziv before. Doing some searches on my email, I found that I had implemented the algorithm Lempel-Ziv-Welch or LZW in 2006, in assembly, for a class in college. I had no recollection of this implementation.

This is funny because when I first saw LZ77 encoding framed as a programming language with instructions literal and copy it reminded me of Assembly.

There’s an interesting story behind LZW. Lempel and Ziv improved upon LZ77 in 1978 and named it LZ78. In 1983, Terry Welch improved on LZ78 and called it LZW. Welch did so while working at Sperry Corporation, later Unisys, who patented the algorithm.

In 1987 CompuServe released the image format GIF, which used LZW. In 1994 Unisys started requiring software developers implementing LZW to pay license fees. Creating or distributing GIF images was not subject to this.

In 1993 Phil Katz invented the DEFLATE algorithm. As a response to the LZW controversy, the PNG image format was created in 1995 which used DEFLATE for compression. The patent for LZW expired in 2003 but due to the licensing requirements and DEFLATE’s better compression LZW isn’t widely adopted.

Conclusion

There are many tweaks and optimizations (e.g. not loading the entire input into memory) we can do but my main goal was to have a high level understanding of how LZ77 works! My main objective was to get a better sense of what goes into zstd.

References

[1] IEEE Spectrum: Remembering Data Compression Pioneer Jacob Ziv.

It’s interesting that both LZW and Asymmetric Numeral Systems have some drama around patents. Encoders have an interesting trait that make them subject to this: once you use a given encoder, you are required to use the corresponding decoder. Another factor seems to be that encoding is low-level enough to be implemented in hardware, which has a stronger precedence of patenting vs. algorithms in general that cannot be patented because they’re abstract ideas.

If we look at the patent it’s actually describing hardware:

See caption. — Figure 1: Page 3 of the LZW patent.

In the post Tree Ring Matching using the KMP Algorithm we’re trying to solve the problem of finding the largest overlap between a suffix and prefix of two strings. This is similar to finding the largest overlap between the prefixes in longest_prefix().

The LZ77 reminds me both of the KMP algorithm mentioned above and the Aho-Corasick where we have to efficiently find patterns in the input text.

| Tags: data structures