 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:
- a search buffer that contains a portion of the recently encoded sequence, and
- 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
|
|