Chapter 15 from my Diploma Thesis, the ...


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:

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.