Databases Reference
In-Depth Information
T A B L E 5 . 8
The LZW dictionary for encoding
wabba
/
b
wabba
/
b
wabba
/
b
wabba
b
/
woo
/
b
woo
/
b
woo.
Index
Entry
Index
Entry
01
b
14
ab
w
02
a
15
w
abb
03
b
16
bab
04
o
17
b
w
a
05
w
18
abb
06
w
a
19
bab
w
07
ab
20
w
o
08
bb
21
oo
09
ba
22
ob
10
ab
23
b
w
o
11
b
w
24
oob
12
w
ab
25
b
w
oo
13
bba
encoding process is shown in Table
5.8
. Notice that the 12th through the 19th entries are all
either three or four letters in length. Then we encounter the pattern
oo
for the first time and
we drop back to two-letter patterns for three more entries, after which we go back to entries
of increasing length.
The encoder output sequence is 5 2 3 3 2 16810129117165441121234.
w
Examp l e 5 . 4 . 4 : The LZW Algorithm—Decoding
In this example we will take the encoder output from the previous example and decode it
using the LZW algorithm. The encoder output sequence in the previous example was
5233216810129117165441121234
This becomes the decoder input sequence. The decoder starts with the same initial dictionary
as the encoder (Table
5.6
).
The index value 5 corresponds to the letter
as the first element of our
sequence. At the same time, we begin construction of the next element of the dictionary in
order to mimic the dictionary construction procedure of the encoder. We start with the letter
w
w
, so we decode
w
. This pattern exists in the dictionary, so we do not add it to the dictionary and continue with
the decoding process. The next decoder input is 2, which is the index corresponding to the
letter
a
. We decode an
a
and concatenate it with our current pattern to form the pattern
a
.
As this does not exist in the dictionary, we add it as the sixth element of the dictionary and
start a new pattern beginning with the letter
a
. The next four inputs 3 3 2 1 correspond to the
letters
bba
w
/
b
and generate the dictionary entries
ab
,
bb
,
ba
, and
a
/
b
. The dictionary now looks
like Table
5.9
, where the 11th entry is under construction.
The next input is 6, which is the index of the pattern
w
a
. Therefore, we decode a
w
and an
a
.
We first concatenate
w
to the existing pattern, which is
b
and form the pattern
/
/
b
w
.As
/
b
w
