Grading Compression Algorithms I

Grading Compression Algorithms I

The easiest way to measure a compression algorithm is to feed it a ˇ leand see if it can make it much smaller. The amount of shrinkage may be represented as a percentage (“The ˇ leis 32% of the original.”) or as a factor (“The compression algorithm reduced it 5 to 1.”). This sort of absolute measure is the best test.

Saying anything more general about a compression algorithm is difˇ cultand fraught with caveats. One algorithm may produce great compression on one ˇ lebut fail to compress another at all. In many cases, it' s hard to produce a good explanation. Some algorithms have a good model that provides solid estimates of their performance while others are less consistent. It' s difˇ cult to go beyond generalities like “This algorithm is good for most images.”

While it may not be possible to provide good, general guarantees for each
algorithm, it is often possible to analyze the performance of algorithms in different
terms. Here are some of the other criteria that people use:

Overhead : Each algorithm will usually attach a certain amount of extra data that it needs to decompress a ˇ le.For instance, the statistical approaches append a list of the common characters, words, or phrases to the ˇ le.The dictionary solutions must arrange for the same dictionary to be available when a ˇ leis uncompressed. This overhead is often much smaller than the amount of space that is saved, and there is no problem when it is added. But there are many times when the overhead is larger than the amount being saved, and the size of the ˇ legrows. In some cases, the overhead also includes a small decompression program that turns the entire ˇ leinto what some call a self-extracting archive . 

Variation : Some algorithms give consistent performance. Others do very well on some types of ˇ les. The amount of variation is rarely codiˇ ed or easily predicted, but it is possible to come up with empirical results based upon past performance. ......

Tweet