Data Compression Lec#12

Dictionary Methods
LZ78
The LZ78 method (which is sometimes referred to as LZ2) [Ziv and Lempel
78] does not use any search buffer, look-ahead buffer, or sliding window.
Instead, there is a dictionary of previously encountered strings. This
dictionary starts empty (or almost empty).
The encoder outputs two-field tokens. The first field is a pointer to the
dictionary; the second is the code of a symbol. Tokens do not contain the
length of a string, since this is implied in the dictionary. Each token
corresponds to a string of input symbols, and that string is added to the
dictionary after the token is written on the compressed stream.
The dictionary starts with the null string at position zero. As symbols are
input and encoded, strings are added to the dictionary at positions 1, 2, and
so on. When the next symbol x is read from the input stream, the dictionary
is searched for an entry with the one-symbol string x. If none are found, x is
added to the next available position in the dictionary, and the token (0, x) is
output. This token indicates the string “null x”(a concatenation of the null
string and x). If an entry with x is found (at, say, position 37), the next symbol
y is read, and the dictionary is searched for an entry containing the twosymbol
string xy. If none are found, then string xy is added to the next
available position in the dictionary, and the token (37, y) is output. This token
indicates the string xy, since 37 is the dictionary position of string x. The
process continues until the end of the input stream is reached.