Chapter 15 from my Diploma
Thesis, the ...
Summary
A functional model for lossless data compression is suggested.
With the help of this model, the nonexistence of the perfect
compression algorithm can be prooved very easily.
On the other hand, the model is not algorithmical but
functional. Therefore it is not suitable for the description
of the single compression algorithms. For such a description,
a model would have to define data compression as an automaton.
To prepare the categorization of the lossless data compression
algorithms, first the terms redundancy and irrelevantness
are distinguished, and by doing this, the loessless and the lossy
data compression algorithms are seperated. To show the difference
more precisely, the criteria for irrelevantness in respect
to the human ear and eye that are important for the lossy
compression of images and audio data are described.
The following criteria for categorizing lossless data
compression algorithms are described:
redundancy: statistical vs referencing.
adaption to redundancy: static, variable or adaptiv.
symmetry: symmetry vs asymmetry of analysis and synthesis.
coding: variable vs fixed length of textsequences and code words.
source structure: length of the data: unknown, known or fixed.
Wellknown data compression algorithms (Huffman, arithmetic coding,
codebook algorithms) are described as well as old-fashioned algorithms
(Shannon-Fano, run length...) and algorithms based on new ideas
(Blaschkowski coding, Hilberg textural language machine).
As far as possible categorization of the algorithms takes place.
This shows that the proposed system of categorization is not
complete since not every algorithm can be categorized in respect
to each of the criteria. Moreover, most of the algorithms may be
varied in one or more of the categories, e.g. some of the
algorithms may be designed using either static or variable or adaptiv
adaption to redundancy.
In addition to the lossless ones lossy algorithms for image and audio
data compression are mentioned.
In three chapters the application of data compression algorithms
in a compression program or operation system environment is
discussed (attachment to an operating system, efficiency and speed,
parallelization).
It can not be stated definitely, whether data compression algorithms
with reverse asymmetry (i.e. decompression is more complex than
compression) is of practical use. Nevertheless, it shows that
this type of compression algorithm is not useless by definition.
The desired application of the algorithm defines the way it has to
be optimized.