Databases Reference
In-Depth Information
Further Reading
1.
Text Compression
, by T.C. Bell, J.G. Cleary, and I.H. Witten [
1
], provides an excellent
exposition of dictionary-based coding techniques.
2.
The Data Compression Book
, by M. Nelson and J.-L. Gailley [
69
], also does a good job
of describing the Ziv-Lempel algorithms. There is also a very nice description of some
of the software implementation aspects.
3.
Data Compression
, by G. Held and T.R. Marshall [
70
], contains a description of digram
coding under the name “diatomic coding.” The topic also includes BASIC programs that
help in the design of dictionaries.
4.
The PNG algorithm is described in a very accessible manner in “PNG Lossless Com-
pression,” by G. Roelofs [
71
]inthe
Lossless Compression Handbook
.
5.
A more in-depth look at dictionary compression is provided in “Dictionary-Based Data
Compression: An Algorithmic Perspective,” by S.C. Sahinalp and N.M. Rajpoot [
72
]in
the
Lossless Compression Handbook
.
5.8 Projects and Problems
1.
To study the effect of dictionary size on the efficiency of a static dictionary technique,
we can modify Equation (
5.1
) so that it gives the rate as a function of both
p
and the
dictionary size
M
. Plot the rate as a function of
p
for different values of
M
, and discuss
the trade-offs involved in selecting larger or smaller values of
M
.
2.
Design and implement a digram coder for text files of interest to you.
(a)
Study the effect of the dictionary size and the size of the text file being encoded on
the amount of compression.
(b)
Use the digram coder on files that are not similar to the ones you used to design the
digram coder. How much does this affect your compression?
/
3.
Given an initial dictionary consisting of the letters
abry
b
, encode the followingmessage
bbay
.
4.
A sequence is encoded using the LZWalgorithm and the initial dictionary shown in Table
5.21
.
using the LZW algorithm:
a
bbar
/
barray
/
/
bby
/
bbarrayar
/
(a)
The output of the LZW encoder is the following sequence:
6
3
4
5
2
3
1
6
2
9
11
16
12
14
4
20
10
8
23
13
Decode this sequence.
(b)
Encode the decoded sequence using the same initial dictionary. Does your answer
match the sequence given above?
