What you're seeing
LZ77 compresses by noticing that text repeats itself. It keeps a window of recently-seen characters; at each position it looks at what comes next and searches the window for the longest stretch that matches. When it finds one, instead of writing those characters again it writes a back-reference: "go back offset characters and copy length of them." Each step emits one token — (offset, length, next-char) — covering the matched run plus the single character that broke the match. No dictionary is stored or shipped; the window is the dictionary, and it's rebuilt identically while decoding. Watch repeats fold into short pointers as the window slides right.
The rule
i = 0
while i < n:
find the longest text[i..i+L) that also occurs
starting somewhere in the window [i−W, i)
emit token (offset = i − match_start, length = L, next = text[i+L])
i += L + 1
# decode: for each token, copy L chars from `offset` back, then append `next`
The invariant
The guarantee is simply that it's lossless: decoding the token stream reproduces the input exactly, byte for byte. That holds because a token only ever points backward, into text the decoder has already reconstructed — so when it needs to copy length characters from offset back, those characters are guaranteed to already be there. The decoder rebuilds the very same window the encoder saw, in lockstep, so a pointer means the same thing on both sides. A lovely subtlety: a match may overlap the cursor (offset < length), e.g. copying "a" repeatedly to spell "aaaaa" — and copying one character at a time still works, because each copied character is produced just before the next one reads it. That's run-length encoding falling out of LZ77 for free.
The cost
The cost is all in finding the matches: scanning a window of size W at every position is O(nW) naively, but real encoders index the window with hash chains or suffix structures to find matches in near-constant time, making encoding roughly linear; decoding is always a fast linear copy. Compression improves with a larger window (more chances to find a match) at the cost of slower search and bigger offsets — the classic time/ratio knob. LZ77 alone shrinks repetition but leaves the tokens themselves uncompressed, which is why it's paired with an entropy coder.
In the wild
LZ77 is one of the most consequential algorithms in computing. With Huffman coding layered on top it is DEFLATE — the engine of gzip, zlib, PNG, and ZIP. Its sibling LZ78 and the LZW variant powered GIF and Unix compress; LZMA (7-Zip), LZ4, Snappy, and Zstandard are all descendants of the same back-reference idea, trading off speed against ratio. Essentially every general-purpose compressor you use today has an LZ77-style match-finder at its core; Lempel and Ziv's 1977–78 papers earned them the IEEE Richard W. Hamming Medal (2007), and Jacob Ziv the IEEE Medal of Honor (2021).
Try this
Watch the token count versus the character count in the readout: on repetitive text it drops well below 1 token per character. Shrink the Window size and compression worsens — distant repeats fall out of view and become literals again; widen it and more matches reappear. Look for an overlapping match (a long run from a small offset): that's run-length encoding emerging from the same machinery.
References
- Ziv, J. & Lempel, A. "A Universal Algorithm for Sequential Data Compression." IEEE Transactions on Information Theory 23(3):337–343, 1977. (LZ77.)
- Ziv, J. & Lempel, A. "Compression of Individual Sequences via Variable-Rate Coding." IEEE Transactions on Information Theory 24(5):530–536, 1978. (LZ78, the dictionary sibling.)
- Deutsch, P. "DEFLATE Compressed Data Format Specification version 1.3." RFC 1951, 1996 — LZ77 + Huffman as shipped in gzip/zlib/PNG.
- Salomon, D. Data Compression: The Complete Reference, 4th ed. Springer, 2007.