LZ 78-Students Report

The LZ78 Approach
The LZ77 approach implicitly assumes that like patterns will occur close together. It makes
use of this structure by using the recent past of the sequence as the dictionary for encoding.
However, this means that any pattern that recurs over a period longer than that covered by the
coder window will not be captured. The worst-case situation would be where the sequence to
be encoded was periodic with a period longer than the search buffer. Consider Figure 5.5.
This is a periodic sequence with a period of nine. If the search buffer had been just one
symbol longer, this sequence could have been significantly compressed. As it stands, none
of the new symbols will have a match in the search buffer and will have to be represented by
separate codewords. As this involves sending along overhead (a 1-bit flag for LZSS and a triple
for the original LZ77 algorithm), the net result will be an expansion rather than a compression.
a b c d e f g h i a b c d e f g h i a b c d e f g h i
Search buffer Look ahead buffer
F IGU R E 5 . 5 The Achilles’ heel of LZ77.
144 5 D I C T I O N A R Y T E C H N I Q U E S
T A B L E 5 . 4 The initial dictionary.
Index Entry
1 w
2 a
3 b
Although this is an extreme situation, there are less drastic circumstances in which the finite
view of the past would be a drawback. The LZ78 algorithm solves this problem by dropping
the reliance on the search buffer and keeping an explicit dictionary. This dictionary has to be
built at both the encoder and decoder, and caremust be taken that the dictionaries are built in an
identical manner. The inputs are coded as a double i, c, with i being an index corresponding
to the dictionary entry that was the longest match to the input and c being the code for the
character in the input following the matched portion of the input. As in the case of LZ77, the
index value of 0 is used in the case of no match. This double then becomes the newest entry in
the dictionary. Thus, each new entry into the dictionary is one new symbol concatenated with
an existing dictionary entry. To see how the LZ78 algorithm works, consider the following
example.