Databases Reference
In-Depth Information
T A B L E 5 . 11
Final dictionary for abababab.
Index
Entry
1
a
2
b
3
ab
4
ba
5
aba
6
abab
7
b
...
T A B L E 5 . 12
Constructing the fourth entry of
the dictionary while decoding.
Index
Entry
1
a
2
b
3
ab
4
b
...
T A B L E 5 . 13
Constructing the fifth entry
(stage one).
Index
Entry
1
a
2
b
3
ab
4
ba
5
a
...
We beginwith the same initial dictionary as the encoder (Table
5.10
). The first two elements
in the received sequence 1235
are decoded as
a
and
b
, giving rise to the third dictionary
entry
ab
, and the beginning of the next pattern to be entered in the dictionary,
b
. The dictionary
at this point is shown in Table
5.12
.
The next input to the decoder is 3. This corresponds to the dictionary entry
ab
. Decoding
each in turn, we first concatenate
a
to the pattern under construction to get
ba
. This pattern
is not contained in the dictionary, so we add this to the dictionary (keep in mind, we have not
used the
b
from
ab
yet), which now looks like Table
5.13
.
The new entry starts with the letter
a
. We have only used the first letter from the pair
ab
.
Therefore, we now concatenate
b
to
a
to obtain the pattern
ab
. This pattern is contained in the
dictionary, so we continue with the decoding process. The dictionary at this stage looks like
Table
5.14
.
...
