انت هنا الان : شبكة جامعة بابل > موقع الكلية > نظام التعليم الالكتروني > مشاهدة المحاضرة

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.