Databases Reference
In-Depth Information
T A B L E 5 . 21
Initial dictionary for
Problem 4.
Index
Entry
1
a
2
b
3
h
4
i
5
s
6
t
T A B L E 5 . 22
Initial dictionary for
Problem 5.
Index
Entry
1
a
2
b
3
r
4
t
5.
A sequence is encoded using the LZW algorithm and the initial dictionary shown in
Table
5.22
.
(a)
The output of the LZW encoder is the following sequence:
3
1
4
6
8
4
2
1
2
5
10
6
11
13
6
Decode this sequence.
(b)
Encode the decoded sequence using the same initial dictionary. Does your answer
match the sequence given above?
6.
Encode the following sequence using the LZ77 algorithm:
barrayar
bbar
/
/
bby
/
bbarrayar
/
bbay
Assume you have a window size of 30 with a lookahead buffer of size 15. Furthermore,
assume that
C
(
a
)
=
1,
C
(
b
)
=
2,
C
(/
b
)
=
3,
C
(
r
)
=
4, and
C
(
y
)
=
5.
7.
A sequence is encoded using the LZ77 algorithm. Given that
C
(
a
)
=
1,
C
(/
b
)
=
2,
C
(
r
)
=
3, and
C
(
t
)
=
4, decode the following sequence of triples:
0
,
0
,
3
0
,
0
,
1
0
,
0
,
4
2
,
8
,
2
3
,
1
,
2
0
,
0
,
3
6
,
4
,
4
9
,
5
,
4
Assume that the size of the window is 20 and the size of the lookahead buffer is 10.
Encode the decoded sequence and make sure you get the same sequence of triples.
