Databases Reference
In-Depth Information
T A B L E 5 . 6
Initial LZW dictionary.
Index
Entry
1
b
2
a
3
b
4
o
5
w
T A B L E 5 . 7
Constructing the 12th entry of
the LZW dictionary.
Index
Entry
01
b
02
a
03
b
04
o
05
w
06
w
a
07
ab
08
bb
09
ba
10
a
/
b
11
b
w
12
w
…
. This “pattern” is in the dictionary so we concate-
nate the next letter to it, forming the pattern
The encoder first encounters the letter
w
w
a
. This pattern is not in the dictionary, so we
encode
a
to the dictionary as the sixth element
of the dictionary, and begin a new pattern starting with the letter
a
.As
a
is in the dictionary,
we concatenate the next element
b
to form the pattern
ab
. This pattern is not in the dictionary,
so we encode
a
with its dictionary index value 2, add the pattern
ab
to the dictionary as the
seventh element of the dictionary, and start constructing a new pattern with the letter
b
.We
continue in this manner, constructing two-letter patterns, until we reach the letter
w
with its dictionary index 5, add the pattern
w
w
in the sec-
ond
abba
. At this point, the output of the encoder consists entirely of indices from the initial
dictionary: 5 2 3 3 2 1. The dictionary looks like Table
5.7
. (The 12th entry in the dictionary
is still under construction.) The next symbol in the sequence is
a
. Concatenating this to
w
w
,
we get the pattern
a
. This pattern already exists in the dictionary (item 6), so we read the
next symbol, which is
b
. Concatenating this to
w
ab
. This pattern does
not exist in the dictionary, so we include it as the 12th entry in the dictionary and start a new
pattern with the symbol
b
. We also encode
w
a
, we get the pattern
w
a
with its index value of 6. Notice that after a
series of two-letter entries, we now have a three-letter entry. As the encoding progresses, the
length of the entries keeps increasing. The longer entries in the dictionary indicate that the
dictionary is capturing more of the structure in the sequence. The dictionary at the end of the
w
