Data Compression Lec#11 PowerPoint

LZ77 (Sliding Window)
The principle of this method (which is sometimes referred to as LZ1) [Ziv and Lempel
77] is to use part of the previously-seen input stream as the dictionary. The encoder
maintains a window to the input stream and shifts the input in that window from right
to left as strings of symbols are being encoded. Thus, the method is based on a sliding
window. The window below is divided into two parts. The part on the left is the search
buffer. This is the current dictionary, and it includes symbols that have recently been
input and encoded. The part on the right is the look-ahead buffer, containing text yet to
be encoded. In practical implementations the search buffer is some thousands of bytes
long, while the look-ahead buffer is only tens of bytes long. The vertical bar between
the t and the e below represents the current dividing line between the two buffers. We
assume that the text sirsideastmaneasilyt has already been compressed, while
the text easesseasickseals still needs to be compressed.
? coded text. . . sirsideastmaneasilyt|easesseasickseals. . .? text to be read
The encoder scans the search buffer backwards (from right to left) looking for a
match for the first symbol e in the look-ahead buffer. It finds one at the e of the word
easily. This e is at a distance (offset) of 8 from the end of the search buffer. The
encoder then matches as many symbols following the two e’s as possible. Three symbols
eas match in this case, so the length of the match is 3. The encoder then continues the
backward scan, trying to find longer matches. In our case, there is one more match, at
the word eastman, with offset 16, and it has the same length. The encoder selects the
longest match or, if they are all the same length, the last one found, and prepares the
token (16, 3, e).
Selecting the last match, rather than the first one, simplifies the encoder, because it
only has to keep track of the last match found. It is interesting to note that selecting the
first match, while making the program somewhat more complex, also has an advantage.
It selects the smallest offset. It would seem that this is not an advantage, because a token
should have room for the largest possible offset. However, it is possible to follow LZ77
with Huffman, or some other statistical coding of the tokens, where small offsets are
assigned shorter codes. This method, proposed by Bernd Herd, is called LZH. Having
many small offsets implies better compression in LZH.