maintitle.gif (26398 bytes)
menu_intro.gif (1886 bytes)
menu_bar_77.GIF (1845 bytes)
 
lossless.jpg (77783 bytes)

Dictionary-based Compressors
Concept
Algorithm
Example
Shortcomings
Variations

The Concept

Lempel-Ziv 77 (LZ77) algorithm is the first Lempel-Ziv compression algorithm for sequential data compression. The dictionary is a portion of the previously encoded sequence. The encoder examines the input sequence through a sliding window as shown in Figure 9. The window consists of two parts:

    1. a search buffer that contains a portion of the recently encoded sequence, and
    2. a look-ahead buffer that contains the next portion of the sequence to be encoded.

In the diagram below, the search buffer contains eight symbols (in blue), while the look-ahead buffer contains nine symbols (in red). In practice, the sizes of the buffers are significantly larger.

 

search buffer

look-ahead buffer

   

…a

c

c

a

b

r

a

c

a

d

a

b

r

a

r

r

a

r

r

a

c…

 

 

back to top | home