| Lossless Data Compression |
Article Index for Lossless |
Website Links For Data Compression |
Information AboutLossless Data Compression |
| CATEGORIES ABOUT LOSSLESS DATA COMPRESSION | |
| data compression | |
| lossless compression algorithms | |
|
Lossless data compression is used in many applications. For example, it is used in the popular ZIP file format and in the Unix tool Gzip . It is also often used as a component within lossy data compression technologies. Lossless compression is used when it is important that the original and the decompressed data be identical, or when no assumption can be made on whether certain deviation is uncritical. Typical examples are executable programs and source code. Some image file formats, like PNG or GIF , use only lossless compression, while others like TIFF and MNG may use either lossless or lossy methods. LOSSLESS COMPRESSION TECHNIQUES Lossless compression methods may be categorized according to the type of data they are designed to compress. The three main types of targets for compression algorithms are text, images, and sound. While, in principle, any general-purpose lossless compression algorithm (general-purpose means that they can handle all binary input) can be used on any type of data, many are unable to achieve significant compression on data that is not of the form for which they were designed to compress. Sound data, for instance, cannot be compressed well with conventional text compression algorithms. Most lossless compression programs use two different kinds of algorithms: one which generates a ''statistical model'' for the input data, and another which maps the input data to bit strings using this model in such a way that "probable" (e.g. frequently encountered) data will produce shorter output than "improbable" data. Often, only the former algorithm is named, while the latter is implied (through common use, standardization etc.) or unspecified. Statistical modeling algorithms for text (or text-like binary data such as executables) include:
Encoding algorithms to produce bit sequences are:
Many of these methods are implemented in open-source and proprietary tools, particularly LZW and its variants. Some algorithms are patented in the USA and other countries and their legal usage requires licensing by the patent holder. Because of patents on certain kinds of LZW compression, and in particular licensing practices by patent holder Unisys that many developers considered abusive, some open source activists encouraged people to avoid using the Graphics Interchange Format (GIF) for compressing image files in favor of Portable Network Graphics PNG , which combines the LZ77 -based Deflate algorithm with a selection of domain-specific prediction filters. However, the patents on LZW have now expired.http://www.unisys.com/about__unisys/lzw Many of the lossless compression techniques used for text also work reasonably well for Indexed Image s, but there are other techniques that do not work for typical text that are useful for some images (particularly simple bitmaps), and other techniques that take advantage of the specific characteristics of images (such as the common phenomenon of contiguous 2-D areas of similar tones, and the fact that color images usually have a preponderance to a limited range of colors out of those representable in the color space). As mentioned previously, lossless sound compression is a somewhat specialised area. Lossless sound compression algorithms can take advantage of the repeating patterns shown by the wave-like nature of the data – essentially using models to predict the "next" value and encoding the (hopefully small) difference between the expected value and the actual data. If the difference between the predicted and the actual data (called the "error") tends to be small, then certain difference values (like 0, +1, -1 etc. on sample values) become very frequent, which can be exploited by encoding them in few output bits. It is sometimes beneficial to compress only the differences between two versions of a file (or, in Video Compression , of an image). This is called Delta Compression (from the Greek letter Δ which is commonly used in mathematics to denote a difference), but the term is typically only used if both versions are meaningful outside compression and decompression. For example, while the process of compressing the error in the above-mentioned lossless audio compression scheme could be described as Delta Compression from the approximated sound wave to the original sound wave, the approximated version of the sound wave is not meaningful in any other context. LOSSLESS COMPRESSION METHODS For a complete list, see General purpose
Audio compression
Graphic compression
Video compression
LOSSLESS DATA COMPRESSION MUST ALWAYS MAKE SOME FILES ''LONGER'' Lossless data compression algorithms cannot guarantee compression for all input data sets. In other words, for any (lossless) data compression algorithm, there will be an input data set that does not get smaller when processed by the algorithm. This is easily proven with elementary mathematics using a Counting Argument , as follows:
Any lossless compression algorithm that makes some files shorter must necessarily make some files longer, but it is not necessary that those files become ''very much'' longer. Most practical compression algorithms provide an "escape" facility that can turn off the normal coding for files that would become longer by being encoded. Then the only increase in size is a few bits to tell the decoder that the normal coding has been turned off for the entire input. For example, DEFLATE compressed files never need to grow by more than 5 bytes per 65,535 bytes of input. In fact, if we consider files of length N, if all files were equally probable, then for any lossless compression that reduces the size of some file, the expected length of a compressed file (averaged over all possible files of length N) must necessarily be ''greater'' than N. So if we know nothing about the properties of the data we are compressing, we might as well not compress it at all. A lossless compression algorithm is only useful when we are more likely to compress certain types of files than others; then the algorithm could be designed to compress those types of data better. Thus, the main lesson from the argument is not that one risks big losses, but merely that one cannot always win. To choose an algorithm always means implicitly to select a ''subset'' of all files that will become usefully shorter. This is the theoretical reason why we need to have different compression algorithms for different kinds of files: there cannot be any algorithm that is good for all kinds of data. The "trick" that allows lossless compression algorithms, used on the type of data they were designed for, to consistently compress such files to a shorter form is that the files the algorithm are designed to act on all have some form of easily-modeled Redundancy that the algorithm is designed to remove, and thus belong to the subset of files that that algorithm can make shorter, whereas other files would not get compressed or even get bigger. Algorithms are generally quite specifically tuned to a particular type of file: for example, lossless audio compression programs do not work well on text files, and ''vice versa''. In particular, files of . There have been many claims through the years of companies achieving 'perfect-compression' where an arbitrary number of random bits can always be compressed to N-1 bits. This is, of course, impossible: if such an algorithm existed, it could be applied repeatedly to losslessly reduce any file to length 0. These kinds of claims can be safely discarded without even looking at any further details regarding the purported compression scheme. SEE ALSO
REFERENCES EXTERNAL LINKS
|
|
|