# - Acharya T.

ISBN 0-471-48422-9

**Download**(direct link)

**:**

**24**> 25 26 27 28 29 30 .. 100 >> Next

S =bacababbaabbabbaaacbbc

Initially the dictionary is empty. Since the first input symbol b has no match in the dictionary, the encoder outputs the pair < 0, C(b) > and inserts the first entry b into the dictionary with index 1 as shown in Table 2.5.

Similarly, the next input symbol a has no match in the dictionary and hence the encoder outputs the pair < 0, C(a) > and inserts new entry a at index 2 in the dictionary as shown in Table 2.6.

ZIV-LEMPEL CODING 47

Table 2.5 Dictionary After Step 1

Encoder Output Index Entry

< 0,C(b) > 1 b

Table 2.6 Dictionary After Step 2

Encoder

Output Index Entry

<0,C(t>) > 1 b

< 0, C(a) > 2 a

Similarly, the next input symbol c has no match in the dictionary and hence the encoder outputs the pair < 0, C(c) > and inserts the new entry c at index 3 as shown in Table 2.7.

Table 2.7 Dictionary After Step 3

Encoder

Output Index Entry

< 0 ,C(b) > 1 b

< 0, C(a) > 2 a

< 0, C(c) > 3 c

The next input symbol a matches with entry 2 in the dictionary, but a b does not have any match. So the encoder outputs the pair < 2, C(b) > and inserts new entry a b at index 4 in the dictionary as shown in Table 2.8.

Table 2.8 Dictionary After Step 4

Encoder Output Index Entry

< 0,C(b) > 1 b

< 0, C(a) > 2 a

< 0,C(c) > 3 c

< 2 ,C(b) > 4 a b

48 SOURCE CODING ALGORITHMS

The next two symbols ab match with entry 4 in the dictionary, but abb does not have any match. So the encoder outputs the pair < 4, C(b) > and inserts a new entry abb at index 5 in the dictionary as shown in Table 2.9.

Table 2.9 Dictionary After Step 5

Encoder Output Index Entry

< 0,C(b) > 1 b

< 0,C(a) > 2 a

< 0, C(c) > 3 c

< 2, C(b) > 4 a b

< 4, C(b) > 5 abb

Continuing the above procedure, the encoder generates the output pairs

< 2, C(a) >, < 1, C(b) >, < 5, C(a) >, < 6, C(c) >, and < 7, C(c) > and builds the dictionary accordingly. The final dictionary is shown in Table 2.10 below.

Table 2.10 Final Dictionary

Encoder Output Index Entry

< 0, C(b) > 1 b

< 0, C(a) > 2 a

< 0,C(c) > 3 c

< 2,C(b) > 4 a b

< 4, C(b) > 5 abb

< 2, C(a) > 6 a a

< 1 ,C(b) > 7 bb

< 5, C(a) > 8 abba

< 6, C(c) > 9 aac

< 7, C(c) > 10 bbc

As a result, the sequence S = bacababbaabbabbaaacbbc is encoded as < 0, C(b) >, < 0, C(a) >, < 0, C(c) >, < 2, C(b) >, < 4, C(b) >,

< 2, C(a) >, < 1, C{b) >, < 5, C{a) >, < 6, C(c) >, < 7, C(c) >.

2.5.2.2 Exampleâ€”LZ78 Decoding: We now decode the encoded data to explain how the LZ78 decoding process works. As with the encoder, the decoder also dynamically builds the dictionary. This dictionary is the same as the one built by the encoder. Initially the dictionary contains nothing. Since the first input pair to the decoder is < 0, C(b) >, the decoder first decodes the symbol b from the codeword C(b). Since the decoded index is 0, it outputs

ZIV-LEMPEL CODING 49

the symbol b and inserts the first entry < 1,6 > in the dictionary same as shown in Table 2.5.

The next input pair to the decoder is < 0, C(a) >. As result, the decoder outputs the symbol a and inserts the next entry < 2, a > in the dictionary, same as shown in Table 2.6. The following input pair is < 0, C(c) > and hence the decoder outputs the symbol c and inserts the next entry < 3, c > in the dictionary, same as shown in Table 2.7.

The next input pair is < 2, C(b) >, which indicates that the new output is the pattern for entry 2 in the dictionary concatenated by the decoded symbol b. Since entry 2 represents a, the output will b eat. A new pattern a b is now inserted at index 4 in the dictionary.

The following input pair is < 4, C(b) >. As a result the decoder outputs the string abb and inserts it in the dictionary in entry 5. The decoder similarly reads the next pair < 2, C(a) > and generates the output a a and inserts it in the dictionary in entry 6. Continuing in the similar fashion, the following decoder outputs are bb, abba, aac, and bbc respectively. The final dictionary should also be identical to the one in Table 2.10. Hence the final decoder output is bacababbaabbabbaaacbbc and it exactly matches with the original input sequence.

There are a number of variations of the LZ78 algorithm. The most popular variation of LZ78 is the algorithm by Welch [12], popularly known as LZW algorithm.

2.5.3 The LZW Algorithm

In the LZ78 encoding algorithm, inclusion of the explicit codeword C(S) of the symbol S along with the index i in the output < i,C(S) > is often very wasteful. In LZW algorithm, this inefficiency has been overcome by removing the inclusion of C(S) and transmitting the index i only. This is accomplished by initializing the dictionary with a list of single symbol patterns to include all the symbols of the source alphabet. In each step, the index of the longest match from the input in the dictionary is output and a new pattern is inserted in the dictionary. The new pattern is formed by concatenating the longest match with the next character in the input stream. As a result, the last symbol (or character) of this new pattern is encoded as the first character of the next one.

**24**> 25 26 27 28 29 30 .. 100 >> Next