Data Compression
Literature references and annotations by Dick Grune, dick@dickgrune.com.
Last update: Thu Dec 10 18:56:34 2009.
These references and annotations were originally intended
for personal use and are presented here only in the hope
that they may be useful to others.
There is no claim to completeness or even correctness.
Each annotation represents my understanding of the text
at the moment I wrote the annotation.
No guarantees given; comments and content criticism welcome.
Alistair Moffat,
Andrew Turpin,
On the Implementation of MinimumRedundancy Prefix Codes,
in Data Compression Conference,
1996,
pp. 170179.
Describes in detail a modification to Huffman compression, which can be
implemented very efficiently.
Full of nifty and complicated algorithms.
Gregory K. Wallace,
The JPEG still picture compression standard,
Commun. ACM,
vol. 34,
#4,
April 1991,
pp. 3144.
JPEG stands for "Joint Photographic Experts Group".
The picture is divided into blocks of 8 µ 8 pixels.
Each such block is subjected to a Forward Discrete Cosine Transform, a
Fourier Transform derivative, which yields in principle 64 coefficients:
the DC component and 63 spatial harmonics, the AC components.
the blocks are treated in "reading order", from top left to bottom right.
Three forms of compression are done:
1. the DC component is replaced by its difference from the previous one;
this is lossless.
2. depending on the desired compression, the AC components are quantized
either by reduction to one of the values in a given table or by truncating
to their N most significant bits; this is lossy.
3. the resulting stream undergoes Huffman coding.
There is a completely different scheme for doing lossless JPEG compression.
It works by defining a predictor (e.g. the average of the pixel above and the
one to the left) and then recording the difference between this prediction and
the actual value, followed by the usual Huffman coding.
Didier Le Gall,
MPEG: a video compression standard for multimedia applications,
Commun. ACM,
vol. 34,
#4,
April 1991,
pp. 4758.
In principle MPEG consists of a sequence of JPEG pictures; in practice
there is a lot of additional trickery, which has to do with interpicture
compression.
The pictures in and MPEG stream are of three types:
I pictures (I for intra), which are new, independent pictures, used to start
a new set of related pictures;
P pictures (P for predicted), which follow a given I picture and which are
specified as differences with the I picture; and
B pictures (B for Bidirectional), which come in between the I and P pictures
and which are specified as the weighted average of the surrounding I and P
pictures.
A possible sequence could be: I B B P B B P B B I ...
MPEG allows but does not require much more sophisticated motion detection
methods.
Ming Lou,
Overview of the px64 kbit/s video coding standard,
Commun. ACM,
vol. 34,
#4,
April 1991,
pp. 6063.
Very brief description.
The official name of the coding is "CCITT Recommendation H.261 Video Format".
It consists of a hierarchical data structure, with each field consisting
of a header and a sequence of subfields, each of which has again a similar
format.
The lowest level contains the data, compressed in various ways, or may even
be omitted, if there was no change.
Gordon V. Cormack,
Data compression on a database system,
Commun. ACM,
vol. 28,
#12,
Dec. 1985,
pp. 13361342.
The exit and entry hooks for record retrieval are used to compress and
decompress the records.
Since the records are relatively small, little is known about their
contents, speed is essential, and space is at a premium, the following
drastic scheme was conceived.
Basically, each character is compressed using a Huffman table determined
by the previous character; the Huffman tables are determined offline by
sampling the data base.
Two problems had to be solved, bot relating to the size of the fixed
tables inside the routine.
The first was that the usual Huffman tables have some entries of
excessive length; these are used very infrequently but still take up
space inside the routine.
This was solved by a modification to the Huffman table generation
algorithm to limit the length of any encoding to 15 bits.
This degrades the tables a little, but not much.
The second was that 256 Huffman tables just occupy too much space,
period.
This was solved as follows.
For each pair of tables, the degradation caused by combining the tables
was computed, and the tables with the lowest degradation penalty were
combined, until the algorthm fitted.
The algorithm achieved a 65% size reduction on the records, and a 42%
reduction in database size; the difference is caused by nonrecord
material in the database.
The compression slowed down the computation by 17 %, but sped up I/O by
33%, resulting in a net gain.
John G. Cleary,
Ian H. Witten,
Data Compression Using Adaptive Coding and Partial String Matching,
IEEE Transactions on Communications,
1984,
vol. 32,
pp. 396402.
Improves LempelZiv on two counts: records the frequency of the words in the
dictionary and adapts the code accordingly; and uses arithemtic encoding.
