Books
in black and white
Main menu
Home About us Share a book
Books
Biology Business Chemistry Computers Culture Economics Fiction Games Guide History Management Mathematical Medicine Mental Fitnes Physics Psychology Scince Sport Technics
Ads

- Acharya T.

Acharya T. - John Wiley & Sons, 2000. - 292 p.
ISBN 0-471-48422-9
Download (direct link): standardforImagecompressioncon2000.pdf
Previous << 1 .. 19 20 21 22 23 24 < 25 > 26 27 28 29 30 31 .. 100 >> Next

2.5.3.1 Example—LZW Encoding: The LZW encoding algorithm is explained below with an example to encode the string babacbabababcb.
The dictionary generation is shown in Table 2.11. Initially, the dictionary consists of single symbol (or character) patterns a, b, and c from the input alphabet {a, b, c}. The indexes of the patterns in the dictionary are 1, 2, and 3 respectively.
After receiving the first character b, the encoder finds the match at index
2. But the pattern ba with first two characters does not have a match in
50 SOURCE CODING ALGORITHMS
Table 2.11 LZW Dictionary
Index Pattern Derived as
1 a
2 b initial
3 c
4 b a 2 + a
5 a b 1 + b
6 bac 4 + c
7 cb 3 + 6
8 bab 4 + 6
9 baba 8 + a
10 abc 5 + c
the current dictionary. Hence the encoder outputs index 2 to encode the first character 6 and inserts the new pattern ba to index 4 in the dictionary.
The second input character a has a match in the dictionary to index 1, but ab formed by the second and third characters does not have a match. As a result the encoder outputs index 1 to encode a and inserts the new pattern a b in the dictionary to index 5.
Now the next two characters ba match with the pattern to index 4, but bac does not have a match. Hence the encoder outputs index 4 to encode ba and inserts the new pattern bac in the dictionary to index 6.
The next character c now matches with index 3, but cb does not. Hence the encoder outputs index 3 to encode c and inserts cb in the dictionary to index 7.
The next two characters ba have a match at index 4, but bab does not. Hence the encoder outputs the index 4 to encode ba and inserts the new pattern bab in the dictionary to index 8.
The next three characters bab have a match in the dictionary to index 8, but baba does not. Hence the encoder now outputs the index 8 to encode bab and inserts the new pattern baba in the dictionary to index 9.
The next two characters ab now match with the pattern at index 5 in the dictionary, but abc does not. Hence the encoder outputs index 5 to encode ab and inserts the new pattern abc in the dictionary to index 10.
The next two characters cb have a match at index 7 in the dictionary. Hence the encoder outputs the index 7 to encode cb and stops.
As a result the output of the encoder is 2143485 7.
2.5.3.2 Example—LZW Decoding: In this example, we take the same encoder output from the previous example and decode using LZW decoding algorithm. The input to the decoder is 2143485 7.
ZIV-LEMPEL CODING 51
Like the encoder, the decoder starts with the initial dictionary with three entries for a, b, c with indexes 1, 2, 3. After visiting the first index 2, the decoder outputs the corresponding pattern b from the dictionary.
The next output is a corresponding to the second input index 1. At this point, the decoder inserts a new pattern ba in the dictionary to index 4. This new pattern ba is formed by concatenating the first character (a) of the current output pattern (a) at the end of the last output pattern (b).
The next input index is 4, which corresponds to the pattern ba in the dictionary. Hence the decoder outputs b a and inserts the new pattern a b in the dictionary to index 5. The new pattern a b is again formed by concatenating the first character (6) of the current output pattern ba at the end of the last output pattern a.
The next input index is 3, which corresponds to c in the current dictionary. The decoder hence outputs c and inserts a new pattern b a c in the dictionary to index 6. This pattern bac has been formed by concatenating c at the end of the previous output or matching pattern ba.
The next output of the decoder is ba because of the input index 4. The decoder now inserts the new pattern cb in the dictionary to index 7. This pattern is again formed by concatenating the first character b of the current output ba at the end of the previous output c. At this point, the dictionary has only 7 entries, as shown in Table 2.12. So far the decoding process was straightforward.
Table 2.12 LZW Dictionary
Index Pattern Derived as
1 a
2 b initial
3 c
4 ba 2 + a
5 a b 1+6
6 bac 4 + c
7 cb 3+6
The next input to the decoder is index 8. But the dictionary does not have any pattern with index 8. This tricky situation arises during decoding if a pattern has been encoded using the pattern immediately preceding it during the encoding process. As a result, the last character of the pattern is the same as the first character in this tricky situation. If we carefully examine the encoding steps in the previous example, we find that index 8 corresponds to the pattern bab, which has been encoded using the immediately preceding pattern ba. And we get ba b by appending the first character b of ba with itself.
52 SOURCE CODING A L GORITHMS
Hence after the decoder receives the input index 8, it discovers that the index and a corresponding pattern does not exist in the current dictionary. It also recognizes that this tricky situation will happen because of the scenario that we discussed above. Hence the decoder creates the output by concatenating the first character of the previous output with the previous output itself. Since the previous output was ba, the decoder outputs the 6a6 in the current decoding step and inserts this new pattern in the dictionary to index
Previous << 1 .. 19 20 21 22 23 24 < 25 > 26 27 28 29 30 31 .. 100 >> Next