LZ77

LZ77
This is an important and widely-used example of adictionary compression algorithm.These algorithms replace entire strings of characters by a single token – only the most common strings are
represented by these tokens (which are maintained in a
dictionary!).LZ77 was invented by Abraham Lempel and Jacob Ziv in
1977 and forms the basis for the gzip utility...

LZ77
This is achieved by considering the data to be encoded as a
stream...As the stream of data passes through the encoder parts
of it are stored in two buffers:the history buffer stores the symbols that have just been encoded (typically the last few thousand),
the lookahead buffer stores the next few symbols about to be encoded (typically 20 or so). If any string of characters in the lookahead buffer already appears in the history buffer then it is encoded by a token which points to the position in the history
buffer where that string can be found!

LZ77 Example
To illustrate the LZ77 sliding window:
COMPRESS_DATA_USING_DATA_COMPRESSION
COMPRESS_DATA_USING[11,6][25,8]ION

Notes on LZ77
Note that we do not discuss implementation details for
this algorithm here – just the overall idea: see http://www.data-compression.com/lossless.html if you are interested in the detail (contains an animation too).
There is a start up cost associated with filling the history buffer.
It is not worth encoding strings of just two or three characters: usually the minimum length worth encoding
is 4 ASCII characters.