The LZ77 Compression Algorithm
Introduction to LZ77
LZ77 is a lossless compression algorithm first published by two Israeli researchers in 1977. It is a classic dictionary-based compression algorithm, and today almost all lossless compression algorithms are built on LZ77, optimizing and modifying it in various ways. It can fairly be called the ancestor of lossless compression algorithms.
See Wikipedia: lz77
How the algorithm works
The core of LZ77 is a sliding window: it searches for repeated bytes within the window and represents each matched byte string with a shorter byte sequence.
Several elements are involved:
- The sliding window buffer
- The look-ahead region of the window
- The already-encoded region of the window
Encoding
Encoding steps:
- First allocate a buffer to process the data
- The look-ahead region starts empty
- The encoded region also starts empty
- Load the byte stream into the look-ahead region; if this is the last byte, go to step 8, otherwise continue to step 5
- Search the encoded region for a matching byte string; if found, go to step 6, otherwise go to step 7
- Record the relative position of the first matched byte and the match length in the encoded region, then go back to step 4
- Copy the byte from the look-ahead region directly into the encoded region, then go back to step 4
- Encoding finished
Encoding diagrams:
Before the sliding window has processed any data:

When the sliding window starts processing data:

While the sliding window is processing data:

When the data is almost fully processed:

The whole process looks as if the byte stream flows through the black box of the sliding window, and what comes out the other side is compressed data.
Encoding involves deciding how to mark data. In this LZ77 implementation, 2–3 bytes are used: if two bytes are both '\0', it denotes a literal byte copied directly, and the byte following the two '\0' bytes is the original byte; otherwise, those two bytes encode the relative position and length of the byte string that should be filled in at the current position. (You can even define your own marking scheme for your own LZ77 encoder.)
Decoding
Decoding is the inverse of encoding.
Decoding steps:
-
If the byte stream is at its last byte, go to step 5, otherwise go to step 2
-
Read two bytes from the stream; if they are
\0x00\0x00, go to step 3, otherwise go to step 4 -
Copy the byte following
\0x00\0x00into the output buffer, continue loading the stream, and go back to step 1 -
Extract the relative offset within the sliding window and the content length from the two-byte code, copy the content at that offset into the current output buffer, and go back to step 1
-
Decoding finished
The output buffer above is the buffer that holds the byte stream after it has been processed at the current byte position.
Decoding diagrams:
Before the sliding window has any input data:

When the sliding window starts processing data:

While data is being processed in the sliding window:

When the data is almost fully processed:

Source code
Helper function:
unsigned int search_maxlen_p( unsigned char** pt, \
unsigned char* head, \
unsigned char* tail, \
unsigned char* end)
{
unsigned char* tmp = *pt;
unsigned int leng = 0, i;
for(tmp;tmp >= head;tmp--){
if(tmp[0] == tail[0]){
for(i = 0;(i < ((1 << LENGTHBITS) - 1)) && (&tmp[i] > head) && (&tmp[i] < tail) && (&tail[i] < end) && (tmp[i] == tail[i]);i++);
if(i > leng){
leng = i;
*pt = tmp;
}
}
}
return leng;
}
Encoder:
int lz77_encode(FILE* in,FILE* out)
{
unsigned char* buf = 0,* head = 0,* tail = 0;
long size = 0;
if(! in || ! out)return 1;
get_filesize(in,size); // get file size.
if(size <= 0)return 1;
buf = (unsigned char*)malloc(size* sizeof(unsigned char)); // allocate memory.
if(! buf)return 1;
if(fread(buf,sizeof(unsigned char),size,in) == size){
head = tail = buf;
fputc((size >> 24) & 0xff,out);
fputc((size >> 16) & 0xff,out);
fputc((size >> 8) & 0xff,out);
fputc((size >> 0) & 0xff,out);
for(;;){ // loop block.
head = tail - WINDOWSIZE;
if(buf > head)head = buf;
if(tail > buf + size - 1)break;
if(tail > head){
unsigned char* pt = tail - 1;
unsigned int bytes = 0;
bytes = search_maxlen_p(&pt,head,tail,buf + size);
// search maximal matched bytes and position.
if(bytes > 0){
unsigned char chars[2] = {0};
chars[0] = (unsigned char)(( (tail - pt) >> LENGTHBITS) & 0xff);
chars[1] = (unsigned char)((((tail - pt) << LENGTHBITS) + bytes) & 0xff);
fputc(chars[0],out);
fputc(chars[1],out);
//fprintf(stderr,"{%d - %d}",tail - pt,bytes);
tail += bytes;
} else {
fputc(0,out);
fputc(0,out);
fputc(*tail,out);
tail++;
}
} else {
fputc(0,out);
fputc(0,out);
fputc(*tail,out);
tail++;
}
}
}
free(buf);
return 0;
}
Decoder:
int lz77_decode(FILE* in,FILE* out)
{
unsigned char* nbuf = 0,* ori_buf = 0,* head = 0,* tail = 0;
long ori_size = 0,nsize = 0;
if(! in || ! out)return 1;
get_filesize(in,nsize); // get file size.
if(nsize <= 0)return 1;
ori_size = (fgetc(in) & 0xff) << 24;
ori_size += (fgetc(in) & 0xff) << 16;
ori_size += (fgetc(in) & 0xff) << 8;
ori_size += (fgetc(in) & 0xff) << 0;
if(ori_size <= 0)return 1;
nbuf = (unsigned char*)malloc(nsize* sizeof(unsigned char));
if(! nbuf)return 1;
ori_buf = (unsigned char*)malloc(ori_size* sizeof(unsigned char));
if(ori_buf){
head = tail = ori_buf; // store head and tail of slide-window.
if(fread(nbuf,sizeof(unsigned char),nsize,in) == (nsize - 4)){
unsigned char* pt = nbuf;
for(;;){
if(pt >= (nbuf + nsize - 4))break;
if(! pt[0] && ! pt[1] ){ // \0\0\?
tail[0] = pt[2];
tail++;
pt += 3;
} else { // \?\?
unsigned int offset = 0,length = 0,i;
offset = pt[0] << LENGTHBITS;
offset += (pt[1] >> LENGTHBITS) & 0x0f;
length = pt[1] & 0x0f;
//fprintf(stderr,"{%d - %d}",offset,length);
for(i = 0;i < length;i++){
tail[i] = ((unsigned char*)(tail - offset))[i];
}
tail += length;
pt += 2;
}
}
fwrite(ori_buf,sizeof(unsigned char),ori_size,out);
}
free(ori_buf);
}
free(nbuf);
return 0;
}
Analysis
When analyzing how efficiently this algorithm compresses data, it clearly depends on the content. Content with high repetition at short distances compresses well, but content with little repetition may not reach a good ratio. In the worst case, the data has no repeats at all within a window-sized span, and the "compressed" output is not only not smaller but grows to three times the original size.
In the data below, you can see that the non-repeating leading portion contains many literal copies starting with "\0x00\0x00"; too much of this makes compression inefficient.

Generally, to offset this weakness, LZ77-compressed data can be encoded again with Huffman coding, which yields a higher overall compression ratio.
Link: Code on GitHub