Data Compression Lec#13

LZW
This is a popular variant of LZ78, developed by Terry Welch in 1984 ([Welch 84] and
[Phillips 92]). Its main feature is eliminating the second field of a token. An LZW token
consists of just a pointer to the dictionary. To best understand LZW, we will temporarily
forget that the dictionary is a tree, and will think of it as an array of variable-size strings.
The LZW method starts by initializing the dictionary to all the symbols in the alphabet.
In the common case of 8-bit symbols, the first 256 entries of the dictionary (entries 0
through 255) are occupied before any data is input. Because the dictionary is initialized,
the next input character will always be found in the dictionary. This is why an LZW
token can consist of just a pointer and does not have to contain a character code as in
LZ77 and LZ78.
(LZW has been patented and for many years its use required a license. This issue
is discussed in Section 3.30.)
The principle of LZW is that the encoder inputs symbols one by one and accumulates
them in a string I. After each symbol is input and is concatenated to I, the
dictionary is searched for string I. As long as I is found in the dictionary, the process
continues. At a certain point, adding the next symbol x causes the search to fail; string
I is in the dictionary but string Ix (symbol x concatenated to I) is not. At this point
the encoder (1) outputs the dictionary pointer that points to string I, (2) saves string
Ix (which is now called a phrase) in the next available dictionary entry, and (3) initializes
string I to symbol x. To illustrate this process, we again use the text string
sirsideastmaneasilyteasesseasickseals. The steps are as follows:
0. Initialize entries 0–255 of the dictionary to all 256 8-bit bytes.
1. The first symbol s is input and is found in the dictionary (in entry 115, since this is